Tags: mod

Project 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

Tags: mod, perl, project euler, variables

Project Euler Q1 with Mysql

By admin on Aug 29, 2009 | In Formula 1 - More advanced stuff, Showroom - Examples of Mysql usage | Send feedback »

Hi, I've recently come across the Euler Project The Euler Project that sets mathematical challenges in whatever coding language you prefer to use. Now I'm not claiming that Mysql is particularly apt for these challenges, but I wondered if I could possibly solve one or two merely by the use of Mysql (not using any other scripting language such as Php or RoR).

Here's the first question:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

First I'm going to see a way it can be done in Perl (the following is adapted from a solution I found at Euler oneliners in Perl ) and then see how I can apply this in Mysql:

Code:

#!/usr/bin/perl
# adds each multiple of 3 to $n
# then adds each mutiple of 5 to $n unless divisible by 3
# to avoid duplication!
 
$n=0;
for($i=3;$i&lt;1000;$i+=3) {$n+=$i}
 
       for($i=5;$i&lt;1000;$i+=5)
 {$n+=$i unless $i%3 == 0}
 print $n, "\n";
 
# produces 233168

For my Mysql code I will start by seeing how we test if a number is divisible by another number in Mysql. One way is to use the function MOD that returns the exact remainder after division. It should therefore return 0 when the number is divisible by your test figure. So select mod(9,3); returns 0 whereas select mod(8,2); returns 2.
Next we need a way to iterate up to 999 (ie all numbers below 1000). I tend to use a dummy table populated with an ascending count for this type of thing; however it's possible to use a variable technique so long as you join to a table with enough rows in it. For example, if we have a table orders with 20,000 records, we can bring back just 20 row-numbered records like this:

Code:

select @rownum:=@rownum+1 'row_num', e.* from orders e,    
(SELECT @rownum:=0) r
order by orderid desc limit 20

So to bring back all those where the row_num is divisible by 3 we put the above into an inner select:

Code:

select row_num from
(select @rownum:=@rownum+1 'row_num' from orders e,    
 (SELECT @rownum:=0) r  
order by orderid desc limit 20) tmp
where mod(row_num,3) = 0;

From there it's an easy step to add in a [strong]OR[/strong] clause to include numbers divisible by 5, and to sum the result.

Code:

select sum(row_num) from
(select @rownum:=@rownum+1 'row_num' from orders e,    
(SELECT @rownum:=0) r  
order by orderid desc limit 999) tmp
where mod(row_num,3) = 0 or mod(row_num,5) = 0;

This gives an answer of: 233168. It came back in 0.08 of a second too, so wasn't too inefficient! I hope to look at another Euler teaser soon!

Tags: mod, perl, project euler, variables