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.

***