Successive Totients

Computer Science Level 2

For all positive integers $n$ , the totient function $\phi (n)$ denotes the number of positive integers $\leq n$ coprime to $n$ .

It turns out that if we apply the totient function successively on any positive integer $n>1$ , after finitely many operations we get the number $1$ . In other words, for all positive integers $n>1$ , there exists a positive integer $m$ such that $\underbrace{\phi ( \phi ( \phi ( \cdots \phi (n ) \cdots )))}_{m \text{ times}}= 1$ .

For all $n \in \mathbb{N}$ , let $f(n)$ denote the minimum number of times we need to apply the totient function successively on $n$ to get the number $1$ . Find the last three digits of $\displaystyle \sum \limits_{n=1}^{2014} f(n)$ .

Details and assumptions

As an explicit example, here's how you'd find $f(5)$ : $\begin{array}{rcl} \phi (5)& = & 4 \\ \phi (\phi (5)) & = & 2 \\ \phi (\phi (\phi (5))) & = & 1 \\ \end{array}$ Note that we had to apply the totient function three times on $5$ to get the number $1$ , so $f(5)=3$ .
By convention, $f(1)=0$ .
Just to clarify, this is a computer science problem.

The answer is 108.

2 solutions

Logan Dymond
Jan 26, 2014

python:

n = 2014

primes = [True]*(n+1)
primes[0]=primes[1]= False
for i in range(int(sqrt(n))+1):
    if primes[i] == True:
        for j in range(i**2,n+1,i):
            primes[j] = False

def Totient(k):
    num = k
    i=2
    while i <= k:
        if primes[i]==True:
            if k%i == 0:
                num = num - num/i
        i  += 1
    return num

tcount = {1:0}
for i in range(2,n+1):
    tcount[i] = tcount[Totient(i)] + 1

print sum(tcount[i] for i in range(2,n+1))

Generate a list of the first 2014 primes via the Sieve of Eratosthenes. Define the function $\phi(n)$ by looping through each of the primes and checking for divisibility. Then, I defined $f(n)$ recursively by $f(1)=0, f(n) = f(\phi(n))+1$ , requiring me to only calculate the totient once per value. Note, $\forall n, \phi(n) < n$ , so we won't run into any issues with the recursion.

Output: $17108$

Answer: $\boxed{108}$

That's exactly my intended solution!

You should be a bit careful with your wording though; $\phi (n) \not < n$ when $n=1$ . :P

Also, shouldn't you import math before you use sqrt ?

Sreejato Bhattacharya - 7 years, 4 months ago

oh, yes, you are absolutely right, when I copy pasted my code I copy pasted the meat inside of my timing function, and my "from math import sqrt" was outside of the timing function.

Logan Dymond - 7 years, 4 months ago

Yes,I did it the same way as well..I was familiar with the problem though..was it by anychance inspired from http://projecteuler.net/problem=214

Thaddeus Abiy - 7 years, 4 months ago

I'm not very active in ProjectEuler, so I wasn't aware of that. This problem is completely original.

Sreejato Bhattacharya - 7 years, 4 months ago

@Sreejato Bhattacharya – Oh ok..Sorry,my bad..you should have a look at the thread for that problem though(you should be able to solve it with this).They usually have pretty good solutions.There was an $O(nloglogn)$ solution if I remember correctly.

Thaddeus Abiy - 7 years, 4 months ago

@Thaddeus Abiy – Yes, I just saw it. Thanks for posting it! :)

Sreejato Bhattacharya - 7 years, 4 months ago

Abrar Nihar
Jan 25, 2014

Python!

from fractions import gcd

def Phi(n): # Computes the totient function!
    Result = 0
    for i in range (1, n+1):
        if gcd(i,n) == 1:
            Result += 1
    return Result

Anything = 5

def f(n): # The function f given in the question!
    Result = 1
    Shot = Phi(n)
    while 0 < Anything < 10:
        if Shot == 1:
            break
        elif Phi(Shot) == 1:
            Result += 1
            break
        else:
            Result += 1
            Shot = Phi(Shot)
    return Result

Answer = 0

for n in range (2, 2015): # f(1) = 0 by convention, so we won't count that!
    Answer += f(n)

Desired_Answer = Answer % 1000

print Answer, Desired_Answer

Output: $\fbox{17108, 108}$ .

Okay first, you should establish that the problem statement is indeed true, i.e. $f(n)$ is finite for all $n \in \mathbb{N}$ . This is easy to verify using strong induction. For the base case, note that $\varphi (2) = 1$ , so $f(2)=1$ . Assume the statement is true for $1, 2, 3, \cdots , n$ for some $n \in \mathbb{N}$ , so $f(k)$ is finite for all $1 \leq k \leq n$ . Note that $\varphi (n+1) \leq n$ , and hence $f(\varphi (n+1))$ is finite, which implies so must be $f(n+1)$ . This completes the inductive step. $\blacksquare$

This logic also shows a way to make your code more efficient. Apparently your runtime is huge (atleast in my computer)! Note that $f(n)= f(\varphi (n))+1$ . Instead of using a function, declare an array with $2014$ elements whose $n^{\text{th}}$ element stores $f(n)$ .

a= [0]

for x in range(2, 2015):
  a.append(a[phi(x)-1]+1)

Just print the sum of the elements of this array now. This seems to be the most efficient way to solve this problem.

Sreejato Bhattacharya - 7 years, 4 months ago

Successive Totients

The answer is 108.

2 solutions

0 pending reports