Here's what I get for the first 20 Fibonacci numbers we can say that these are the first 20 Fibonacci numbers, "mod 11". But we don't have to understand how everything is put together before we use it. This program at the right actually has a creepy issue with it. I'd like to compose a piece of music based on the Fibonacci numbers, but I can see already that the numbers "grow" too quickly.
Now the sequence is 1, 1, 2. That said, I think we can agree that pylint is wrong here, and even the name n fails it. But now we can apply exponentiation by squaring with matrices rather than numbers to get a faster solution. Play That Fibonacci Music The reason we get some buggy numbers is that operating with floating point numbers is tricky when what we want are integer remainders.
Modular Arithmetic First, let me start by being able to generate any Fibonacci number that I want, rather than having to look up the numbers in a list. Even further speed can be gained if you use the "fast doubling" recurrence shown here.
What remainder should be displayed for each of the numbers in Question 3? It also has the advantage of never causing stack overflows and using a constant amount of memory.
So, now I can use the same methodology I started writing music with to produce something of a little greater length. What is the next number in the sequence?