# Euler $\phi(x)$ function

Euler $\phi(x)$ function. Are there infinitely many solutions $n$ to this equation:

$$\phi(n)=\phi(n-1)+\phi(n-2)?$$

Here the vector of the $n's$ prime (source OEIS): [3, 5, 7, 11, 17, 23, 37, 41, 47, 101, 137, 233, 257, 857, 1297, 1601, 2017, 4337, 14401, 16097, 30497, 62801, 65537, 77617, 686737, 18800897, 255080417, 12885295097, 12918324737, 96052225601, 516392008697, 7026644072737]

• Looks like Fibonacci. – badjohn May 14 at 12:11
• This has nothing to do with Fibonacci, it's about consecutive values of the Euler totient function. – Teddy38 May 14 at 12:28
• So we have $\phi(1)=1$, $\phi(2)=1$, $\phi(3)=2$, $\phi(4)=2$, $\phi(5)=4$, $\phi(6)=2$, $\phi(7)=6$, $\phi(8)=4$, $\phi(9)=6$, $\phi(10)=4$ etc. You can already spot a few solutions here. However, the question asks whether there are infinitely many such solutions. Nothing to do with fibonacci. – Teddy38 May 14 at 12:30
• @MeesdeVries $1037 = 17 \cdot 61$. – Michael Biro May 14 at 12:48
• Thanks for that catch! That'll teach me... let me amend my statement to "with $n$ usually prime, seemingly biased towards having fewer factors". – Mees de Vries May 14 at 12:50

I've seen these called Phibonacci numbers. This paper talks about bounding their asymptotic density so presumably there are infinitely many, but I am not familiar with a proof.

They are A065557.

I suggest to start with $n=3$ because the definition of $\phi(0)$ might be problematic. If we assume $\phi(0)=0$ however, $n=2$ is a solution as well. Starting with $n=3$, the number of solutions below $10^k$ is :

? for(k=1,7,print(k,"   ",length(select(m->eulerphi(m)==eulerphi(m-1)+eulerphi(m
-2),[2..10^k]))))
1   3
2   9
3   14
4   22
5   31
6   39
7   47
?


With the additional condition that $n$ is composite, the count is as follows :

? for(k=1,7,print(k,"   ",length(select(m->(eulerphi(m)==eulerphi(m-1)+eulerphi(
m-2))*(ispseudoprime(m)==0),[2..10^k]))))
1   0
2   0
3   0
4   4
5   7
6   14
7   22
?


The smallest solution exceeding $10^k$ is :

? for(k=1,7,n=10^k;while(eulerphi(n)<>eulerphi(n-1)+eulerphi(n-2),n=n+1);print(k
,"   ",n))
1   11
2   101
3   1037
4   14401
5   110177
6   1876727
7   10076627
?


Apparently all solutions (besides $n=2$) are odd. Maybe this can be proven.

• PARI/GP considers $\phi(0)=2$, which is strange. $$116\ 781\ 757$$ is the smallest solution exceeding $10^8$. – Peter May 14 at 16:39
• The smallest solution exceeding $10^9$ is $$1\ 267\ 578\ 227$$ – Peter May 14 at 17:21
• The smallest solution exceeding $10^{10}$ is $$10\ 250\ 728\ 121$$ – Peter May 14 at 19:53