A007374 Smallest k such that phi(x) = k has exactly n solutions. (Formerly M1093)

1, 2, 4, 8, 12, 32, 36, 40, 24, 48, 160, 396, 2268, 704, 312, 72, 336, 216, 936, 144, 624, 1056, 1760, 360, 2560, 384, 288, 1320, 3696, 240, 768, 9000, 432, 7128, 4200, 480, 576, 1296, 1200, 15936, 3312, 3072, 3240, 864, 3120, 7344, 3888, 720, 1680, 4992

Offset

2,2

Comments

The Carmichael Totient Conjecture is that there is no k such that phi(x) = k has a unique solution x. So a(1) does not exist.

Ford proved that a(n) exists for all n > 1. - Charles R Greathouse IV, Oct 13 2014

References

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 840.

Wacław Sierpiński, Elementary Theory of Numbers, p. 234, Warsaw, 1964.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Donovan Johnson, Table of n, a(n) for n = 2..7448 (terms up to a(1023) from T. D. Noe)

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

Kevin Ford, The distribution of totients, Ramanujan J., (2) No. 1-2 (1998); New version of the 1998 article, arXiv:1104.3264 [math.NT], 2011-2013.

Kevin Ford, The number of solutions of phi(x) = m, Annals of Mathematics 150:1 (1999), pp. 283-311.

S. D. Merow, Has Carmichael's Totient Conjecture Been Proven? No, No, It Has Not, Notices Amer. Math. Soc., 66 (No. 5, 2019), 759-761.

A. Schlafly and S. Wagon, Carmichael's conjecture on the Euler function is valid below 10^{10,000,000}, Mathematics of Computation, 63 No. 207 (1994), 415-419. See Table 2.

Eric Weisstein's World of Mathematics, Phi function.

Eric Weisstein's World of Mathematics, Carmichael's Totient Function Conjecture.

Mathematica

a = Table[ 0, {10^5} ]; Do[ s = EulerPhi[ n ]; If[ s < 100001, a[ [ s ] ]++ ], {n, 1, 10^6} ]; Do[ k = 1; While[ a[ [ k ] ] != n, k++ ]; Print[ k ], {n, 2, 75} ]

Prog

(PARI) v=vectorsmall(10^6); for(n=1, 1e7, t=eulerphi(n); if(t<=#v, v[t]++))
u=vector(100); for(i=1, #v, t=v[i]; if(t&&t<=#u&&u[t]==0, u[t]=i)); u[2..#u]
\\ Charles R Greathouse IV, Oct 13 2014

Crossrefs

Essentially same as A014573. Records in A105207, A105208.

Cf. A000010, A097942, A105207, A105208.

Sequence in context: A187941 A085083 A076745 * A105207 A202148 A215825

Adjacent sequences: A007371 A007372 A007373 * A007375 A007376 A007377

Keyword

nonn,easy,nice

Author

N. J. A. Sloane, Mira Bernstein, Robert G. Wilson v

Status

approved