- #1

huba

- 32

- 0

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.

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]

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]

Last edited: