Geek Answers Handbook

Fibonacci less than 4 million

Possible duplicate:
Python program to find the Fibonacci series. Read more Pythonic way.

Hey, I tried to write a script that sums all the even members in a “Fibonacci sequence” under 4 million.

Fibonacci1 = 1 Fibonacci2 = 2 a = 2 i = 4 for i in range(1,4000000): Fibonacci1 = Fibonacci1 + Fibonacci2 if Fibonacci1 % 2 == 0: a = a + Fibonacci1 Fibonacci2 = Fibonacci1 + Fibonacci2 if Fibonacci2 % 2 == 0: a = a + Fibonacci2 print a raw_input()

it took less than a minute, but it took all night, and it was not allowed!

Edit: Sorry guys, I misunderstood the problem. I, although this means that I must summarize all the even conditions to 4 million! But the solution was to sum the even conditions up to 4 million.

Work code (completed in less than one second):

 Fibonacci1 = 1 Fibonacci2 = 2 a = 2 while a < 4000000: Fibonacci1 = Fibonacci1 + Fibonacci2 if Fibonacci1 % 2 == 0: a = a + Fibonacci1 Fibonacci2 = Fibonacci1 + Fibonacci2 if Fibonacci2 % 2 == 0: a = a + Fibonacci2 print a raw_input()
+4
python sequence
source share
10 answers

The loop condition is wrong, it should be something like this:

 while True: Fibonacci1 = Fibonacci1 + Fibonacci2 if Fibonacci1 % 2 == 0: if a + Fibonacci1 > 4000000: break a = a + Fibonacci1 Fibonacci2 = Fibonacci1 + Fibonacci2 if Fibonacci2 % 2 == 0: if a + Fibonacci2 > 4000000: break a = a + Fibonacci2
+2
source share

There are several problems in your code:

  • You loop four million times instead of the condition being true.
  • You repeated the code in the body of the loop.

Most people, when they start learning Python, only study imperative programming. This is not surprising because Python is a required language. But Python also supports functional programming to some extent, and for this kind of exercise, the functional programming approach is more enlightened, in my opinion.

First, define a generator that generates all Fibonacci numbers:

 def fib(): a = b = 1 while True: yield a a, b = b, a + b

To use this generator, we can import some useful functions from itertools. To print the first few numbers, use islice :

 from itertools import ifilter, islice, takewhile for x in islice(fib(), 5): print x 
  one
 one
 2
 3
 5

To find only even numbers, we can use ifilter to create a new generator:

 def is_even(x): return x % 2 == 0 evenfibs = ifilter(is_even, fib()) for x in islice(evenfibs, 5): print x 
  2
 8
 34
 144
 610

To get numbers from a generator while the number is more than four million, use takewhile :

 for x in takewhile(lambda x: x < 4000000, evenfibs): print x

To solve the problem, you can use the amount:

 sum(list(takewhile(lambda x: x < 4000000, evenfibs)))

Hopefully this shows that the functional programming approach is not complicated and is a more elegant way to solve certain problems.

+25
source share

Are you sure i want to be less than 4 million?

+3
source share

You may be interested in learning about the Online Encyclopedia of Whole Sequences!

You can search for information by name or by sequence.

If you are looking for either 0,2,8,34 or "Even Fibonacci", you will be redirected to the sequence A014445

There you will find a lot of information, including formulas,
from this, it’s easy to encode a generator that will give even Fibonacci numbers.

 def evenfib(): """ Generates the even fibonacci numbers """ a, b = 2, 0 while True: a, b = b, a+4*b yield a
+3
source share

You are currently summing all the first 2 million even Fibonacci numbers.

But this is not a task. You have to sum all even Fibonacci numbers that are below 4 million.

+2
source share

NOTE. This has been greatly modified to address the urgent issue.

Here's an alternative (and a very quick, but untested method). It relies on several properties:

  • Each Fibonacci number can be calculated directly as a gender (pow (phi, n) + 0.5) (See "Calculation by Rounding" at http://en.wikipedia.org/wiki/Fibonacci_number ). Conversely, the index of the largest Fibonacci number smaller than i is determined by gender (log (i * sqrt (5)) / log (phi))
  • The sum of the first Fibonacci numbers N is the N + 2nd Fibonacci number minus 1 (see The second certificate on the same wikipedia page).
  • Even Fibonacci numbers are every third number. (Look at the sequence mod 2, and the result is trivial)
  • The sum of the even Fibonacci numbers is half the sum of the odd Fibonacci numbers to the same point in the sequence. (This follows from 3. and the fact that F (3N) = F (3N-1) + F (3N-2), therefore F (3N-2) + F (3N-1) + F (3N) = 2 F (N) .. then summing up both sides.

So, we convert our maximum value of 4,000,000 to calculate the index of the highest Fibonacci number than it is.

 int n = floor(log(4000000*sqrt(5))/log(phi)) = 33.

33 is divided by 3, so this is an even Fibonacci number, if there was no need to adjust n.

 n = (n/3)*3

The sum of all Fibonacci numbers to this point, if given

 sum = floor( pow( phi, n+2 )/sqrt(5) + 0.5 ) - 1 = 9227464

The sum of all even numbers is half this:

 sum_even = 4613732

The nice thing is that its O (1) (or O (log (N)), if you include the cost of the pow / log algorithm), and works at doubling .., so we can calculate the sum for very large values.

+2
source share

I definitely don’t understand your algorithm, but it seems that smerriman has a point, 4,000,000 Fibonacci numbers will undoubtedly grow above 4M. I suppose a faster approach would be to generate a sequence up to 4M, then adding evens.

0
source share

Come on, the optimal way to calculate the Fibonacci sequence uses 2 tricks:

EDITED, sorry for the earlier mistake

one

 N =|2 0 0| |1 0 0| |0 0 0| M =|3 2 1| |2 1 0| |0 0 1|

The matrix N * M ^ (n / 3) has the sum of the first n Fibonacci numbers (filtered only by even) - the upper right element.

2:

You can use http://en.wikipedia.org/wiki/Exponentiation_by_squaring , because matrix multiplication is a ring.

So you can solve our problem in O (log n)

0
source share

There are other tricks that make this more efficient than just calculating a complete list of Fibonacci numbers and then adding up the even numbers in the list.

I would like if I were trying to solve this problem, make a list of even Fibonacci numbers. Are there any interesting characteristics of this list? Can you convince yourself that this pattern takes place at all?

Further, I could find a way to calculate the members of this list and only those elements that are needed. I could even see if there are any formulas that give the sum of the sequence of Fibonacci numbers.

Of course, all this would take more of your time than just coding a brute force solution, but Project Euler is all about finding a solution rather than a brute force solution. In the end, if you learned something about mathematics, about computing, then you got it.

0
source share
 ## nice simple generator Mark Byers def fib(): a = b = 1 while True: yield a a, b = b, a + b ## does same as takewhile 5 for fibonacci in zip(range(1,1+5),fib()): print "fib(%i) = %i" % fibonacci ## we can slice to take every second print "even sequence upto 100th" total=0 for fibonacci in zip(range(1,1+100),fib())[::2]: print "fib(%i) = %i" % fibonacci total+=fibonacci[1] ## to double check print "Has sum: ", sum( b for a,b in zip(range(1,1+100),fib())[::2] ),'that is ',total print "odd sequence upto 100th" total=0 for fibonacci in zip(range(1,1+100),fib())[1::2]: print "fib(%i) = %i" % fibonacci total+=fibonacci[1] ## to double check print "Has sum: ", sum( b for a,b in zip(range(1,1+100),fib())[1::2] ),'that is ',total
0
source share

More articles:


All Articles