# PPaste!

### someta1

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81``` ```#!/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 ```