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
Keywords
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
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
Extensions
Offset corrected by Arkadiusz Wesolowski, Jan 19 2013
Comments