|
| |
|
|
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.
|
|
14
|
|
|
|
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 the 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
|
P. A. Catlin, Concerning the iterated phi function, Amer. Math. Monthly, Vol. 77, No. 1 (1970), 60-61.
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.
Harold Shapiro, An arithmetic function arising from the phi function, Amer. Math. Monthly, Vol. 50, No. 1 (1943), 18-30.
|
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n = 1..1002
T. D. Noe, Computing Numbers in Section I of the Totient Iteration
|
|
|
FORMULA
|
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}] (from Robert G. Wilson v)
|
|
|
PROG
|
(Haskell)
a007755 = (+ 1) . fromJust . (`elemIndex` a003434_list) . (subtract 1)
-- Reinhard Zumkeller, Feb 08 2013, Jul 03 2011
|
|
|
CROSSREFS
|
Cf. A000010, A003434, A049108, A092873 (prime factors of a(n)), A060611, A098196.
Sequence in context: A062737 A085613 A082605 * A060611 A103598 A077497
Adjacent sequences: A007752 A007753 A007754 * A007756 A007757 A007758
|
|
|
KEYWORD
|
nonn,nice,changed
|
|
|
AUTHOR
|
Pepijn van Erp [ vanerp(AT)sci.kun.nl ]
|
|
|
EXTENSIONS
|
More terms from David W. Wilson May 15 1997
Additional comments from James S. Cronen (cronej(AT)rpi.edu)
|
|
|
STATUS
|
approved
|
| |
|
|
