Problems & Puzzles: Puzzles

 Puzzle 1010. 21 is a Fibonacci number special... G.L. Honaker Jr. made me notice one of his curios: "The only known Fibonacci number that is the sum of exactly three distinct Fibonacci primes, i.e., 21 = 3 + 5 + 13. Does another one exist? [Honaker]" According to W1 and W2 there are 34 prime-Fibonacci integers currently known. So the Honaker's question means to test all these 5984 combinations of trios from an universe of 34, to detect if one of these 5456 sums S is a Fibonacci number. For sure you know also that S is a Fibonacci integer if at least one of these, 5S^2+/-4, is a perfect square. Q. Send your results.

Contributions came from Oscar Volpatti and Emmanuel Vantieghem.

***

Oscar wrote:

There can't be another Fibonacci number like 21.
I'll prove the following slightly more general statement:

The Fibonacci numbers 5, 8, and 21 are the only ones which can be written as the sum of exactly three positive, non-composite Fibonacci numbers with distinct indexes.

The claimed sums are:

5 = 3+1+1;
8 = 5+2+1;
21 = 13+5+3.

As the number 1 is no more considered a prime, only last sum involves three primes.

Note that 1 can be used twice without contradicting my statement because it appears twice in the Fibonacci sequence, at indexes 1 and 2.

For the proof, I will use two known properties of Fibonacci numbers.

Recurrence relation: F(n) = F(n-1) + F(n-2).

Strong divisibility: gcd(F(m),F(n)) = F(gcd(m,n)).

Step 1.

A Fibonacci number F(n) with n >= 5 can be written in only one way as the sum
of exactly three positive Fibonacci numbers with distinct indexes:
F(n) = F(n-1) + F(n-3) + F(n-4).

Proof, using the recurrence relation.
F(n) = F(n-1) + F(n-2) < F(n-1) + F(n-2) + F(1), so the sum can't use both F(n-1) and F(n-2).

F(n) = F(n-1) + (F(n-3)+F(n-4)) > F(n-2) + (F(n-3)+F(n-4)), so the sum must use F(n-1), and it can't use F(n-2).

F(n) = F(n-1) + F(n-3) + F(n-4) > F(n-1) + F(n-4) + F(n-5),  so the sum must use F(n-3) too.

Then last term must be F(n) - F(n-1) - F(n-3) = F(n-4).

Step 2.

The sequence R(n) = F(n) mod 4 is periodic, with period 6.
R(0) = F(0) = 0 and R(1) = F(1) = 1; by applying the recurrence relation:
0,1,1,2,3,1,0,1,1,2,3,1,...

Let us check the six possible triplets F(n-1), F(n-3), F(n-4)  mod 4.
The first column lists n mod 6.

| 0 || 1 | 2 | 1 |
| 1 || 0 | 3 | 2 |
| 2 || 1 | 1 | 3 |
| 3 || 1 | 0 | 1 |
| 4 || 2 | 1 | 0 |
| 5 || 3 | 1 | 1 |

If n is congruent to 1, 3 or 4 mod 6, one term of the sum is zero or a composite multiple of 4.
If n is congruent to 0 mod 6, then F(n-3) is an odd multiple of 2 and is composite, unless F(n-3) = 2; equality holds only for n = 6.
If n is congruent to 2 mod 6, then n = 6*k+8; by the strong divisibility property, the number F(n-4) = F(6*k+4) is divisible by the smaller number F(3*k+2) and is composite, unless F(3*k+2) = 1; equality holds only for k = 0, so n = 8.
If n is congruent to 5 mod 6, then n = 6*k+5; again, the number F(n-1) = F(6*k+4) is composite, unless k = 0; so n = 5.

Therefore, the only candidates are F(5) = 5, F(6) = 8, and F(8) = 21.
For each candidate, the only possible sum is the one listed above, which actually involves no composites, as claimed.

***

Emmanuel wrote:

There are no other such sums !

Indeed, let  F(n) denote the nth Fibonacci number.

Suppose we have  3 < a < b < c  and  F(a) + F(b) + F(c) = F(d).
Then we must have  c = d - 1.
Indeed, c <= d - 2  would imply :
F(a) + F(b) + F(c) <= F(c-2) + F(c-1) + F(c)
F(d)            <= F(d-4) + F(d-3) + F(d-2)
<= F(d-4) + F(d-1) < F(d-2) + F(d-1) = F(d),
Impossible.

Thus, F(a) + F(b) + F(d-1) = F(d)
which implies that  F(a) + F(b)  must be equal to  F(d-2),
which is only possible when  a = d-4  and  b = d-3.

The only cases in which two consecutive Fibonacci number are both prime are :
2 and 3 (but this is not giving a solution)
3 and 4 which give the solution  3 + 5 + 13 = 21.

***

 Records   |  Conjectures  |  Problems  |  Puzzles