

A007755


Smallest number m such that the trajectory of m under iteration of Euler's totient function phi(n) [A000010] contains exactly n distinct numbers, including m and the fixed point.


24



1, 2, 3, 5, 11, 17, 41, 83, 137, 257, 641, 1097, 2329, 4369, 10537, 17477, 35209, 65537, 140417, 281929, 557057, 1114129, 2384897, 4227137, 8978569, 16843009, 35946497, 71304257, 143163649, 286331153, 541073537, 1086374209, 2281701377, 4295098369
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Least integer k such that the number of iterations of Euler phi function needed to reach 1 starting at k (k is counted) is n.
a(n) is smallest number in the class k(n) which groups families of integers which take the same number of iterations of the totient function to evolve to 1. The maximum is 2*3^(n1).
Shapiro shows that the smallest number is greater than 2^(n1). Catlin shows that if a(n) is odd and composite, then its factors are among the a(k), k < n. For example a(12) = a(5) a(8). There is a conjecture that all terms of this sequence are odd.  T. D. Noe, Mar 08 2004
The indices of odd prime terms are given by n=A136040(k)+2 for k=1,2,3,....  T. D. Noe, Dec 14 2007
Shapiro mentions on page 30 of his paper the conjecture that a(n) is prime for each n > 1, but a(13) is composite and so the conjecture fails.  Charles R Greathouse IV, Oct 28 2011


REFERENCES

J.M. De Koninck, Ces nombres qui nous fascinent, Entry 83, p. 29, Ellipses, Paris 2008. Also Entry 137, p. 47.
R. K. Guy, Unsolved Problems in Number Theory, 2nd Ed. New York: SpringerVerlag, p. 97, 1994, Section B41.


LINKS



FORMULA

a(n) = smallest m such that A049108(m)=n.
Alternatively, a(n) = smallest m such that A003434(m)=n1.
a(n+2) ~ 2^n.


EXAMPLE

a(3) = 3 because trajectory={3,2,1}. n=1: a(1)=1 because trajectory={1}


MATHEMATICA

f[n_] := Length[ NestWhileList[ EulerPhi, n, Unequal, 2]]  1; a = Table[0, {30}]; Do[b = f[n]; If[a[[b]] == 0, a[[b]] = n; Print[n, " = ", b]], {n, 1, 22500000}] (* Robert G. Wilson v *)


PROG

(Haskell)
a007755 = (+ 1) . fromJust . (`elemIndex` a003434_list) . (subtract 1)


CROSSREFS

A060611 has the same initial terms but is a different sequence.


KEYWORD

nonn,nice


AUTHOR

Pepijn van Erp [ vanerp(AT)sci.kun.nl ]


EXTENSIONS

Additional comments from James S. Cronen (cronej(AT)rpi.edu)


STATUS

approved



