The road to using Mysql

Here is the question set for us this time from The Euler Project

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143

In Mysql you can calulate prime numbers using a "numbers" table eg:

Code:

But this is probably not efficient or realistic for larger numbers (and we are probably looking at big numbers in this exercise).
Another way to approach this is to work out the smallest divisor of the original number starting from 2, divide out that number, and again (starting from 2) find the next smallest divisor (ie bigger than or equal to the previous result) of that new number. Carry on doing this until we can go no further and we should end up with the largest prime factor (as for instance a factor of 8 would be broken down by 2 twice). I hope the following Mysql code makes sense; we increment the variable var1 by 1 each time and test (via the mod function) whether it's a factor of the variable bignuma. If it is, we divide out var1 to get a smaller bignuma, and start incrementing var1 again from 2.

Code:

In my three blog entries on iterating through numbers I've used a table that I've already created and populated in my database (in this case it's called orders). Although it's relatively straightforward to create a table yourself with lots of rows, there are system tables you can use for this purpose. I recently found this on the web - openark blog mysql - a very good read. If they are installed you can use rows from mysql.help_topic, otherwise the author suggests you can use tables from the data dictionary INFORMATION_SCHEMA instead like COLLATIONS or COLUMNS. You do need to check first that there are enough rows to suit your requirement though. As this method can also be slow I would recommend that you create a table with the required number of rows for iteration purposes where possible. Here's one way you can populate a table with a range of numbers in Mysql ( taken from a question on Stack overflow by a user known as PittsburghDBA). This generates 1000 rows (from 0 to 999) using the combination of using a cross join method with the UNION keyword, but you can always adapt it to suit yourself.

Code:

I hope in the last 3 blog entries I've given some idea on how to approach solving the problems in the Euler Project with Mysql. Although I'll continue looking at the problems myself, I won't be publishing most of the solutions here, so it's up to you if you continue or not (with or without Mysql). Good luck!

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:

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:

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:

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:

Hope this is of use to someone!
Regards
Mark

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:

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:

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

Code:

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:

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!