Project Euler Forum

I am not sure I understand the SUM from i=2 to k.

In the example S(3), how is 3 used to only look at (1,1) (1,2) (2,1) (2,2) ?

The sum is evaluated over pairs (f_i, f_j) of Fibonacci numbers. The example S(3) is like that because f_2 = 1 and f_3 = 2.

Thanks. I missed that.

Now I just have to figure out why my S(5) gives me 10,407 instead of 10,396.

I presume A(0,j) where j>1 = 0 as there's no way of finding those values.

Yes?

KING-OLE wrote: Mon Apr 14, 2025 7:49 pm I presume A(0,j) where j>1 = 0 as there's no way of finding those values.

That is not correct. A(0, n) is undefined if n is not 0 or 1. You can't assume any value for it. If you need it to be zero, you've probably gone wrong somewhere.

So, how would you find A(1,3)?

Using first formula: A(1,3) = A(0,4) + A(0,3). Both A(0,4) and A(0,3) are unspecified.

Using second one: A(1,3) = 2A(1,2) + A(0,2). A(0,2) is unspecified.

What am I missing?

DJohn wrote: Mon Apr 14, 2025 8:41 pm

KING-OLE wrote: Mon Apr 14, 2025 7:49 pm I presume A(0,j) where j>1 = 0 as there's no way of finding those values.

That is not correct. A(0, n) is undefined if n is not 0 or 1.

"Undefined" is not the correct word to use. It's perfectly well defined, but to determine the value it's necessary to make suitable application of the recurrence relations.

KING-OLE wrote: Mon Apr 14, 2025 10:24 pm So, how would you find A(1,3)?

Build it up bit by bit. Try expanding the recurrence relations for small values of m and n, and then see which ones relate one unknown and two knowns. Then check again to see what you can do with the new known.