Euler’s totient function is the numerical values that are relatively prime to a number n and less than n. For example, if n = 6, the values 1 and 5 are relatively prime to 6, and the φ(n) is 2.
Euler’s totient maximum is a value n < N, such that n/ φ(n) is maximum. For example, if N = 10, then the number 6 has the maximum value of n/ φ(n), i.e., 3.
The formula for totient and totient maximum is:
The following table displays the relative primes of n, φ(n), and n/ φ(n) for n <= 11:
| n | Relatively Prime | φ(n) | n/ φ(n) |
|---|---|---|---|
| 2 | 1 | 1 | 2 |
| 3 | 1,2 | 2 | 1.5 |
| 4 | 1,3 | 2 | 2 |
| 5 | 1,2,3,4 | 4 | 1.25 |
| 6 | 1,5 | 2 | 3 |
| 7 | 1,2,3,4,5,6 | 6 | 1.1666… |
| 8 | 1,3,5,7 | 4 | 2 |
| 9 | 1,2,4,5,7,8 | 6 | 1.5 |
| 10 | 1,3,7,9 | 4 | 2.5 |
| 11 | 1,2,3,4,5,6,7,8,9,10 | 10 | 0.909… |
The table shows that if N = 11, the totient maximum is 6.
The following Python code demonstrates how to calculate the totient maximum for a general limit:
As the above formula illustrates, multiplying prime numbers until the specified limit is reached generates the totient maximum for that limit.
# variable n stores the final resultn = 1# variable stores the limit to calculate the totient maximum forL = 100# variable primes stores list of primesprimes = [2, 3, 5, 7, 11, 13, 17, 19, 21, 23, 29, 31]for i in primes:# store the product in a temp variable to compare it with the limittemp = n*i# exit the loop if if product is greater than the limitif temp > L:break# if product is less than the limit multiply the prime with the previous# value of n and store in nn = n*iprint("The totient maximum of L is", n)
The above code calculates the totient maximum for the number 100. From the above formula, we know that the totient maximum of 100 is equal to 1 x 2 x 3 x 5 = 30.
for loop to iterate over them.for loop completes contains the totient maximum.Free Resources