#!/usr/bin/env python
# coding: utf-8
# [Discussions](https://discu.eu/q/https://youtu.be/ea7ljkehyta) about Conway's video.
# Memory allocation is the slowest part. We estimate the upper bound of the length of the nth sequence and preallocate two lists with the needed space and compute the new sequence populating each time the other list.
# In[45]:
def look_and_say(current, new):
prev_d = current[0]
run_len = 0
new_i = 0
for d in current:
if d != prev_d:
new[new_i] = run_len
new[new_i+1] = prev_d
new_i += 2
run_len = 0
prev_d = d
if d == 0:
break
run_len += 1
def estimate_length(times):
λ = 1.30357726903429639125709911215255189073070250465940487575486139062855088785246155712681576686442522555
return λ**times
# In[46]:
times = 50
upper_bound = int(10 * estimate_length(times))
sequence = [0]*upper_bound
sequence[0:10] = [1,1,1,3,1,2,2,1,1,3]
tmp = [0]*upper_bound
for _ in range(times):
look_and_say(sequence, tmp)
sequence, tmp = tmp, sequence
# remove trailing 0s
sequence = sequence[:sequence.index(0)]
len(sequence)