cp's OEIS Frontend

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.

%I A007755 #49 Mar 26 2019 23:41:00
%S A007755 1,2,3,5,11,17,41,83,137,257,641,1097,2329,4369,10537,17477,35209,
%T A007755 65537,140417,281929,557057,1114129,2384897,4227137,8978569,16843009,
%U A007755 35946497,71304257,143163649,286331153,541073537,1086374209,2281701377,4295098369
%N 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.
%C A007755 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 A007755 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 A007755 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 A007755 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 A007755 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 A007755 J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 83, p. 29, Ellipses, Paris 2008. Also Entry 137, p. 47.
%D A007755 R. K. Guy, Unsolved Problems in Number Theory, 2nd Ed. New York: Springer-Verlag, p. 97, 1994, Section B41.
%H A007755 T. D. Noe, <a href="/A007755/b007755.txt">Table of n, a(n) for n = 1..1002</a>
%H A007755 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 A007755 T. D. Noe, <a href="http://www.sspectra.com/math/IteratedPhi2.pdf">Computing Numbers in Section I of the Totient Iteration</a>
%H A007755 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 A007755 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 A007755 a(n) = smallest m such that A049108(m)=n.
%F A007755 Alternatively, a(n) = smallest m such that A003434(m)=n-1.
%F A007755 a(n+2) ~ 2^n.
%e A007755 a(3) = 3 because trajectory={3,2,1}. n=1: a(1)=1 because trajectory={1}
%t A007755 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 A007755 (Haskell)
%o A007755 a007755 = (+ 1) . fromJust . (`elemIndex` a003434_list) . (subtract 1)
%o A007755 -- _Reinhard Zumkeller_, Feb 08 2013, Jul 03 2011
%Y A007755 Cf. A000010, A003434, A049108, A092873 (prime factors of a(n)), A060611, A098196, A227946.
%Y A007755 A060611 has the same initial terms but is a different sequence.
%K A007755 nonn,nice
%O A007755 1,2
%A A007755 Pepijn van Erp [ vanerp(AT)sci.kun.nl ]
%E A007755 More terms from _David W. Wilson_, May 15 1997
%E A007755 Additional comments from James S. Cronen (cronej(AT)rpi.edu)