Pages

Last Digit of the Sum of Fibonacci Numbers

Another couple of problems in the same lot of the one previously discussed. Now we have to calculate the last digit of the (full or partial) sum of Fibonacci numbers.

Also these problems are presented in the the edX MOOC Algs200x Algorithmic Design and Techniques by the UC San Diego, week 2, so I suggest you to give them a try and then comparing your solutions with my python scripts.

Last Digit of the Sum of Fibonacci Numbers

Given an integer 𝑛, find the last digit of the sum 𝐹0 + 𝐹1 + · · · + 𝐹𝑛.

Considering that n could be as big as 10^14, the naive solution of summing up all the Fibonacci numbers as long as we calculate them is leading too slowly to the result.

We'd better take notice of the hint about experimenting a bit with small test cases looking if we can extrapolate anything interesting. Actually, after a while I find out that the sum of the first n Fibonacci number is just one shorter than the sum of Fibonacci of n + 2.

Sum of Fib(1) + Fib(2) + ... + Fib(n) = Fib(n+2) - 1

We know that Fib(3) = Fib(2) + Fib(1), we can rewrite it as
Fib(1) = Fib(3) - Fib(2)
Let's do the same for all the subsequent Fibonacci numbers up to n.
Fib(2) = Fib(4) - Fib(3)
Fib(3) = Fib(5) - Fib(4)
...
Fib(n) = Fib(n+2) - Fib(n+1)
If we add up all the elements on the left side we get that the required sum is
Fib(3) - Fib(2) + Fib(4) - Fib(3) + 
Fib(5) - Fib(4) + ... + Fib(n+2) - Fib(n+1)
Considering that Fib(2) is 1, it simplifies to
Fib(n+2) - 1
Another useful consideration is that, since we need just the last digit, we could use the result of the previous exercise and limit our loop following the Pisano period.

Putting all together, this is my solution:
PISANO = 60  # 1


def solution(number):
    if number < 2:
        return number

    number %= PISANO

    results = [1, 1]
    for _ in range(number):  # 2
        results.append((results[-1] + results[-2]) % 10)  # 3

    return (results[-1] - 1) % 10  # 4
1. Instead of giving the result for the requested number, I check the modulo 60, being that the Pisano period for 10. (See below, the part in green, for a clarification on this point)
2. I have initialized the list named 'results' with the values of Fib(1) and Fib(2), now I loop n times, since I am looking for Fib(n+2).
3. I'm not interested in the actual Fibonacci number, just it's last digit, so here I apply modulo 10 to the brand new calculated one. In this way I avoid scaling to big numbers.
4. I apply the modulo operator once again to get rid of the unfortunate case of possibly negative results.

Naive, Pisano script, and test case for both, are on GitHub.

Last Digit of the Partial Sum of Fibonacci Numbers

Given two non-negative integers π‘š and 𝑛, where π‘š ≤ 𝑛, find the last digit of the sum πΉπ‘š + πΉπ‘š+1 + ... + 𝐹𝑛.

The trick used in the previous problem won't work here, and I couldn't think of any similar clever approach. So I resorted to make full use of Pisano, hoping that it was enough.
PISANO = 60


def solution(left, right):
    assert not left > right  # 1

    fib_mods = [0, 1]  # 2
    for _ in range(PISANO - 2):
        fib_mods.append((fib_mods[-1] + fib_mods[-2]) % 10)

    left %= PISANO  # 3
    right %= PISANO
    if right < left:
        right += PISANO

    result = 0
    for i in range(left, right + 1):
        result += fib_mods[i % PISANO]  # 4
    return result % 10  # 5
1. Not strictly required by the problem, where we can assume the input data is clean.
2. I fill this list with all the Fibonacci number modulo 10 in the range of the Pisano period.
3. I don't need to loop on all the actual requested numbers, I can safely stay in the limit of the Pisano period. With one major caveat, the right limit should not become smaller that left.
4. Loop on the interval, ensuring that I stay in the Pisano limits.
5. Return the last digit of the sum, as required.

Let's try and clarify point 3.

The idea of the algorithm is working with the Pisano period for 10. So instead of calculating all the Fibonacci numbers in the range, adding them up, and finally extract modulo ten from the result, we would work with the small numbers in the Pisano 60 period.

Calculating the Pisano number for any value in [m, n], adding all them up, and the returning its modulo 10 could be already a good solution. However, let's consider the fact that n - m could be huge. It's not a good idea adding up all those numbers, when we could get rid of all the repetition, since they won't be relevant. We could limit them to the bare minimum, looping, in the worst case 60 times.

That's the ratio for considering m and n modulo 60. Still, there is an issue. What if m % 60 is bigger than n % 60.

Say that we want to know the result for m = 57 and n = 123.

58 % 60 is 58, but 123 % 60 is 3. We need to adjust the end value in the loop. Let's add 60 to the right value, now we are sure that it is bigger than left.

Also for this problem I have pushed naive, Pisano script, and test case for both, on GitHub. See the github folder for all the stuff about week 2 exercises.

12 comments:

  1. Actually, after a while I find out that the sum of the first n Fibonacci number is just one shorter than the sum of Fibonacci of n + 2.

    I didn't understand this line?
    Where did you implemented this line?

    ReplyDelete
    Replies
    1. Thank you for asking. I answered to the first point in the post, adding a section (in blue) that I hope makes it more clear.
      For the second point I added a note (now marked as '2') in the code. The idea is that I run the for-loop until I get the modulo of Fibonacci(n+2), so that I just have to decrease it by one to get the expected result.

      Delete
  2. Hey. The only thing that was missing in my code was that you added the pisano period to right when right < left. It worked like a charm after that. Can you explain how adding pisano period to right helps?

    ReplyDelete
    Replies
    1. Hi, thank you for asking. I added a section in the post (in green) that I hope would clarify the point. Please let me know if it didn't work as I expected.

      Delete
  3. This comment has been removed by the author.

    ReplyDelete
  4. Great post, thanks for that!
    I'm missing the logical connection in step 1 of the first solution ... how did you arrive to the idea to use Pisano period for 10 ... ? Not 20 or 15 ...

    ReplyDelete
    Replies
    1. Thank you for your feedback and question. I guess the addendum in green is not enough clear - I'll rework it. In brief, the Pisano gives a way of identifying the last digit of Fibonacci in a stated base. So, since we are usually interested in base 10, we use Pisano(10). Hence we check the 60 module, because that is its period.

      Delete
    2. It does not work for range 100-200

      Delete
    3. What do you mean, Anonymous? Could you please provide an example?

      Delete
  5. This is awesomeee! You did a great job

    ReplyDelete