Totient Chains

Let $\phi$ be Euler’s totient function, i.e. for a natural number $n$,
$\phi(n)$ is the number of $k$, $1 \le k \le n$, for which $\gcd(k, n) = 1$.
By iterating $\phi$, each positive integer generates a decreasing chain of numbers ending in $1$.
E.g. if we start with $5$ the sequence $5,4,2,1$ is generated.
Here is a listing of all chains with length $4$:

\begin{align}
5,4,2,1&\\
7,6,2,1&\\
8,4,2,1&\\
9,6,2,1&\\
10,4,2,1&\\
12,4,2,1&\\
14,6,2,1&\\
18,6,2,1
\end{align}

Only two of these chains start with a prime, their sum is $12$.
What is the sum of all primes less than $40000000$ which generate a chain of length $25$?

To solve this problem, we can iterate through all prime numbers less than $40000000$ and for each prime number, generate the chain using Euler’s totient function. We can then check if the length of the chain is equal to 25 and if so, add the prime number to a running sum.

Here is the Python code to solve this problem:

“`python
import math

def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)

def phi(n):
count = 0
for i in range(1, n + 1):
if gcd(i, n) == 1:
count += 1
return count

def generate_chain(n):
chain = [n]
while chain[-1] != 1:
chain.append(phi(chain[-1]))
return chain

def sum_of_primes(length):
prime_sum = 0
for i in range(2, 40000000):
is_prime = True
for j in range(2, int(math.sqrt(i)) + 1):
if i % j == 0:
is_prime = False
break
if is_prime:
chain = generate_chain(i)
if len(chain) == length:
prime_sum += i
return prime_sum

print(sum_of_primes(25))
“`

Running this code will give you the sum of all primes less than $40000000$ which generate a chain of length $25$. Please note that this solution may take some time to execute due to the large numbers involved.

More Answers: