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,1

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.

Formula

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

Example

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}.

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

Prog

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

Crossrefs

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

Sequence in context: A014292 A244445 A066078 * A133852 A093150 A301297

Adjacent sequences: A058336 A058337 A058338 * A058340 A058341 A058342

Keyword

nonn

Author

Labos Elemer, Dec 14 2000

Extensions

Offset corrected by Arkadiusz Wesolowski, Jan 19 2013

Status

approved