XML FeedsProject Euler Q2 with Mysql
By admin on Aug 29, 2009 | In Formula 1 - More advanced stuff, Showroom - Examples of Mysql usage | Send feedback »
Here's question 2 from Project Euler The Euler Project :
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Find the sum of all the even-valued terms in the sequence which do not exceed four million.
Hmmm. Looking at the Perl solution (again from AJSWiki Perl Euler solutions ) we have the following code:
Code:
#!/usr/bin/perl | |
| |
@f=(1,2); | |
$sum=2; | |
while(($f=$f[0]+$f[1]) <= 4_000_000) { | |
shift @f; push @f,$f; | |
$sum+=$f if $f%2==0 } | |
print $sum, "\n"; | |
# Answer = 4613732 |
We see that the Perl program adds to $sum where the variable $f is an even number, and loops until the value shifted into memory (which is added to each previous value to produce the Fibonacci series) exceeds 4,000,000.
So how can we accomplish this in MySql? Again (as per my first post on the Euler Project) we will use variables to iterate. In order to get the Fibonacci sequence we can use:
Code:
set @varsum=1; | |
set @varadd=1; | |
set @var1=1; | |
set @var2=1; | |
| |
select @varsum:=@varadd+@varsum as fibonacci, | |
@varadd:=@var2, | |
@var2:=@varsum, orderid | |
from orders limit 40; |
I used 40 as a limit after a bit of trial and error. Remember to reset the variables every time you run a query like this.
We can then do a sum of those values brought back where the Fibonacci value is less than 4 million, by using an inner select:
Code:
set @varsum=1; | |
set @varadd=1; | |
set @var1=1; | |
set @var2=1; | |
| |
select sum(fibonacci) from (select @varsum:=@varadd+@varsum as fibonacci,@varadd:=@var2,@var2:=@varsum, orderid from orders limit 40) tmp where fibonacci < 4000000; |
But we're summing up every term by doing this - the problem states we should only sum up the even-valued term. Easily modified (see entry on number 1 solution) by using the MOD function to only sum up even numbers:
Code:
set @varsum=1; | |
set @varadd=1; | |
set @var1=1; | |
set @var2=1; | |
| |
select sum(fibonacci) from | |
(select @varsum:=@varadd+@varsum as fibonacci, | |
@varadd:=@var2, @var2:=@varsum | |
from orders limit 40) tmp | |
where fibonacci < 4000000 | |
and mod(fibonacci,2)=0; | |
| |
+----------------+ | |
| sum(fibonacci) | | |
+----------------+ | |
| 4613732 | | |
+----------------+ | |
1 row in set (0.27 sec) |
Hope this is of use to someone!
Regards
Mark
Feedback awaiting moderation
This post has 8 feedbacks awaiting moderation...
Leave a comment
| « Project Euler Q3 with Mysql | Project Euler Q1 with Mysql » |
