Re: Game: find the integers

[Kurt Foster <drsardonicus@earthlink.net>]

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