Problems & Puzzles: Puzzles

Puzzle 715 phi(x + n) = sigma(x - n)

Jahangeer Kholdi & Farideh Firoozbakht sent the following nice puzzle

Consider the equation,

phi(x + n) = sigma(x - n)           (n, *)

where n is a positive integer.

It is easily shown that x is a solution of the equation (1, *) 
iff x is an average of twin prime pairs (A014574 ).

Q. Prove: " For every integer n greater than 1, the set of solutions 
of  (n, *)  is a non empty finite set."  or find a counterexample.

Contributions came from Emmanuel Vantieghem


Emmanuel wrote:

I prove that, if there is a solution  x  for some n > 1, then x - n = y  is strictly less than  4n^2.

Suppose y  satisfies the equation
   sigma(y) = phi(y + 2n)    (**)

and suppose  y >= 4n^2.

If   y  has a prime divisor p <= Sqrt(y) then it also has a divisor d = y/d >= Sqrt(y).

Thus, sigma(y) > y+d >= y+Sqrt(y) >= y+2n, which contradicts the equality (**), since  phi(m)  is allways less than  m. Thus, y is prime and sigma(y) = y+1. 

From (**) it is clear that y+2n = z cannot be prime, unless n = 1. Thus, z has a prime divisor p <= sqrt(z). Since  phi(z) = z*Product(1 - 1/r), where r runs through all prime divisors of z, it follows :
  phi(z) <= z(1-1/p) = z - z/p <= z - Sqrt(z) = y+2n - Sqrt(y+2n) < y+2n - Sqrt(y) <= y+2n - 2n = y.

This is a contradiction which shows that no solution y can be bigger than 4n^2.


Could it also be worthwile to mention that I found at least one solution for all  n <= 10000 ? Therefore, I think the conjecture that for every  n > 2 there are finetely many solutions of (n,*)  is very reasonable.


Jud McCranie wrote:

I forgot to send my work on puzzle 715.  I checked to 3,800,000 and didn't find a counterexample


Records   |  Conjectures  |  Problems  |  Puzzles