Quel est le problème avec mon générateur de séquence Fibonacci?

Question

J'essaie de résoudre Problem #25 on Project Euler. Voici ce que j'ai jusqu'à présent:

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] 

Chaque numéro que je l'ai testé pour (y compris certains large ones) sort avec un match, mais le projet est Euler n'accepte pas la réponse que je reçois.

Je lis que la réponse est le numéro 4782th, mais je suis en train que le premier nombre avec plus de 1000 chiffres est le 4787e,

11867216745258291596767088485966669273798582100095758927648586619975930687764095025968215177396570693265703962438125699711941059562545194266075961811883693134762216371218311196004424123489176045121333888565534924242378605373120526670329845322631737678903926970677861161240351447136066048164999599442542656514905088616976279305745609791746515632977790194938965236778055329967326038544356209745856855159058933476416258769264398373862584107011986781891656652294354303384242672408623790331963965457196174228574314820977014549061641307451101774166736940218594168337251710513138183086237827524393177246011800953414994670315197696419455768988692973700193372678236023166645886460311356376355559165284374295661676047742503016358708348137445254264644759334748027290043966390891843744407845769620260120918661264249498568399416752809338209739872047617689422485537053988895817801983866648336679027270843804302586168051835624516823216354234081479331553304809262608491851078404280454207286577699580222132259241827433 

et le projet Euler est dire chaque réponse que je l'ai essayé est faux. (Évidemment, je n'ai pas encore essayé 4782, car ce serait tricher.)

Je suis terriblement proche, et clairement quelque chose ne va pas, mais quoi?

Answer 1

Vous regardez len(str(i)) > 1000, alors que, selon l'énoncé du problème, vous devriez vérifier len(str(i)) == 1000.

En outre, vous avez mal interprété le nombre dans la réponse que vous avez lié comme un nombre de fibonacci. En fait, si vous lisez attentivement, c'est le nombre de fois que la fonction fib est appelée. Votre numéro de fibonacci 4782 est correct.

Answer 2

selon le forum de projecteuler pour les solveurs du 25ème problème, vous avez raison.

et le second grand nombre qui commence par 1322 ... n'est pas un nombre de fibonacci.

une fonction pour vérifier si x est un nombre de fibonacci:

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

Comme thkang a souligné que le nombre de gars est faux, Voir le commentaire de wims. Votre algorithme fonctionne.

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 

Voici ce que j'ai utilisé pour le résoudre et obtenir les mêmes réponses que vous.

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

En plus de la question (et problème), vous pouvez utiliser la Génération Functionology Fibonnaci fonction pour obtenir les numéros de Fibonacci de façon directe.

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 est le premier avec 1000 chiffres pour mon code.

La sortie: [4782, 4783, 4784, 4785 4786].

À propos de la formule Fibonnaci en utilisant des fonctions génératrices http://www.math.ufl.edu/~joelar/generatingfibonacci.pdf

Answer 5

Vous pouvez accéder à la solution sans aucune programmation.

Nous savons qu'un nombre m utilise au moins k chiffres en représentation décimale si log_10 (m)> = k-1.

Donc, fondamentalement, tout ce que nous devons faire est de résoudre l'inégalité:

log_10 (F_n)> = 999

En utilisant la forme explicite de F_n, vous savez qu'il est l'entier le plus proche de ((1 + Sqrt (5))/2)^n/Sqrt (5). Nous pouvons utiliser cette approximation pour F_n. Gardez à l'esprit qu'il y a une petite erreur, mais nous le ferons plus tard.

Ainsi, l'inégalité devient:

log_10 (((1 + RACINE (5))/2)^n/RACINE (5))> = 999

Après avoir utilisé des identités logarithmiques et une commande il ressemble à:

n> = (999 + log_10 (RACINE (5)))/log_10 ((1 + RACINE (5))/2) ~ = 4781,8592

donc, notre réponse finale devrait être quelque part autour de cela, parlons de l'erreur que j'ai mentionnée plus tôt. L'erreur d'approximation est ((1-Sqrt (5))/2)^n/Sqrt (5). (1-Sqrt (5))/2 ~ = -0,68, sa valeur absolue est plus petite que 1, donc après l'exponentiation, il devient de plus en plus proche de 0. (-0,68)^4781 est un très petit nombre, donc la différence entre le logarithme de F_n et son approximation que nous avons utilisé (ce sont des nombres autour de 1000) est encore plus petit. Sans le calculer exactement, vu la magnitude de F_n, cette différence peut être complètement négligée. Ainsi, la solution est le plus petit entier n, pour lequel n> = 4781,8592, qui est 4782.

Answer 6

Ce générateur donne des nombres entiers et je l'ai testé jusqu'à 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)) 

Pour quitter le programme , tapez simplement x