Problems & Puzzles: Puzzles

Puzzle 489. Mersenne Primes & 0, 23 & 1535 Farideh Firoozbakht  sent the following puzzle: If q is a Mersenne prime then sigma(sigma(phi(q+1))) = q+1.  Other than the Mersenne primes three numbers (0, 23 and 1535) have the same property.  Q. Can you find other such numbers?

---

Contribution came from Antoine Verroken.

***

Antoine wrote:

1.between 1 and 1.000.000 the numbers ( q + 1 ) are :

1 , 4 , 8 , 24 , 32 , 128 , 1536 , 8192 , 131072 , 524288

2.it seems that these numbers have the factorization : 2^a * 3^b

3. if b= 0 à q + 1 = 2^a

- phi ( 2^a ) = 2^( a – 1 )

- sigma (2^( a – 1 ) ) = 1 + 2 + 2^2 + … + 2^( a – 1 ) = 2^a – 1

- sigma ( 2^a – 1 ) must be equal to ( q + 1 ) = 2^a

Therefor 2^a – 1 must be prime

This is the case for 4 , 8 , 32 , 128 , 8192 , 131072 , 524288

***

Farideh shares his own answer:

My answer to this puzzle:

If 2^p-1 is prime (Mersenne prime) and sigma(2^p+1) = 3*2^(p-1) then for
q = 3*2^(2p-1)-1 we have sigma(sigma(phi(q+1))) = q+1.

Proof : sigma(sigma(phi(q+1))) = sigma(sigma(phi((3*2^(2p-1)-1)+1)))
= sigma(sigma(phi(3*2^(2p-1))))
= sigma(sigma(2^(2p-1)))
= sigma(2^(2p)-1)
= sigma((2^p-1)*(2^p+1))
= sigma(2^p-1)*sigma(2^p+1)
= 2^p*(3*2^(p-1))
= 3*2^(2p-1)
= q+1

Examples :

1. p = 2 ; 2^2-1 is prime and sigma(2^2+1) = 3*2^(2-1) so q1 = 3*2^(2*2-1)-1 = 23

2. p = 5 ; 2^5-1 is prime and sigma(2^5+1) = 3*2^(5-1) so q2 = 3*2^(2*5-1)-1 = 1535

Next such p, if it exists is greater than 1278.

For finding other such numbers we need to know the factorizations of 2^p+1, where p
is in the sequence A000043.

A000043 : 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607,
1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937,
21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839,
859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917

***