Что случилось с моим генератором последовательности Фибоначчи?

Question

Я пытаюсь решить Problem #25 on Project Euler. Вот что у меня до сих пор:

def fibonacci(length): 
    fibs = [0,1] 
    while length > len(fibs): 
     fibs.append(fibs[-1] + fibs[-2])   
    return fibs 

fibs = fibonacci(5000) 

for i in fibs: 
    if len(str(i)) > 1000: 
     print i 

     ## The location of the number in the Fibonacci set. 
     print [j for j, x in enumerate(fibs) if x == i] 

Каждый номер я проверил на (в том числе некоторых large ones) выходит с матчем, но Project Euler не принимает ответ я получаю.

Я прочитал, что ответ является 4782th числа, но я получаю, что первый номер с более чем 1000 цифр является 4787th,

11867216745258291596767088485966669273798582100095758927648586619975930687764095025968215177396570693265703962438125699711941059562545194266075961811883693134762216371218311196004424123489176045121333888565534924242378605373120526670329845322631737678903926970677861161240351447136066048164999599442542656514905088616976279305745609791746515632977790194938965236778055329967326038544356209745856855159058933476416258769264398373862584107011986781891656652294354303384242672408623790331963965457196174228574314820977014549061641307451101774166736940218594168337251710513138183086237827524393177246011800953414994670315197696419455768988692973700193372678236023166645886460311356376355559165284374295661676047742503016358708348137445254264644759334748027290043966390891843744407845769620260120918661264249498568399416752809338209739872047617689422485537053988895817801983866648336679027270843804302586168051835624516823216354234081479331553304809262608491851078404280454207286577699580222132259241827433 

и Проект Эйлер говорит каждый ответ, который я пытался это неправильно. (Очевидно, я еще не пытался 4782, так как это было бы обманом.)

Я дразняще близко, и, очевидно, что-то идет не так, но что?

Answer 1

Вы проверяете len(str(i)) > 1000, когда в соответствии с постановкой задачи вы должны проверять len(str(i)) == 1000.

Кроме того, вы неверно интерпретировали номер в ответе, который вы связывали в качестве числа фибоначчи. Собственно, если вы внимательно прочитаете, это количество раз, когда функция fib вызывается. Ваш фибоначчи номер 4782 верен.

Answer 2

в соответствии с форумом projecteuler для решателей 25-й проблемы, вы правы.

и второе большое число, которое начинается с 1322 ... не является числом фибоначчи.

некоторая функция, чтобы проверить, является ли х число Фибоначчи:

import decimal 
    def check_fib(n): 
     a, b = decimal.Decimal(5*(n**2) + 4), decimal.Decimal(5*(n**2) - 4) 
     return any(int(x.sqrt())==x for x in (a, b)) 

Answer 3

Как сказал thkang, номер ребята неправильный, См. Комментарий wims. Ваш алгоритм работает.

def fibonacci(length): 
    fibs = [0,1] 
    while length > len(fibs): 
     fibs.append(fibs[-1] + fibs[-2])   
    return fibs 

fibs = fibonacci(5000) 
for i,n in enumerate(fibs): 

    if len(str(n)) >= 1000: 
     print i 
     print n 
     break 

Вот что я использовал для решения проблемы, и я получаю те же ответы, что и вы.

def fib(): 
    x, y = 0, 1 
    while True: 
     yield x 
     x += y 
     x, y = y, x 
f = fib() 
for i,n in enumerate(f): 
    if len(str(n)) >= 1000: 
     print i 
     print n 
     break 

Answer 4

В дополнение к этому вопросу (и проблемы), вы можете использовать функцию Генерирование Functionology Fibonnaci, чтобы получить номера fibonnaci прямым способом.

from decimal import Decimal 
from math import sqrt 

#sqrt_5 = Decimal(sqrt(5)) 
sqrt_5 = decimal.Decimal(5).sqrt() # As thkang suggested! 
fib = lambda n: (1/sqrt_5)*((2/(-1+ sqrt_5))**(n+1) - (2/(-1-sqrt_5))**(n+1)) 

for i in xrange(10000): 
    if fib(i).adjusted()+1 == 1000: 
     print i+1 

4782 - это первый номер с 1000 цифрами для моего кода.

Выход: [4782, 4783, 4784, 4785 4786].

О fibonnaci формуле с использованием порождающих функций http://www.math.ufl.edu/~joelar/generatingfibonacci.pdf

Answer 5

Вы можете получить решение без какого-либо программирования.

Мы знаем, что число m использует не менее k цифр в десятичном представлении, если log_10 (m)> = k-1.

Поэтому в основном все, что мы должны сделать, это решить неравенство:

log_10 (F_n)> = 999

Используя явный вид F_n, вы знаете, это ближайшее целое число к ((1 + SQRT (5))/2)^п/SQRT (5). Мы можем использовать это приближение для F_n. Имейте в виду, что в этом есть небольшая ошибка, но мы справимся с этим позже.

Так неравенство становится:

log_10 (((1 + Sqrt (5))/2)^п/SQRT (5))> = 999

После использования некоторых логарифмических тождества и некоторое упорядочение это выглядит следующим образом:

п> = (999 + log_10 (SQRT (5)))/log_10 ((1 + Sqrt (5))/2) ~ = 4781,8592

Таким образом, наш окончательный ответ должен быть где-то вокруг этого, давайте обсудим ошибку, о которой я упоминал ранее. Ошибка аппроксимации равна ((1-Sqrt (5))/2)^n/Sqrt (5). (1-Sqrt (5))/2 ~ = -0,68, его абсолютное значение меньше 1, поэтому после возведения в степень он приближается и приближается к 0. (-0.68)^4781 - очень небольшое число, поэтому разность между логарифмом F_n и его приближением, которые мы использовали (это числа около 1000), еще меньше. Не вычисляя его точно, учитывая величину F_n, эту разность можно полностью пренебречь. Таким образом, решение является наименьшее целое число п, для которых п> = 4781.8592, то есть 4782.

Answer 6

Этот генератор дает целые числа, и я испытал его до fib(21)

from decimal import Decimal 
from math import sqrt 

while True: 
#sqrt_5 = Decimal(sqrt(5)) 
    sqrt_5 = Decimal(5).sqrt() # As thkang suggested! 
    fib = lambda n: (1/sqrt_5)*((2/(-1+ sqrt_5))**(n) - (2/(-1-sqrt_5))**(n)) 
    a=input() 
    if a=="x": 
     break 
    d=round(fib(int(a))) 

    print("\t"+str(d)) 

Для выхода из программы , просто введите x