A058339 Number of solutions to 1 + phi(x) = prime(n), where phi is A000010.

2, 3, 4, 4, 2, 6, 6, 4, 2, 2, 2, 8, 9, 4, 2, 2, 2, 9, 2, 2, 17, 2, 2, 6, 17, 4, 2, 2, 9, 6, 2, 2, 2, 2, 2, 2, 7, 4, 2, 2, 2, 10, 2, 21, 2, 2, 2, 2, 2, 2, 6, 2, 31, 2, 10, 2, 2, 2, 9, 8, 2, 2, 2, 2, 16, 2, 2, 18, 2, 6, 12, 2, 2, 2, 2, 2, 2, 13, 13, 6, 2, 13, 2, 34

Offset: 1

Author

Labos Elemer, Dec 14 2000

Keywords

• nonn

Examples

			The equation phi(x) = p-1 always has at least 2 solutions: p and 2p a prime and a composite. Many times more than 2 x gives phi(x) = p-1. For p-1 = 96 there are 17 (that is, an odd number of) solutions: {97, 119, 153, 194, 195, 208, 224, 238, 260, 280, 288, 306, 312, 336, 360, 390, 420}, 4 odd and 13 even numbers while for p-1 = 100 there are 4 (an even number of) solutions: {101, 125, 202, 250}. For all odd solutions x, 2x is also a solution.
1+phi(x) = 11 has 2 solutions: 11 and 22; 1+phi(x) = 241 has 31 solutions: x = {241, 287, 305, 325, 369, 385, 429, 465, 482, 488, 495, 496, 525, 572, 574, 610, 616, 620, 650, 700, 732, 738, 744, 770, 792, 858, 900, 924, 930, 990, 1050}.
		

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
• David M. Bressoud, CNT.m, Computational Number Theory Mathematica package.

Crossrefs

Cf. A000010, A000040, A006093, A058340, A066071, A066072, A066073, A066074, A066075, A066076, A066077, A066080.

Programs

Maple

with(numtheory): >[seq(nops(invphi(-1+ithprime(i))),i=1..256)];

Mathematica

Needs["CNT`"]; Table[Length[PhiInverse[Prime[n] - 1]], {n, 100}] (* T. D. Noe, Dec 11 2013 *)
Take[Length /@ Values@ KeySelect[KeyMap[# + 1 &, PositionIndex@ Array[EulerPhi, 10^4]], PrimeQ], 84] (* Michael De Vlieger, Dec 29 2017 *)

PARI

a(n) = invphiNum(prime(n) - 1); \\ Amiram Eldar, Aug 18 2024, using Max Alekseyev's invphi.gp

Formula

a(n) = A210500(n) + A210501(n). - Arkadiusz Wesolowski, Jan 19 2013

Extensions

Offset corrected by Arkadiusz Wesolowski, Jan 19 2013