|
|
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^(n-1).
Shapiro shows that the smallest number is greater than 2^(n-1). 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: Springer-Verlag, 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)=n-1.
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
|
|
|
|