On Nov 6, 2024, at 1:22 PM, Bill Allombert wrote:
Dear PARI lovers,
A new little game!
Find positive integers n such that
2*eulerphi(n) = n+1
I know 8 solutions, but maybe there are more!
Cheers,
Bill.
The "obvious" solutions are
2^1 - 1 = 1
(2^1 - 1)*(2^1 + 1) = 2^2 - 1
(2^1 - 1)*(2^1 + 1)*(2^2 + 1) = 2^4 - 1
(2^1 - 1)*(2^1 + 1)*(2^2 + 1)*(2^4 + 1) = 2^8 - 1
(2^1 - 1)*(2^1 + 1)*(2^2 + 1)*(2^4 + 1)*(2^8 + 1) = 2^16 - 1
and
(2^1 - 1)*(2^1 + 1)*(2^2 + 1)*(2^4 + 1)*(2^8 + 1)*(2^16 + 1) = 2^32 - 1
The factors > 1 in parentheses are prime, leading to easy eulerphi() evaluations of 1, 2, 2^(1+2), 2^(1+2+4), 2^(1+2+4+8), and 2^(1+2+4+8+16).
Since 2^32 + 1 is not prime, eulerphi(2^32 + 1) is not 2^32, so this vein has played out: 2^64 - 1 does not have the required property.
By cheating (searching online for n such that eulerphi(n) divides n+1) I found two more values: 83623935 and 83623935*83623937 = 6992962672132095.
Checking this suggested the following result, which is easy to prove, and "explains" the sequence of six "obvious" solutions above:
If eulerphi(n) = (n+1)/2, and n+2 is prime, then eulerphi(n*(n+2)) = (n*(n+2)+1)/2