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 - The Fusion of Science and Community**

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

Loading...

Similar Threads for Iteration Euler's function | Date |
---|---|

I Preconditioning for linear equations | Nov 25, 2016 |

Euler Representation of complex numbers | Jan 8, 2016 |

Jacobi and Gauss-Seidel Iteration | Apr 16, 2015 |

Correlation between Iterative Methods and Convolution Codes | Mar 28, 2015 |

**Physics Forums - The Fusion of Science and Community**