11
$\begingroup$

Does anybody have any ideas how to solve the equation $x=\phi(x)+\phi(x+1)-1$, where $x$ is a natural number and $\phi$ is Euler's totient function?

I failed even to figure out whether this equation has finite number of solutions or infinite.

Any help will be appreciated.

$\endgroup$
3
  • 1
    $\begingroup$ It seems nicer to write it as y=phi(y)+phi(y-1). What have you tried? Can you deduce some divisibility properties of y? Does this arise as part of a research problem? Gerhard "Has More Questions And Answers" Paseman, 2017.06.29. $\endgroup$ Jun 29 '17 at 17:50
  • 1
    $\begingroup$ It appears that there is a lot of solutions, the number of which appears to grow logarithmically. $\endgroup$
    – Wojowu
    Jun 29 '17 at 17:55
  • $\begingroup$ My belief is that the solutions of the equation, A067798 from the OEIS, are the same that the solutions of $$x=\phi(\phi(x)+\phi(x+1)-1)+\phi(\phi(x)+\phi(x+1))-1.$$ I've tested it for the segment of integers $1\leq x\leq 10^6$. I have not studied subsequent compositions. $\endgroup$
    – user142929
    Oct 17 '19 at 14:41
18
$\begingroup$

This is OEIS Sequence A067798. Nothing else seems to be known about it; at any rate OEIS gives no references to the literature, only a link to a list of further such $x$ from Giovanni Resta that extends it from the 43rd solution, $722015$, to the 76th, $1103806594815$, which is just a a bit larger than $2^{40}$. (Thanks to Robert Israel for noting this link in his comment.)

It seems very hard to do anything with the problem other than make a few elementary observations (e.g. all $x>2$ will be odd), do some heuristics (biases mod $3$, $4$, $5$, and other small moduli; expected asymptotics), and use yet more computing power to find a handful of further solutions.

$\endgroup$
7
  • 2
    $\begingroup$ Note that A067798 also includes a file from Giovanni Resta containing the first 76 terms, ending with 1103806594815. $\endgroup$ Jun 29 '17 at 18:41
  • $\begingroup$ Right, I saw the link but forgot to check it. I'll edit my reply to give this link (oeis.org/A067798/b067798.txt) and remove my shorter list. $\endgroup$ Jun 29 '17 at 18:46
  • $\begingroup$ It would be of interest to know for these solutions if y/phi(y) stays in a narrow range. I suspect it may be bounded over all solutions. Gerhard "Good A Conjecture As Any" Paseman, 2017.06.29. $\endgroup$ Jun 29 '17 at 18:53
  • $\begingroup$ Is it possible that 2^(2^n) is a solution for y for infinitely many n? Gerhard "Easier Than Fermat Primes, Perhaps?" Paseman, 2017.06.29. $\endgroup$ Jun 29 '17 at 19:07
  • 4
    $\begingroup$ @GerhardPaseman That would require $\varphi(2^{2^n}-1) = 2^{2^n-1}$. For $n \ge 6$, $2^{2^n}-1$ is divisible by $641$, so $\varphi(2^{2^n}-1)$ divisible by $\varphi(641) = 640$ which is not a power of $2$. So $2^{2^n}$ is never a solution for $n \ge 6$. $\endgroup$ Jun 29 '17 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.