How do you write a program to solve the problem that each Fibonacci number can be represented as the sum of three not necessarily different Fibonacci numbers?

Answer 1

You don't actually need a program to prove this. Fib[n] is the sum of Fib[n-1] and Fib[n-2]. it therefore follows that Fib[n-2] must be the sum of Fib[n-3] and Fib[n-4]. That being the case, it stands to reason that Fib[n] must be the sum of Fib[n-1], Fib[n-3] and Fib[n-4].

The "not necessarily different" part of the problem is only required to cater for the first part of the sequence where either Fib[n-1], Fib[n-3] or Fib[n-4] do not exist. E.g.,:

0 = 0+0+0

1 = 1+0+0

2 = 1+1+0 or 2+0+0

3 = 1+1+1 or 2+1+0 or 3+0+0

5 = 2+2+1 or 3+1+1 or 3+2+0 or 5+0+0

From there onwards, there is always at least one solution where all three numbers are different and greater than zero. Note that every Fibonacci is the sum of itself, zero and zero, so there is always at least one solution for every Fibonacci number.

int main (void)

{

/* Fact: there are only 44 Fibonacci numbers in the range 0:1,000,000,000 */

const int max=44;

int fib[max];

int index;

/*

Note: the sequence begins 0, 1, 1, 2, 3, 5...

The value 1 appears twice so we'll begin the

sequence there and then replace the first 1

with a 0.

*/

fib[0]=1;

fib[1]=1;

index=2;

while (index<max) {

fib[index]=fib[index-1]+fib[index-2];

++index;

}

fib[0]=0;

/* Test each Fibonacci... */

for (index=0; index<max; ++index) {

bool found = false; /* Toggle this when we find a solution */

int a, b, c;

for (a=0; a<max; ++a)

for (b=0; b<max; ++b)

for (c=0; c<max; ++c)

if (fib[index]==fib[a]+fib[b]+fib[c]) {

found = true;

printf ("%d = %d + %d + %d\n", fib[index], fib[a], fib[b], fib[c]);

}

if (!found) {

printf ("I'm too stupid to solve this problem!\n");

return -1;

}

}

return 0;

}