Problems & Puzzles: Puzzles

Puzzle 335. Prime values for σ(n). It has been proved that: 'The number of divisors d(n) is prime whenever σ(n) is prime'. 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 σ(n). Q3: Will it happen again that σ(n) 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 solutions.
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 Puzzle 318, CR]

***

 

 

---