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

***