Iterating Euler's totient function [tex]\varphi(n)[/tex], it eventually arrives at 1. Let h(n) denote the least number of iterations to arrive at 1. For instance, h(18)=3, ie [tex]\varphi^{3}(18)=1[/tex]. There is a conjecture (or is there a proof?) that the largest n for which h(n)=k is [tex]2\times 3^{k-1}[/tex]. The only reference I found on the internet was a short note in a comment to Sloane's A007755 (the smallest n for which h(n)=k), saying that the maximum value is of that form.(adsbygoogle = window.adsbygoogle || []).push({});

Although I haven't found a proof, I think that I have at least a simple result, using the [tex]2\times 3^{k-1}[/tex] form. Richard K. Guy (2004), in "Unsolved Problems in Number Theory", p.149 (haven't read it, found it in Google Book Search) describes perfect totient numbers as those n for which [tex]n = \varphi(n) + \varphi^{2}(n) + \varphi^{3}(n) + ... + 2 + 1[/tex], and says that all powers of 3 are perfect totient numbers. I haven't seen the proof for all powers of 3 being perfect totient numbers, but I would reason this way:

It is easy to prove by induction that

[tex]\sum^{k-1}_{j=0}2\times 3^{j}+1=3^{k}[/tex].

As for all [tex]x\geq j, \varphi^{j}(2\times 3^{x}) = 2\times 3^{x-j}[/tex], and [tex]\varphi^{x+1}(2\times 3^{x}) = \varphi(2) = 1 [/tex],

[tex]\sum^{k+1}_{j=1}\varphi^{j}(2\times 3^{k})=3^{k}[/tex]

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Iteration of Euler's phi function

**Physics Forums | Science Articles, Homework Help, Discussion**