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]

  • 3
    Looks like Fibonacci. – badjohn May 14 at 12:11
  • 3
    This has nothing to do with Fibonacci, it's about consecutive values of the Euler totient function. – Teddy38 May 14 at 12:28
  • 3
    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
  • 2
    @MeesdeVries $1037 = 17 \cdot 61$. – Michael Biro May 14 at 12:48
  • 2
    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.

  • 1
    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
  • 1
    The smallest solution exceeding $10^9$ is $$1\ 267\ 578\ 227$$ – Peter May 14 at 17:21
  • 1
    The smallest solution exceeding $10^{10}$ is $$10\ 250\ 728\ 121$$ – Peter May 14 at 19:53

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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