19th Phibonacci number

Number Theory Level 3

Let $n_{1}<n_{2}<n_{3}< ...$ be solutions to the equation: $\phi(n)=\phi(n-1)+\phi(n-2)$

where $\phi(n)$ is Euler's Totient Function .

Find $n_{19}$ .

The answer is 2017.

2 solutions

Maria Kozlowska
Jan 8, 2017

OEIS Sequence A065557 provides the answer.

I had a hunch the answer would be $2017$ . :)

I initially wondered if all such $n$ would be prime, but as we go up the list $1037$ and $1541$ are composite, and it is noted in the OEIS link that the incidence of composites increases as the list goes on. It's also curious that all known Fermat primes are in this list.

Brian Charlesworth - 4 years, 5 months ago

Is this solvable by hand? I find solving it manually a huge pain (and waste of time).

Pi Han Goh - 4 years, 5 months ago

Yuriy Kazakov
Oct 23, 2020

from math import gcd

def phi(n):
    amount = 0        
    for k in range(1, n + 1):
        if gcd(n, k) == 1:
            amount += 1
    return amount
s=0
n=2
q0=phi(1)
q1=phi(2)
for k in range(3,10000):
  n=n+1
  q=phi(k)
  r=q-q0-q1
  if r==0: 
    s=s+1
    print(s,n,q,q0,q1)
  q0=q1
  q1=q

1 3 2 1 1
2 5 4 2 2
3 7 6 4 2
4 11 10 6 4
5 17 16 8 8
6 23 22 12 10
7 37 36 24 12
8 41 40 24 16
9 47 46 24 22
10 101 100 60 40
11 137 136 72 64
12 233 232 120 112
13 257 256 128 128
14 857 856 432 424
15 1037 960 528 432
16 1297 1296 864 432
17 1541 1452 972 480
18 1601 1600 960 640
19 2017 2016 1440 576
20 4337 4336 2176 2160
21 6527 6360 3360 3000
22 9179 8976 4752 4224

19th Phibonacci number

The answer is 2017.

2 solutions

0 pending reports