A227946 -id:A227946 - 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.

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

Offset: 1

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

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

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

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.

T. D. Noe, Table of n, a(n) for n = 1..1002
P. A. Catlin, Concerning the iterated phi-function, Amer Math. Monthly 77 (1970), pp. 60-61.
T. D. Noe, Computing Numbers in Section I of the Totient Iteration
T. D. Noe, Primes in classes of the iterated totient function, JIS 11 (2008) 08.1.2
Harold Shapiro, An arithmetic function arising from the phi function, Amer. Math. Monthly, Vol. 50, No. 1 (1943), 18-30.

Cf. A000010, A003434, A049108, A092873 (prime factors of a(n)), A060611, A098196, A227946.

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

a007755 = (+ 1) . fromJust . (`elemIndex` a003434_list) . (subtract 1)
-- Reinhard Zumkeller, Feb 08 2013, Jul 03 2011

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 *)

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.

More terms from David W. Wilson, May 15 1997

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

A227944 Number of iterations of "take odd part of phi" (A053575) to reach 1 from n.

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 2, 3, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 1, 2, 1, 2, 1, 2, 2, 3, 3, 2, 1, 2, 2, 3, 2, 2, 3, 4, 1, 3, 2, 1, 2, 3, 3, 2, 2, 3, 3, 4, 1, 2, 2, 3, 1, 2, 2, 3, 1, 3, 2, 3, 2, 3, 3, 2, 3, 2, 2, 3, 1, 4, 2, 3, 2, 1, 3, 3, 2, 3, 2, 3, 3, 2, 4, 3, 1, 2, 3, 2, 2

Offset: 1

Max Alekseyev, Oct 03 2013

a(n) >= A256757(n) - 1.

			a(18) = 2 because it takes two steps to reach 1 from 18: phi(18) = 6, the odd part of which is 3, and phi(3) = 2, the odd part of which is 1.
a(19) = 3 because it takes three steps to reach 1 from 19: phi(19) = 18, the odd part of which is 9, and phi(9) = 6, the odd part of which is 3, and phi(3) = 2, the odd part of which is 1.

T. D. Noe, Table of n, a(n) for n = 1..10000

A variant of A049115: a(n) = A049115(n) unless n is a power of 2.

Cf. A003434, A227946.

a227944 n = fst $
            until ((== 1) . snd) (\(i, x) -> (i + 1, a053575 x)) (0, n)
-- Reinhard Zumkeller, Oct 09 2013

oddPhi[n_] := Module[{phi = EulerPhi[n]}, phi/2^IntegerExponent[phi, 2]]; Table[Length[NestWhileList[oddPhi[#] &, n, # > 1 &]] - 1, {n, 100}] (* T. D. Noe, Oct 07 2013 *)

For n > 1, a(n) = a(A053575(n)) + 1.

A049117 Smallest number which when Euler phi function is repeatedly applied have not reached a power of 2 in n steps.

Original entry on oeis.org

3, 7, 19, 47, 163, 487, 1307, 2879, 19683, 39367, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 86093443, 258280327, 688747547, 3486784401, 10460353203

Offset: 0

Labos Elemer

a(21) <= 31381059609 = 3^22. [Donovan Johnson, Feb 06 2010]

Note that all terms so far are primes or powers of 3. Is it true that all terms have this form? - T. D. Noe, Oct 07 2013

			The corresponding iterated phi-sequences are:
{3, 2, 1},
{7, 6, 2, 1},
{19, 18, 6, 2, 1},
{47, 46, 22, 10, 4, 2, 1},
{163, 162, 54, 18, 6, 2, 1},
{487, 486, 162, 54, 18, 6, 2, 1}, ...

A variant of A227946.

Cf. A000010.

a[n_] := Module[{i = 1}, While[IntegerQ[Log[2, Nest[EulerPhi, i, n]]], i++ ]; i]; (* Sam Handler (sam_5_5_5_0(AT)yahoo.com), Sep 04 2006 *)

More terms from Jud McCranie, Jan 14 2000
More terms from Sam Handler (sam_5_5_5_0(AT)yahoo.com), Sep 04 2006
a(19)-a(20) from Donovan Johnson, Feb 06 2010

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

Extensions

A227944 Number of iterations of "take odd part of phi" (A053575) to reach 1 from n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A049117 Smallest number which when Euler phi function is repeatedly applied have not reached a power of 2 in n steps.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions