A378507 The smallest number k such that the equation phi(phi(x)) = k has exactly n solutions.

10, 56, 6, 1, 84, 312, 2, 200, 464, 36, 108, 4, 12, 88, 816, 264, 440, 360, 552, 120, 224, 8, 3696, 1320, 928, 176, 624, 1472, 832, 5728, 24, 4560, 1080, 2000, 16, 2848, 72, 1312, 1872, 80, 1120, 216, 880, 336, 23360, 448, 3808, 10608, 648, 528, 352, 9280, 32

Offset: 2

Author

Amiram Eldar, Nov 29 2024

Keywords

• nonn

Comments

The smallest number k such that A378506(k) = n.

If phi(phi(x)) = k has a solution, then according to Carmichael's totient function conjecture there is at least one another number y != x such that phi(y) = phi(x) and then y is also a solution. Therefore, according to this conjecture, a(1) does not exist.

Links

• Amiram Eldar, Table of n, a(n) for n = 2..1000
• Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
• David M. Bressoud, A Course in Computational Number Theory (web page), CNT.m, Computational Number Theory Mathematica package.
• Eric Weisstein's World of Mathematics, Carmichael's Totient Function Conjecture.
• Wikipedia, Carmichael's totient function conjecture.

Crossrefs

Cf. A000010, A010554, A007374, A378506.

Programs

Mathematica

s[n_] := Sum[PhiMultiplicity[k], {k, PhiInverse[n]}]; seq[len_] := Module[{v = Table[0, {len+1}], c = 0, k = 1, ns}, While[c < len, ns = s[k]; If[0 < ns <= len + 1 && v[[ns]] == 0, v[[ns]] = k; c++]; k++]; Rest[v]]; seq[30] (* using David M. Bressoud's CNT.m *)

PARI

s(n) = vecsum(apply(x -> invphiNum(x), invphi(n))); \\ using Max Alekseyev's invphi.gp
lista(len) = {my(v = vector(len+1), c = 0, k = 1, ns); while(c < len, ns = s(k); if(ns > 0 && ns <= len + 1 && v[ns] == 0, c++; v[ns] = k); k++); vecextract(v,"^1");}