cp's OEIS Frontend

A058277 Number of values of k such that phi(k) = n, where n runs through the values (A002202) taken by phi.

%I A058277 #56 Feb 16 2025 08:32:43
%S A058277 2,3,4,4,5,2,6,6,4,5,2,10,2,2,7,8,9,4,3,2,11,2,2,3,2,9,8,2,2,17,2,10,
%T A058277 2,6,6,3,17,4,2,3,2,9,2,6,3,17,2,9,2,7,2,2,3,21,2,2,7,12,4,3,2,12,2,8,
%U A058277 2,10,4,2,21,2,2,8,3,4,2,3,19,5,2,8,2,2,6,2,31,2,9,10
%N A058277 Number of values of k such that phi(k) = n, where n runs through the values (A002202) taken by phi.
%C A058277 Carmichael (1922) conjectured that the number 1 never appears in this sequence. Sierpiński conjectured and Ford (1998) proved that all integers greater than 1 occur in the sequence. Erdős (1958) proved that if s >= 1 appears in the sequence then it appears infinitely often. - Nick Hobson, Nov 04 2006
%C A058277 A002202(n) occurs a(n) times in A007614. - _Reinhard Zumkeller_, Nov 22 2015
%D A058277 Édouard Lucas, Théorie des Nombres, Blanchard 1958.
%H A058277 T. D. Noe, <a href="/A058277/b058277.txt">Table of n, a(n) for n=1..10000</a>
%H A058277 Max Alekseyev, <a href="https://oeis.org/wiki/User:Max_Alekseyev/gpscripts">PARI/GP Scripts for Miscellaneous Math Problems</a> (invphi.gp).
%H A058277 R. D. Carmichael, <a href="http://dx.doi.org/10.1090/S0002-9904-1922-03504-5">Note on Euler's totient function</a>, Bull. Amer. Math. Soc. 28 (1922), pp. 109-110.
%H A058277 Paul Erdős, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa4/aa413.pdf">Some remarks on Euler's totient function</a>, Acta Arith. 4 (1958), pp. 10-19.
%H A058277 M. Farrokhi D. G., <a href="/A058277/a058277.txt">Gap function to compute the inverse of Euler's totient function</a>.
%H A058277 Kevin Ford, <a href="http://dx.doi.org/10.1090/S1079-6762-98-00043-2">The distribution of totients</a>, Electron. Res. Announc. Amer. Math. Soc. 4 (1998), 27-34.
%H A058277 Nick Hobson, <a href="https://web.archive.org/web/20160328125112/http://qbyte.org/puzzles/p152s.html">Solution to puzzle 152: Totient valence</a>.
%H A058277 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/TotientValenceFunction.html">Totient Valence Function</a>.
%t A058277 max = 300; inversePhi[_?OddQ] = {}; inversePhi[1] = {1, 2}; inversePhi[m_] := Module[{p, nmax, n, nn}, p = Select[Divisors[m] + 1, PrimeQ]; nmax = m * Times @@ (p/(p-1)); n = m; nn = Reap[While[n <= nmax, If[EulerPhi[n] == m, Sow[n]]; n++]] // Last; If[nn == {}, {}, First[nn] ] ]; Reap[For[n = 1, n <= max, n = If[n == 1, 2, n+2], nn = inversePhi[n] ; If[nn != {} , Sow[nn // Length] ] ] ] // Last // First (* _Jean-François Alcover_, Nov 21 2013 *)
%o A058277 (Haskell)
%o A058277 import Data.List (group)
%o A058277 a058277 n = a058277_list !! (n-1)
%o A058277 a058277_list = map length $ group a007614_list
%o A058277 -- _Reinhard Zumkeller_, Nov 22 2015
%o A058277 (PARI) lista(nmax) = {my(m); for(n = 1, nmax, m = invphiNum(n); if(m > 0, print1(m, ", ")));} \\ _Amiram Eldar_, Nov 15 2024 using _Max Alekseyev_'s invphi.gp
%Y A058277 The nonzero terms of A014197.
%Y A058277 Cf. A000010, A002202, A007614.
%Y A058277 Cf. A006511 (largest k for which A000010(k) = A002202(n)).
%K A058277 nonn,easy
%O A058277 1,1
%A A058277 Claude Lenormand (claude.lenormand(AT)free.fr), Jan 05 2001
%E A058277 More terms from _Nick Hobson_, Nov 04 2006