Consider the number $50$.
$50^2 = 2500 = 2^2 \times 5^4$, so $\phi(2500) = 2 \times 4 \times 5^3 = 8 \times 5^3 = 2^3 \times 5^3$. 1
So $2500$ is a square and $\phi(2500)$ is a cube.
Find the sum of all numbers $n$, $1 \lt n \lt 10^{10}$ such that $\phi(n^2)$ is a cube.
1 $\phi$ denotes Euler’s totient function.
This problem involves advanced number theory, specifically Phi, or Euler’s Totient Function. The Euler totient function, denoted as φ(n), is an arithmetic function that counts the amount of integers less than n that are coprime to n. Two numbers are coprime if their greatest common factor is 1.
Also note that we are looking for where φ(n^2) is a cube, and the sum of those numbers where 1 < n < 10^10. Firstly, observe that we can express n^2 in its prime factorization as follows: n^2 = (p1^a1 x p2^a2 x p3^a3 ...,)^2, where pn represents a prime number and an represents the power to which the prime is raised. The key property of the Euler totient function that we will apply here is: φ(p^k) = p^(k-1)x(p-1), where p is a prime number and k is an integer. So such a integer n which φ(n^2) is a cube must has the form either (1) 2^a * p^b or (2) p1^b * p2^c where p, p1, p2 are odd primes and a is an odd number, b, c > 1 are even numbers.
But we can’t afford to check the sum one by one, so we need to get the relationship that the cube root of totient(n^2) is an integer.
1. For condition (1), φ(n^2) = n(1 – 1/2)(1 – 1/p) should be a cube. For number of this type, we consider the factors 2^a and p^b separately. We can suggest that b = 2l, and a must be in the form of 6k+1, where l & k are any natural numbers. Note that a, b > 1, 2^b * p^a < 10^10. 2. For condition (2), φ(n^2) = n(1 - 1/p1)(1 - 1/p2) which should be a cube as well. For numbers of this kind, we take that b = c = 2l, and p1 * p2^b < 10^10 where l>0.
To calculate sum involving prime numbers you’ll have to be aware of the amount of primes till 10^5 (since we are checking till 10^10), by Sieve or some Prime Number Theorem methods.
Find all possible a,b,c,l,k values that hold conditions (1) and (2) respectively using loops or other method depending on which program you use.
Get the sum by 2^b * p^a for condition (1) and p1 * p2^b for condition (2) with all possible a,b,c,l,k values you found.
I have explained all possible conditions, now implement this in a program and compute the sum as it’s computationally heavy to even find primes till 10^5.
The key to solving this problem is actually finding the relationship between the cube root of the totient and the square root of the original number.
This is a conceptually difficult problem so take time to understand this.
More Answers:
Peredur Fab EfrawgCrazy Function
Golomb’s Self-describing Sequence