cp's OEIS Frontend

A357916 Primes p that can be written as phi(k) + d(k) for some k, where phi(k) = A000010(k) is Euler's totient function and d(k) = A000005(k) is the number of divisors of k.

%I A357916 #14 Feb 29 2024 13:45:32
%S A357916 2,3,5,13,23,59,113,137,229,457,509,523,661,1021,2063,3541,3923,4973,
%T A357916 5449,5521,9949,10103,10273,12659,14107,15601,16249,17033,22063,25321,
%U A357916 29759,32507,34843,36293,37273,52501,54059,62753,68449,68909,89329,99409,103963,111347,125509,139297,146309,157231
%N A357916 Primes p that can be written as phi(k) + d(k) for some k, where phi(k) = A000010(k) is Euler's totient function and d(k) = A000005(k) is the number of divisors of k.
%C A357916 Does any prime have more than one representation as phi(k) + d(k)?
%H A357916 Robert Israel, <a href="/A357916/b357916.txt">Table of n, a(n) for n = 1..3000</a>
%e A357916 a(4) = 13 is a term because 13 is prime and for k = 16, phi(k) + d(k) = 8 + 5 = 13.
%p A357916 N:= 10^6: # to allow k <= N
%p A357916 pmax:=  evalf(N/(exp(gamma)*log(log(N))+3/log(log(N)))): # lower bound for phi(k), k<=N
%p A357916 P:= {3}:
%p A357916 for k from 1 to sqrt(N) do
%p A357916   n:= k^2;
%p A357916   v:= numtheory:-phi(n)+numtheory:-tau(n);
%p A357916   if v <= pmax and isprime(v) then
%p A357916      P:= P union {v};
%p A357916   fi
%p A357916 od:
%p A357916 sort(convert(P,list));
%t A357916 Select[Table[EulerPhi[n]+DivisorSigma[0,n],{n,400000}],PrimeQ]//Sort (* _Harvey P. Dale_, Feb 29 2024 *)
%Y A357916 Cf. A000005, A000010, A061468, A357917.
%K A357916 nonn
%O A357916 1,1
%A A357916 _J. M. Bergot_ and _Robert Israel_, Oct 19 2022