|
%I #49 Mar 26 2019 23:41:00
%S 1,2,3,5,11,17,41,83,137,257,641,1097,2329,4369,10537,17477,35209,
%T 65537,140417,281929,557057,1114129,2384897,4227137,8978569,16843009,
%U 35946497,71304257,143163649,286331153,541073537,1086374209,2281701377,4295098369
%N 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.
%C 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.
%C 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).
%C 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
%C The indices of odd prime terms are given by n=A136040(k)+2 for k=1,2,3,.... - _T. D. Noe_, Dec 14 2007
%C 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
%D J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 83, p. 29, Ellipses, Paris 2008. Also Entry 137, p. 47.
%D R. K. Guy, Unsolved Problems in Number Theory, 2nd Ed. New York: Springer-Verlag, p. 97, 1994, Section B41.
%H T. D. Noe, <a href="/A007755/b007755.txt">Table of n, a(n) for n = 1..1002</a>
%H P. A. Catlin, <a href="http://www.jstor.org/stable/2316857">Concerning the iterated phi-function</a>, Amer Math. Monthly 77 (1970), pp. 60-61.
%H T. D. Noe, <a href="http://www.sspectra.com/math/IteratedPhi2.pdf">Computing Numbers in Section I of the Totient Iteration</a>
%H T. D. Noe, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL11/Noe/noe080107.html">Primes in classes of the iterated totient function</a>, JIS 11 (2008) 08.1.2
%H Harold Shapiro, <a href="http://www.jstor.org/stable/2303988">An arithmetic function arising from the phi function</a>, Amer. Math. Monthly, Vol. 50, No. 1 (1943), 18-30.
%F a(n) = smallest m such that A049108(m)=n.
%F Alternatively, a(n) = smallest m such that A003434(m)=n-1.
%F a(n+2) ~ 2^n.
%e a(3) = 3 because trajectory={3,2,1}. n=1: a(1)=1 because trajectory={1}
%t 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_ *)
%o (Haskell)
%o a007755 = (+ 1) . fromJust . (`elemIndex` a003434_list) . (subtract 1)
%o -- _Reinhard Zumkeller_, Feb 08 2013, Jul 03 2011
%Y Cf. A000010, A003434, A049108, A092873 (prime factors of a(n)), A060611, A098196, A227946.
%Y A060611 has the same initial terms but is a different sequence.
%K nonn,nice
%O 1,2
%A Pepijn van Erp [ vanerp(AT)sci.kun.nl ]
%E More terms from _David W. Wilson_, May 15 1997
%E Additional comments from James S. Cronen (cronej(AT)rpi.edu)
|
