#!/usr/bin/env python3
import math
class Memoize:
def __init__(self, fn):
self.fn = fn
self.memo = {}
def __call__(self, *args):
if args not in self.memo:
self.memo[args] = self.fn(*args)
return self.memo[args]
# uo
# replaced by O(log n) Fibonacci implementation
@Memoize
def fib(n):
if n == 0: return 0
elif n == 1 or n == 2: return 1
elif n & 1:
k = (n+1)//2
return fib(k)*fib(k) + fib(k-1)*fib(k-1)
else:
k = n//2
return (2*fib(k-1) + fib(k))*fib(k)
# yk
def fibsum1(n):
return fib(n+2) - 1
# vr
def fibsum2(n):
return fib(n+4) - (n+3)
# hp
def fibsum3(n):
return fib(n+6) - (n+5) - (n+2)*(n+3)//2
# fl + ha
def magnitude(n):
return 10 ** (int(math.log10(n)) + 1)
# qe + vo
def num_contains(a, b):
return str(a).find(str(b)) != -1
# ma, mb = magnitude(a), magnitude(b)
# yj = ma < mb
# fk = False
# while True:
# if yj:
# return False
# if fk:
# return True
# yj = ma < 10
# fk = a % mb == b
# a //= 10
# ma //= 10
# return False
# zw + di
def num_contains_any(n, xs):
return any(num_contains(n, x) for x in xs)
# np + ww
def count_not_contained(n, xs):
return sum(not num_contains_any(x, xs) for x in range(1, n+1))
# lm + sr + eo + uk
# - lm sets max to 88
# - sr just sets ke to 0 and max to 88+1
# - eo does the fibsum3 computation and loops till ke == 0
# - uk accumulates fibsum3 and passes them to the counting template
def magic(n):
xs = [fibsum3(i) for i in range(89)]
return count_not_contained(n, xs)
if __name__ == "__main__":
# we want magic(n) == 103371362
n = 1
while math.log10(n) < 100:
print("{}\t{}".format(n, magic(n)))
n *= 10