cp's OEIS Frontend

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

%I A058339 #31 Aug 18 2024 04:36:59
%S A058339 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,
%T A058339 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,
%U A058339 2,2,18,2,6,12,2,2,2,2,2,2,13,13,6,2,13,2,34
%N A058339 Number of solutions to 1 + phi(x) = prime(n), where phi is A000010.
%H A058339 T. D. Noe, <a href="/A058339/b058339.txt">Table of n, a(n) for n = 1..10000</a>
%H A058339 Max Alekseyev, <a href="https://oeis.org/wiki/User:Max_Alekseyev/gpscripts">PARI/GP Scripts for Miscellaneous Math Problems</a> (invphi.gp).
%H A058339 David M. Bressoud, <a href="https://drive.google.com/file/d/1UMesJ93mpdCabQvETMqOBH8eCR4JWA6X/view?usp=sharing">CNT.m</a>, Computational Number Theory Mathematica package.
%F A058339 a(n) = A210500(n) + A210501(n). - _Arkadiusz Wesolowski_, Jan 19 2013
%e A058339 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.
%e A058339 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}.
%p A058339 with(numtheory): >[seq(nops(invphi(-1+ithprime(i))),i=1..256)];
%t A058339 Needs["CNT`"]; Table[Length[PhiInverse[Prime[n] - 1]], {n, 100}] (* _T. D. Noe_, Dec 11 2013 *)
%t A058339 Take[Length /@ Values@ KeySelect[KeyMap[# + 1 &, PositionIndex@ Array[EulerPhi, 10^4]], PrimeQ], 84] (* _Michael De Vlieger_, Dec 29 2017 *)
%o A058339 (PARI) a(n) = invphiNum(prime(n) - 1); \\ _Amiram Eldar_, Aug 18 2024, using _Max Alekseyev_'s invphi.gp
%Y A058339 Cf. A000010, A000040, A006093, A058340, A066071, A066072, A066073, A066074, A066075, A066076, A066077, A066080.
%K A058339 nonn
%O A058339 1,1
%A A058339 _Labos Elemer_, Dec 14 2000
%E A058339 Offset corrected by _Arkadiusz Wesolowski_, Jan 19 2013