<jupyter_start><jupyter_text>Question: The 7th Fibonacci number is 13, and its last digit is 3. What is the last digit of the 7777th Fibonacci number?  TL;DR: 7  Starting from ground zero... If we don't care about time and space complexity, this is a very easy question. We could just run a brute force algorithm: iteratively construct a list of the first 7777 numbers in the sequence, then return the last digit of the final element. This will be O(n) in time and space. This is an incredibly crude solution, but let's begin here as a starting point.Sidenote: it's sometimes ambiguous whether the Fibonacci sequence starts with 0 or 1, and for the purposes of this question, we need a definitive answer! Luckily, we're told in the problem statement that the 7th Fibonacci number is 13, so we can deduce that the sequence here starts with 1.  Simple ways to improve the algorithm... Firstly, we don't actually need to store every successive element. All we need to construct the next number is the two previous ones, so we just need two variables to keep track of this, not an entire list.Furthermore, we don't need to store the entire number either, just the last digit. Everything else is irrelevant to the question we're trying to answer. The last digit of a Fibonacci number only depends on the last digit of the two prior numbers - nothing else. Since the Fibonacci numbers grow roughly by a factor of 1.618 (The Golden Ratio), storing the entire number would actually be problematic for very large N.If we incorporate these improvements, we can really clean up the code and, more importantly, achieve constant space complexity. The algorithm is still O(n) in time, but 7777 is small enough where we'll be able to compute the answer.  Code for O(n) time, O(1) space<jupyter_code># returns the last digit of the Nth Fibonacci number, with the sequence beginning 1, 1 ...
def last_digit_a(N):
    # a = two previous, b = one previous
    a = 0
    b = 1
    for _ in range(N):
        a, b = b, (a+b)%10
    return a<jupyter_output><empty_output><jupyter_text>We can do a quick check with N=7, and we expect 3 (7th Fibonacci number is 13). We'll do more rigourous testing with this at the end of the notebook - don't worry.<jupyter_code>last_digit_a(7)<jupyter_output><empty_output><jupyter_text>Nice! Let's figure out what the 7777th Fibonacci number ends with.<jupyter_code>last_digit_a(7777)<jupyter_output><empty_output><jupyter_text>OK, so we have our answer. The last digit of the 7777th Fibonacci number is 7 - good enough, right!? Well, we were lucky here since we were only asked to compute the result for N=7777. But what if N was a lot bigger? What if we wanted to compute the result for the 10 quadrillionth Fibonacci number? O(n) time complexity won't suffice, we need to be better. But how? How can we arrive at the digit of the Nth number without calculating the intermediary results for every Fibonacci number in between? When I saw this problem, I was instantly reminded of an algorithm problem I solved in the past on LeetCode called "Prison Cells after N Days" - link [here](https://leetcode.com/problems/prison-cells-after-n-days/). A few months ago, I actually created a YouTube video to explain my solution for this problem, as a lot of users were finding it too cryptic and bewildering. You can check that video out [here](https://www.youtube.com/watch?v=-dOYJ_80bjQ).OK, enough shameless plugs. What's the connection? Well, both problems are asking us to find the Nth element of a sequence in constant time. Sounds a bit tough, but what if we knew that this sequence had a cycle? If this sequence began repeating itself, would we actually need to spend valuable time going through the cycle again and again and again? Turns out, if we use some sneaky hashing and modular math, we can determine the Nth value in the sequence **immediately** after we figure out that we're trapped in a cycle.This sounds OK, but how do we prove that this sequence will fall into a cycle? Lot's of sequences don't. Let's reformulate the sequence to be the following:Old Sequence (last digit of Fib numbers):`1123583 (from 13)1 (from 21)4 (from 34)5 (from 55)9 (from 89)4 (from 144)3 (from 233)...`New Sequence (last digit of Fib number and last digit of next Fib number):`(1, 1)(1, 2)(2, 3)(3, 5)(5, 8)(8, 3)(3, 1)(1, 4)(4, 5)(5, 9)(9, 4)(4, 3)...`Note that elements in our sequence are now 2-dimensional vectors, instead of scalars. You're probably wondering why we're introducing all this complicated math ... what's the point of all this?Look again at the new sequence. Two key observations:- Each element can only assume a finite number of states. We could list out all possibilities that an element in this sequence could assume.- Each element depends **only** on the prior element. If a given element is `(a,b)` the next element will be `(b, (a+b)%10)`. This is huge.This two properties combine to yield the following powerful result: this process is **cyclic**.  But how can we leverage this to get O(1) time? Crude outline of the algorithm:- record each element (2D vector) in an ordered list- use a hashmap to connect each element we've seen to *the location where we first saw it*- if we get to an element that already exists in our hashmap, spit out the answer using `cycle_start_index + remaining_steps % cycle_length` as the index for the ordered listNote that both the list and hashmap are O(1) since there are a only a finite number of possible elements to store. The memory that these can consume is bounded and is thus O(1).  Code for O(1) time, O(1) space ... very spicy<jupyter_code># returns the last digit of the Nth Fibonacci number, with the sequence beginning 1, 1 ...
def last_digit_b(N):
    
    # seed for the sequence
    seq = [0, 1]
    
    # key   : (last digit of fib(n), last digit of fib(n+1))
    # value : n
    position = {}
    
    # list of all the states we see, ordered by when we see them
    history = []

    for i in range(N):
        a, b = seq
        key = (a, b) # convert to immutable type (tuple) so it's hashable
        if key in position:
            cycle_start = position[key]
            cycle_length = i - cycle_start
            index = cycle_start + (N-i)%cycle_length
            return history[index]
        position[key] = i
        history.append(a)
        seq = [b%10, (a+b)%10]
        i += 1
    
    # happens if we get to the Nth element before we hit a cycle
    return seq[0]%10
    # might happen if N<100 (100 possible states)<jupyter_output><empty_output><jupyter_text>Let's verify that this algorithm works properly... To verify that this algorithm gives correct answers (and the first one we developed), let's build a crude (but dependable) algorithm that we can use to easily check answers for N <= 300.<jupyter_code>fibonacci = [0, 1]
for _ in range(300):
    fibonacci.append(fibonacci[-2] + fibonacci[-1])
# pardon the English
for N in range(1, 12):
    print(f'{N}-th Fib number is {fibonacci[N]}')
# values to test
test_input = [1, 2, 3, 4, 5, 6, 100, 131, 170, 221, 227, 250, 254, 255, 266, 290]
errors = 0

for ti in test_input:
    actual = fibonacci[ti]%10
    alg_a = last_digit_a(ti)
    alg_b = last_digit_b(ti)
    if actual != alg_a:
        print(f'Alg A error with input {ti} ... Actual: {actual}, Output: {alg_a}')
        errors += 1
    if actual != alg_b:
        print(f'Alg B error with input {ti} ... Actual: {actual}, Output: {alg_b}')
        errors += 1

if errors == 0:
    print('All good boss.')<jupyter_output>All good boss.<jupyter_text>Checking that we get the same value for N=7777.<jupyter_code>last_digit_b(7777)<jupyter_output><empty_output><jupyter_text>Yup.  Flexing the new algorithm because we can If anyone ever asks you what the last digit of the 239457293847572938475792384573984573948573948572943875th Fibonacci number is ...<jupyter_code>last_digit_b(239457293847572938475792384573984573948573948572943875)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.07616060225846925, 'fraction_numerical': 0.039272271016311165, 'mean_word_length': 3.929499072356215, 'pattern_counts': {'":': 0, '<': 30, '<?xml version=': 0, '>': 28, 'https://': 2, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '561328', 'license': 'Unlicense', 'n_tokens_mistral': 2569, 'n_tokens_neox': 2258, 'n_words': 1174, 'path': 'last-digit-of-nth-fibonacci-number.ipynb', 'repo_name': 'cjporteo/last-digit-of-nth-fibonacci-number', 'size': '7970'}