I don't know if was in the literature a characterization of the solutions for pair of integers $(x,y)$ of the equation $$\varphi(2+\varphi(x))=2^{y-1},\tag{1}$$ where $\varphi(n)$ denotes the Euler's totient function and we consider that our integers satisfy $x\geq 1$ and $y\geq 2$.

Since I've created the equation with the purpose to get a relationship with numbers related with constructible polygons, and Mersenne primes I've the following basic facts of our equation $(1)$.

Claim 1. Each Mersenne prime $x=2^p-1$ satisfies $(1)$. That is, if we know a Mersenne prime $x=2^p-1$ then $$(x,y)=(2^p-1,p)$$ is a solution of $(1)$.$\square$

Because we know the relationship of Fermat primes and the power of two (and the Euler's totient function) and constructible polygons, see if you want this Wikipedia, or from [1] as Theorem 4.3 and Theorem 4.5, one deduce next.

Claim 2. If $(x,y)$ is a solution of $(1)$ then $$2+\varphi(x)=2^k\cdot(\text{ a product of distinct Fermat primes}),\tag{2}$$ for some positive integer $k\geq 0$.$\square$

Question. A) Do you know if the equation $(1)$ and how get families of solutions of $(1)$ were in the literature? Please, then answer this question as a reference request and I try to search and read those propositions concerning the solutions of the equation $(1)$. B) In other case I would like to know if is it feasible to get such characterization? Can you find different sequences/families of solutions $(x',y')$ of our equation $(1)$? Can you provide us a remarkable computational fact to know what about the different solutions $(x,y)$ of the equation $(1)$? Many thanks.

Thus I understand that neither Claim 1 nor Claim 2 provide us a full characterization of the solutions of $(1)$. As I've said in the first paragraph I would like to know if this equation was in the literature (I've search in OEIS and I believe that there is no an entry about the sequence of $x$ in our pairs $(x,y)$; and I believe that the chain phi(2+phi(x)) isn't showed from the browser of the OEIS), I think that is a nice equation than maybe was studied. I doubt that it is possible to find a full characterization of the solutions of $(1)$, because I think it is a very difficult problem.


[1] Křížek, and Luca and Somer, 17 Lectures on Fermat Numbers, CMS Books in Mathematics Springer-Verlag (2001).

  • 1
    $\begingroup$ With a computer, if you do a loop $x=1,2,3,4,5,\ldots$, you find many cases where $\varphi(2+\varphi(x))$ is a power of two, i.e. solutions to your equation. I agree it looks like that sequence of $x$ is not in OEIS. Terms below $100$ (ignoring the $y \ge 2$ condition) are: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 19, 20, 22, 23, 24, 27, 29, 30, 31, 38, 46, 47, 51, 54, 58, 59, 62, 64, 67, 68, 79, 80, 94, 96 $\endgroup$ – Jeppe Stig Nielsen Feb 4 '18 at 14:39
  • 1
    $\begingroup$ The number of solutions (still with $y$ any integer) with $x<10^8$ is $371$. The last two of these are $98251370$ and $98252840$. $\endgroup$ – Jeppe Stig Nielsen Feb 4 '18 at 15:18
  • $\begingroup$ Many thanks for this great help, since I've calculated the first few terms, it is a surprise to me that there are only 371 soutions when $x$ runs over the segment $[1,10^8]$. Many thanks for your attention one more time @JeppeStigNielsen $\endgroup$ – user243301 Feb 4 '18 at 17:43
  • 1
    $\begingroup$ @user243301: there are just $27$ powers of $2$ in the interval $[1,10^8]$ and the function $\varphi(n)$ is, loosely speaking, weakly contractive, so it does not look so surprising to me. $\endgroup$ – Jack D'Aurizio Feb 4 '18 at 19:21
  • 1
    $\begingroup$ For $x<10^9$ the count of solutions is $426$. $\endgroup$ – Jeppe Stig Nielsen Feb 5 '18 at 22:19

Your Answer

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