Conjecture on the gap between integers having the same number of co-primes

145 Views Asked by At

Based on experimental data while analyzing the related question posted here I observed the following which I am presenting as conjectures.

Conjecture 1: For every natural number $k$, the equation $\varphi(x) = \varphi(x+2k)$ has infinitely many solutions. Further, if $x = n$ is a solution then $\frac{n}{\varphi(n)}$ is bounded.

Conjecture 2: The only solutions of $\varphi(x) = \varphi(x+3)$ are $x = 3,5$.

$\varphi(n)$ denotes the totient function.

Any reference to these in literature.

Update: I have verified conjecture 2 upto $n = 2 \times 10^8$.

2

There are 2 best solutions below

0
On BEST ANSWER

In my earlier comment I misremembered the author of the conjecture. The conjecture that is the first half of your conjecture 1 (that $\phi(n+2k)=\phi(n)$ has infinitely many solutions for any $k$ is due to Schinzel. The relevant entry in Guy's "Unsolved Problems in Number Theory" is B36 (in the third edition page 138-139). He lists two papers of Schinzel where this conjecture is discussed, both in Acta Arithmetica, one from 1958, the other from 1959. The full citations given by Guy (which I have not checked) are "A. Schinzel, Sur l'equation $\phi(x+k) = \phi(x)$, Acta Arithmetica, 4 (1958), 1818-184, MR 21 # 5597." and "A. Schinzel, A. Wakulicz, Sur l'equation $\phi(x+k) = \phi(x)$ II, Acta Arithmetica, 5 (1959), 425-426, MR 23, #A831."

Guy also mentions that Sierpinski proved that for any $k$, $\phi(n+2k)= \phi(n)$ has at least one solution. There's a bit connected to this and related problems in B36, so you should probably check the entry in the book out.

4
On

Partial answer :

Conjecture $2$ is false : One of the entries in the OEIS-sequence in the linked question besides of $1$ is congruent $1$ modulo $3$. With the help of this entry I constructed $$n=9134280520365$$ which satisfies $$\varphi(n)=\varphi(n+3)$$