In [1]:
# The Fibonacci sequence we'll be using is: [0,1,1,2,3,5,8...], and so the numbering is fib(3) == 2
def fib(n):
    if n <= 1:
        return n
    current = 1
    previous = 0
    for i in range(2,n+1):
        temp = previous + current
        previous = current
        current = temp
    return temp
In [8]:
print(fib(1000))

43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
In [5]:
def fibSeq(n):
    if n == 0:
        return [0]
    if n == 1:
        return [0,1]
    
    current = [0,1]
    for i in range(2,n+1):
        current += [current[-1] + current[-2]]
    return current
In [10]:
print(fibSeq(10))

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
In [11]:
# Hailstone (Collatz Conjecture)
def Hailstone(seed):
    answer = [seed]
    while seed != 1:
        if seed % 2 == 0:
            seed //= 2
        else:
            seed = 3 * seed + 1
        answer += [seed]
    return answer
In [27]:
Hailstone(6)
Out[27]:
[6, 3, 10, 5, 16, 8, 4, 2, 1]
In [22]:
# a helper function that just calculates the length of the hailstone sequence starting from seed
def HailstoneCount(seed):
    length = 1
    while seed != 1:
        if seed % 2 == 0:
            seed //= 2
        else:
            seed = 3 *seed + 1
        length += 1
    return length

def HailstoneSummary(low,high):
    max_length = HailstoneCount(low)
    max_seed = low
    for trial in range(low+1,high+1):
        trial_length = HailstoneCount(trial)
        if trial_length > max_length:
            max_length = trial_length
            max_seed = trial
    return [max_seed,max_length]
In [23]:
HailstoneSummary(3,100)
Out[23]:
[97, 119]
In [36]:
# Challenge problem.  We'll do it 2 ways and time the results: 
# 1) the straightforward way using the HailstoneSummary(3,1000000) above.
# 2) adding Nora Miller's speedup ideas of saving all of the Lengths for all calculated seeds so far
import time
start1 = time.time()
print('First version: ',HailstoneSummary(3,1000000))
end1 = time.time()
print('Elapsed time in secs: ',(end1-start1))

def HailstoneSummaryNora(low, high):
    all_seeds = [0] * (high+1)
    first = HailstoneCount(low)
    all_seeds[low] = first
    max_length = first
    max_seed = low
    
    for seed in range(low+1,high+1):
        # fast counter with shortcut if we've found a stored length from a previous seed
        length = 1
        trial = seed
        found = False
        while trial != 1:
            if trial % 2 == 0:
                trial //= 2
            else:
                trial = 3 * trial + 1
            if trial <= high and all_seeds[trial] > 0:
                length = length + all_seeds[trial]
                break
            length += 1
        all_seeds[seed] = length
        if length > max_length:
            max_length = length
            max_seed = seed
        
    return [max_seed,max_length]

print('Second version: ', HailstoneSummaryNora(3,1000000))
print('Elapsed time in secs: ', (time.time() - end1))
                
    

First version:  [837799, 525]
Elapsed time in secs:  22.102885723114014
Second version:  [837799, 525]
Elapsed time in secs:  1.5458648204803467
In [ ]: