Just add five

Number Theory Level 3

$F_n$ are the Fibonacci numbers, $0,1,1,2,3,5,8,13,...$ where $F_0=0, F_1=1$ , and $F_n = F_{n-1} + F_{n-2}$ for $n>1$ .

How many positive integers can't be represented by $F_n + 5m$ with the appropriate choice of non-negative integers $m$ and $n$ ?

If you think the answer is "an infinite number" put -1 as your answer.

Inspiration

The answer is 6.

2 solutions

Geoff Pilling
Dec 28, 2018

As soon as you find a number that has a certain value modulo 5, all successive numbers with that same value (modulo 5) can be formed. Since the first few Fibonacci numbers are 0, 1, 2, and 3 modulo 5, the only numbers you can't make will be 4 (modulo 5).

The first Fibonacci number that is 4 (modulo 5) is 34.

Therefore, the only numbers that can't be represented are 4, 9, 14, 19, 24, and 29.

Interesting. If $N(k)$ represents the number of positive integers that can't be represented by $F_{n} + km$ for some non-negative integers $m,n$ then $N(4) = 0, N(5) = 6, N(6) = 5, N(7) = 21, N(8) = \infty, N(9) = 113, N(10) = 1093, N(11) = \infty, N(12) = \infty, N(13) = \infty$ . $N(14)$ and $N(15)$ are finite, but $N(16)$ is infinite. Suffice it to say I'm not finding a pattern here, but I am curious as to the cardinality of the set of all $k$ such that $N(k)$ is finite. Huh, you've sent me down the rabbit hole yet again. :)

Brian Charlesworth - 2 years, 5 months ago

Whoa... You've once again succeeded in taking my problem and turning it on it's head. 😂. Interesting indeed that the pattern is so complex. I'll have to think a bit more about the cardinality question.... 🤔 Hmmm...

Geoff Pilling - 2 years, 5 months ago

OEIS to the rescue! . The Burr (1971) paper gives a full proof.

Brian Charlesworth - 2 years, 5 months ago

@Brian Charlesworth – I have learned from this! Thanks!

X X - 2 years, 5 months ago

@Brian Charlesworth – Cool... Will take a look when I get a chance...

Geoff Pilling - 2 years, 5 months ago

@Brian Charlesworth – The FORMULA given is so unexpected.

Jeremy Galvagni - 2 years, 5 months ago

Yuriy Kazakov
Oct 23, 2020

s = set()
s0 = {k for k in range(120)}
f = [0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

for k in range(2, 26):
    f[k] = f[k - 1] + f[k - 2]
for m in f:
    for w in range(0, 30):
        s.add(m + w * 5)

dd = set(s)
print('max', max(dd), s0 - dd, 'length', len(s0 - dd))

max 75170
 {4, 9, 14, 19, 24, 29} 
length 6

Just add five

The answer is 6.

2 solutions

0 pending reports