Problems & Puzzles:
Prime values for
It has been proved
'The number of divisors
Q1. Can you give
your own proof for this statement?
The first values for σ(n) = prime are:
3, 7, 13, 31, 31, 127, 307, ... (for n=2, 4, 9, 16, 25, 64, 289,
Q2: Find large
prime values for
Q3: Will it happen
is the same prime value for two distinct n values?
Contributions came from Faride Firoozbakht, Joseph L. Pe and J. K.
Andersen. The three of them solved basically the questions 1 & 2 in the
same way. Only Andersen provided diverse answers for Q2 and
responded to the question 3.
Here is the Andersen contribution:
Q1. If x and y are relatively prime then sigma(x*y) = sigma(x)*sigma(y).
Hence, if sigma(n) is prime then n = p^(a-1) where p is prime.
sigma(n) = sigma(p^(a-1)) = p^(a-1) + p^(a-2) + ... + p + 1 =
(p^a-1)/(p-1). d(n) = d(p^(a-1)) = a. If a = c*d is composite then p^c-1
divides p^a-1, and so sigma(n) is composite. This proofs sigma(n) can
only be prime if d(n) is prime.
Q2. sigma(2^(a-1)) = 2^a-1. This means all Mersenne primes are
The largest known prime is sigma(2^25964950) = 2^25964951-1, found by
Martin Nowak and GIMPS.
Numbers on the form (x^a-1)/(x-1) are called generalized repunits (GRU,
sometimes with restrictions on x and a). The base x must be prime to
give a solution for this question. The largest proven GRU where the base
is an odd prime is sigma(15679^3498) = (15679^3499-1)/15678. It has
14676 digits and was proven by Bouk de Water and David Broadhurst. It is
hard to prove primality for GRU's:
http://primes.utm.edu/top20/page.php?id=16 . The largest known prp
GRU with odd prime base is the 40309-digit sigma(1907^12288) =
(1907^12289-1)/1906, found by Jiong Sun.
If p is prime then sigma(p^2) = p^2+p+1 = p*(p+1)+1. This form can
easily be proven prime. sigma((1717*2^8320+1)^2) =
(1717*2^8320+1)^2+(1717*2^8320+1)+1 is a 5016-digit prime. I found and
proved it with PrimeForm/GW by testing p's in the Prime Pages database.
Q3. This will never happen. It would require different (p,a) pairs
giving the same value of (p^a-1)/(p-1). [See his answer to