p104.py 961 Bytes
Newer Older
1 2
# 
# Solution to Project Euler problem 104
3
# Copyright (c) Project Nayuki. All rights reserved.
4
# 
5
# https://www.nayuki.io/page/project-euler-solutions
6 7 8
# https://github.com/nayuki/Project-Euler-solutions
# 

9 10
import itertools

11 12 13 14 15

def compute():
	MOD = 10**9
	a = 0
	b = 1
16 17 18 19 20 21
	for i in itertools.count():
		# Loop invariants: a == fib(i) % MOD, b == fib(i+1) % MOD
		if "".join(sorted(str(a))) == "123456789":  # If suffix is pandigital
			f = fibonacci(i)[0]
			if "".join(sorted(str(f)[ : 9])) == "123456789":  # If prefix is pandigital
				return str(i)
22 23 24 25
		a, b = b, (a + b) % MOD
	return str(ans)


26
# Returns the tuple (F(n), F(n+1)), computed by the fast doubling method.
27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
def fibonacci(n):
    if n == 0:
        return (0, 1)
    else:
        a, b = fibonacci(n // 2)
        c = a * (b * 2 - a)
        d = a * a + b * b
        if n % 2 == 0:
            return (c, d)
        else:
            return (d, c + d)


if __name__ == "__main__":
	print(compute())