59 lines
1.8 KiB
Python
59 lines
1.8 KiB
Python
#! /usr/bin/env python3
|
||
|
||
# The Fibonacci sequence is defined by the recurrence relation:
|
||
#
|
||
# F_n = F_n−1 + F_n−2, where F_1 = 1 and F_2 = 1.
|
||
# It turns out that F_541, which contains 113 digits, is the first Fibonacci number for which the last nine digits are 1-9 pandigital
|
||
# (contain all the digits 1 to 9, but not necessarily in order). And F_2749, which contains 575 digits, is the first Fibonacci number
|
||
# for which the first nine digits are 1-9 pandigital.
|
||
#
|
||
# Given that F_k is the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital, find k.
|
||
|
||
import sys
|
||
|
||
from mpmath import matrix
|
||
|
||
from projecteuler import is_pandigital, timing
|
||
|
||
|
||
sys.set_int_max_str_digits(70000)
|
||
|
||
|
||
@timing
|
||
def p104():
|
||
found = 0
|
||
fib1 = 1
|
||
fib2 = 1
|
||
i = 2
|
||
|
||
while not found:
|
||
# Calculate the next Fibonacci number modulo 10^9 and check if the result is 1-9 pandigital.
|
||
fibn = (fib1 + fib2) % 1000000000
|
||
fib1 = fib2
|
||
fib2 = fibn
|
||
i = i + 1
|
||
|
||
# If the last 9 digits of fib_n are pandigital, calculate the ith Fibonacci number using
|
||
# the matrix representation, with sufficient precision so that the at least the first
|
||
# 9 digits are correct (we don't need the whole number. If the first 9 digits are also
|
||
# pandigital, we found the solution.
|
||
if is_pandigital(fibn, 9):
|
||
fib_matrix = matrix(2)
|
||
fib_matrix[0, 0] = 1
|
||
fib_matrix[0, 1] = 1
|
||
fib_matrix[1, 0] = 1
|
||
fib_matrix[1, 1] = 0
|
||
|
||
fib = fib_matrix ** i
|
||
fib = int(fib[0, 1])
|
||
|
||
if is_pandigital(int(str(fib)[:9]), 9):
|
||
found = 1
|
||
|
||
print('Project Euler, Problem 104')
|
||
print(f'Answer: {i}')
|
||
|
||
|
||
if __name__ == '__main__':
|
||
p104()
|