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$:


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:

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:
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
if is_prime:
chain = generate_chain(i)
if len(chain) == length:
prime_sum += i
return prime_sum


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:
Divisor Square Sum
Combined Volume of Cuboids
Flea Circus

Error 403 The request cannot be completed because you have exceeded your quota. : quotaExceeded


Recent Posts

Don't Miss Out! Sign Up Now!

Sign up now to get started for free!