p104.py 961 Bytes
 1 2 ``````# # Solution to Project Euler problem 104 `````` Nayuki committed Dec 27, 2016 3 ``````# Copyright (c) Project Nayuki. All rights reserved. `````` 4 ``````# `````` Nayuki Minase committed Feb 05, 2016 5 ``````# https://www.nayuki.io/page/project-euler-solutions `````` 6 7 8 ``````# https://github.com/nayuki/Project-Euler-solutions # `````` Nayuki Minase committed Aug 13, 2015 9 10 ``````import itertools `````` 11 12 13 14 15 `````` def compute(): MOD = 10**9 a = 0 b = 1 `````` Nayuki Minase committed Aug 13, 2015 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) `````` Nayuki Minase committed Aug 13, 2015 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())``````