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.

Improve this question
$\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$
    – Gerhard Paseman
    Jun 29, 2017 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, 2017 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, 2019 at 14:41

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
7
  • 2
    $\begingroup$ Note that A067798 also includes a file from Giovanni Resta containing the first 76 terms, ending with 1103806594815. $\endgroup$
    – Robert Israel
    Jun 29, 2017 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$
    – Noam D. Elkies
    Jun 29, 2017 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$
    – Gerhard Paseman
    Jun 29, 2017 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$
    – Gerhard Paseman
    Jun 29, 2017 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$
    – Robert Israel
    Jun 29, 2017 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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