CODEWITHSUNDEEP
algorithmfibonacci
Stanley Yu
Stanley Yu

Reputation: 109

How to use the Pisano Period to find the Last Digit of the Sum of Fibonacci Numbers?

I'm taking an online algorithms course, and I've come across a problem where I need to find the last digit of the sum of the Fibonacci numbers up the nth (current) number.

I need some help connecting the dots. As I understand it, the "Last Digit of the Sum of Fibonacci Numbers" problem has a solution that is somehow related to the Pisano Period.

But I don't really understand what that means.

The Pisano Period was used to calculate the remainder given some value of m for an extremely large Fibonacci Number, which was the focus of a prior problem (I.E., Solve Fn mod m = ???).

Forum posts (and the instruction set) seem to suggest that the length can somehow help us quickly zero in on the sum for the current Fibonacci without having to actually build up to it normally through a loop.

I would rather avoid just looking at someone else's solution if possible, so if anyone has any useful hints that can help me see the missing link, I would really appreciate it.

Upvotes: 3

Views: 808

Answers (1)

Dillon Davis
Dillon Davis

Reputation: 7750

The last digit of a Fibonacci number is just that number reduced modulo 10. Pisaso periods are the periods of which the sequence of fibonacci numbers, modulo some base, repeat. So, if you're interested in F(x) mod 10, you'd interested in the Pisaso Period p(10).

If we have this period, say it was something like [1, 5, 2, 7, 0] (its not, but for sake of example), we'd know that the 3rd integer in the sequence ended with a "2". And because it repeats, we'd know the 8th integer also ends in a "2", and the 13th...

Generalizing this, we could say that the last digit of the number N could be found at the ith index in our list we just built, for i satisfying N = 5 * k + i, where k is just any integer, and 5 comes from the fact that our list has 5 elements (and thus repeats every 5 values). Rewriting this, we could say i = N mod 5.

Putting that all together (spoilers), we just need to find the actual values of the repeating sequence mod 10, and then take our input value N (for finding the Nth Fibonacci number mod 10), and index into said repeatingSequence at index N mod len(repeatingSequence) for our answer.

For reference, for base 10, the actual repeating sequence is:

011235831459437077415617853819099875279651673033695493257291

Upvotes: 5

Related Questions