CODEWITHSUNDEEP
pythonfibonacci
John
John

Reputation: 16058

What's wrong with my Fibonacci sequence generator?

I'm trying to solve Problem #25 on Project Euler. Here's what I've got so far:

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]

Every number I've tested for (including some large ones) comes out with a match, but Project Euler isn't accepting the answer I'm getting.

I read that the answer is the 4782th number, but I'm getting that the first number with over 1000 digits is the 4787th,

11867216745258291596767088485966669273798582100095758927648586619975930687764095025968215177396570693265703962438125699711941059562545194266075961811883693134762216371218311196004424123489176045121333888565534924242378605373120526670329845322631737678903926970677861161240351447136066048164999599442542656514905088616976279305745609791746515632977790194938965236778055329967326038544356209745856855159058933476416258769264398373862584107011986781891656652294354303384242672408623790331963965457196174228574314820977014549061641307451101774166736940218594168337251710513138183086237827524393177246011800953414994670315197696419455768988692973700193372678236023166645886460311356376355559165284374295661676047742503016358708348137445254264644759334748027290043966390891843744407845769620260120918661264249498568399416752809338209739872047617689422485537053988895817801983866648336679027270843804302586168051835624516823216354234081479331553304809262608491851078404280454207286577699580222132259241827433

and Project Euler is saying every answer I've tried is wrong. (Obviously I didn't try 4782 yet, as that would be cheating.)

I'm tantalizingly close, and clearly something is going wrong, but what?

Upvotes: 3

Views: 693

Answers (6)

hamidfzm
hamidfzm

Reputation: 4685

This generator gives integer numbers and I have tested it up to 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))

To quit the program, just type x

Upvotes: 0

elias
elias

Reputation: 849

You can get to the solution without any programming.

We know, that a number m uses at least k digits in decimal representation if log_10(m)>=k-1.

So basically all we have to do is to solve the inequality:

log_10(F_n)>=999

Using the explicit form of F_n, you know it is the closest integer to ((1+Sqrt(5))/2)^n/Sqrt(5). We can use this approximation for F_n. Keep in mind there is a small error in this, but we will handle it later.

So the inequality becomes:

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

After using some logarithmic identities and some ordering it looks like:

n>=(999+log_10(Sqrt(5)))/log_10((1+Sqrt(5))/2)~=4781.8592

So our final answer should be somewhere around this, let's discuss the error I've mentioned earlier. The approximation error is ((1-Sqrt(5))/2)^n/Sqrt(5). (1-Sqrt(5))/2~=-0.68, its absolute value is smaller than 1, so after exponentiation, it gets closer and closer to 0. (-0.68)^4781 is a very small number, so the difference between the logarithm of F_n and its approximation we used (those are numbers around 1000) is even smaller. Without calculating it exactly, considering the magnitude of F_n this difference can be completely neglected. Thus, the solution is the smallest integer n, for which n>=4781.8592, that is 4782.

Upvotes: 0

Arnaldo Ignacio Gaspar Véjar
Arnaldo Ignacio Gaspar Véjar

Reputation: 1277

In addition to the question (and problem), you can use the Generating Functionology Fibonnaci Function to get the fibonnaci numbers in a direct way.

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 is the first with 1000 digits for my code.

The output: [4782, 4783, 4784, 4785 4786].

About fibonnaci formula using Generating Functions http://www.math.ufl.edu/~joelar/generatingfibonacci.pdf

Upvotes: 1

thkang
thkang

Reputation: 11543

according to the projecteuler forum for solvers of 25th problem, you're correct.

and the second big number which starts with 1322... is not a fibonacci number.

some function to check whether x is a fibonacci number:

   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))

Upvotes: 2

John
John

Reputation: 13699

As thkang pointed out that guys number is wrong, See wims comment. Your algorithm works.

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

Here is what I used to solve it and I get the same answers that you do.

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

Upvotes: 1

wim
wim

Reputation: 362657

You are checking len(str(i)) > 1000, when according to the problem statement you should be checking len(str(i)) == 1000.

Additionally, you misinterpreted the number in the answer you've linked as a fibonacci number. Actually, if you read carefully, it's the number of times the fib function is called. Your fibonacci number 4782 is correct.

Upvotes: 3

Related Questions