login
This site is supported by donations to The OEIS Foundation.

 

Logo

The October issue of the Notices of the Amer. Math. Soc. has an article about the OEIS.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A023194 Numbers n such that sigma(n) (sum of divisors of n) is prime. 62

%I

%S 2,4,9,16,25,64,289,729,1681,2401,3481,4096,5041,7921,10201,15625,

%T 17161,27889,28561,29929,65536,83521,85849,146689,262144,279841,

%U 458329,491401,531441,552049,579121,597529,683929,703921,707281,734449,829921,1190281

%N Numbers n such that sigma(n) (sum of divisors of n) is prime.

%C All numbers except the first are squares. Why? - _Zak Seidov_, Jun 10 2005

%C Answer from Gabe Cunningham (gcasey(AT)MIT.EDU): "From the fact that the sigma (the sum-of-divisors function) is multiplicative, we can derive that the sigma(n) is even except when n is a square or twice a square.

%C "If n = 2*(2*k + 1)^2, that is, n is twice an odd square, then sigma(n) = 3*sigma((2*k + 1)^2). If n = 2*(2*k)^2, that is, n is twice an even square, then sigma(n) is only prime if n is a power of 2; otherwise we have sigma(n) = sigma(8*2^m) * sigma(k/2^m) for some positive integer m.

%C "So the only possible candidates for values of n other than squares such that sigma(n) is prime are odd powers of 2. But sigma(2^(2*m + 1)) = 2^(2*m + 2) - 1 = (2^(m + 1) + 1) * (2^(m + 1) - 1), which is only prime when m = 0, that is, when n = 2. So 2 is the only nonsquare n such that sigma(n) is prime."

%C All numbers on this list also have a prime number of divisors. - Howard Berman (howard_berman(AT)hotmail.com), Oct 29 2008

%C This is because 1 + p + ... + p^k is divisible by 1 + p + ... + p^j if k + 1 is divisible by j + 1. - _Robert Israel_, Jan 13 2015

%C From Gabe Cunningham's comment it follows that the alternate Mathematica program provided below is substantially more efficient as it only tests squares. - _Harvey P. Dale_, Dec 12 2010

%C Each number of this sequence is a prime power. This follows from the facts that sigma is multiplicative and sigma(n) > 1 for n > 1. Thus, for n > 1, a(n) is of the form a(n) = k^2 where k = p^m, with p prime, so the divisors of a(n) are {1, p, p^2, p^3, ..., (p^m)^2}, and this set is a multiplicative group (modulo q); if q is prime, q = sigma(k^2). Reciprocally, if q is a prime of the form 1 + p + p^2 + ... + p^(2*m), then q = sigma(p^(2*m)) (definition of sigma). - _Michel Lagneau_, Aug 17 2011, edited by _Franklin T. Adams-Watters_, Aug 17 2011

%C The sums of divisors of the even numbers in this sequence are the Mersenne primes, A000668. These even numbers are in A061652. - _Hartmut F. W. Hoft_, May 04 2015

%C Numbers n = p^(q - 1), where p is a prime, such that (p^q - 1)/(p - 1) is prime. Then q must be a prime that does not divide p - 1. - _Thomas Ordowski_, Nov 18 2017

%H T. D. Noe and David W. Wilson, <a href="/A023194/b023194.txt">Table of n, a(n) for n = 1..10000</a>

%p N:= 10^8: # to get all entries <= N

%p Primes:= select(isprime, [2,seq(2*i+1, i=1..floor((sqrt(N)-1)/2))]):

%p P2:= select(t -> (t > 2 and t < 1 + ilog2(N)), Primes):

%p cands:= {seq(seq([p,q],p=Primes), q=P2)} union {[2,2]}:

%p f:= proc(pq) local t,j;

%p t:= pq[1]^(pq[2]-1);

%p if t <= N and isprime((t*pq[1]-1)/(pq[1]-1)) then t else NULL fi

%p end proc:

%p map(f,cands);

%p # if using Maple 11 or earlier, uncomment the next line

%p # sort(convert(%,list)); # _Robert Israel_, Jan 13 2015

%t Select[ Range[ 100000 ], PrimeQ[ DivisorSigma[ 1, # ] ]& ] (* _David W. Wilson_ *)

%t Prepend[Select[Range[1100]^2, PrimeQ[DivisorSigma[1,#]]&],2] (* _Harvey P. Dale_, Dec 12 2010 *)

%o (PARI) for(x=1,1000,if(isprime(sigma(x)),print(x))) /* Jorge Coveiro (jorgecoveiro(AT)yahoo.com), Dec 23 2004 */

%o (PARI) list(lim)=my(v=List([2])); forprime(p=2,sqrtint(lim\=1), if(isprime(p^2+p+1), listput(v,p^2))); forstep(e=4,logint(lim,2),2, forprime(p=2,sqrtnint(lim,e), if(isprime((p^(e+1)-1)/(p-1)), listput(v,p^e)))); Set(v) \\ _Charles R Greathouse IV_, Aug 17 2011; updated Jul 22 2016

%o (MAGMA) [n: n in [1..2*10^6] | IsPrime(SumOfDivisors(n))]; // _Vincenzo Librandi_, May 05 2015

%o (Python)

%o from sympy import isprime, divisor_sigma

%o A023194_list = [2]+[n**2 for n in range(1,10**3) if isprime(divisor_sigma(n**2))] # _Chai Wah Wu_, Jul 14 2016

%Y Cf. A055638 (the square roots of the squares in this sequence).

%Y Cf. A023195 (the primes produced by these n).

%K nonn,easy,nice

%O 1,1

%A _David W. Wilson_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 22 15:16 EDT 2018. Contains 315270 sequences. (Running on oeis4.)