login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Numbers n such that sigma(n) + phi(n) is a composite number of the form p^k where p is a prime.
0

%I #13 Sep 04 2014 16:56:42

%S 2,4,12,15,110,121,125,511,908,2047,31269,58252,180544,2275680,

%T 3776877,4164717,4835820,8386433,8388607,32284479,60333777,82628532,

%U 122016110,174438012,238609292,513528686,515718093,919749786,1043394771,3851465145,4264386607

%N Numbers n such that sigma(n) + phi(n) is a composite number of the form p^k where p is a prime.

%C All semiprimes of the form 2^m-1 are in the sequence. Because if 2^m-1=p*q where p and q are prime then sigma(2^m-1)+phi(2^m-1)=(p+1)*(q+1)+(p-1)*(q-1)=2(p*q+1)=2^(m+1). 15, 511, 2047, 8388607 and 137438953471 are the first five such terms of the sequence.

%C Also if p=(2^m-5)/9 is prime then n=4*p is in the sequence. Because phi(n)+sigma(n)=9*p+5=2^m. 12, 908, 58952 and 77433143050453552574776799557806810784652 are the first four such terms of the sequence.

%C Let h(n)=sigma(n)+phi(n), except for n=4 and n=121 for all other known terms n of the sequence h(n) is of the form 2^m. Note that h(4)=3^2 and h(121)=3^5, what is the next term n of the sequence such that h(n) is odd?

%e sigma(12)+phi(12)=sigma(15)+phi(15)=2^5,

%e sigma(180544)+phi(180544)=2^19.

%t h[n_]:=DivisorSigma[1,n]+EulerPhi[n];Do[a=h[n];If[Length[FactorInteger[a]] == 1 && !PrimeQ[a], Print[n]],{n, 123456789}]

%o (PARI) is(n)=isprimepower(sigma(n)+eulerphi(n))>1 \\ _Charles R Greathouse IV_, Sep 04 2014

%Y Cf. A000010, A000203, A038344, A065387.

%K nonn,nice

%O 1,1

%A _Jahangeer Kholdi_, Jan 07 2014

%E a(24)-a(31) from _Donovan Johnson_, Feb 19 2014