Project Euler 005 – TSQL

3 03 2011

Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Solution

— 2520 is the smallest number that can be

— divided by each of the numbers from 1 to 10

— without any remainder.

 

— What is the smallest positive number

— that is evenly divisible by all of the

— numbers from 1 to 20?

 

SELECT EXP(SUM(LOG(POWER(number, FLOOR(LOG(20) / log(number))))))

FROM Number WHERE isprime = 1

AND number < 20

Discussion

I’ll admit it.  I am pretty proud of this solution.  Assuming that we have a list of primes already (which we do) there are two problems that we need to solve.  The first is, what is the proper exponent for each prime?

If you remember from Monday’s solution (F#), I mentioned that 25 was too big (32 > 20) so 24 was the number we needed to use?  So how do you figure that out?  Well, we want to find the maximum k such that

2k ≤ 20

Right?  Let’s solve for k.  Here’s the “trick”:

log(2k) ≤ log(20)

k*log(2) ≤ log(20)

k ≤ log(20)/log(2)

k ≤ 4.32

Since k is an integer, we can set it to 4.  That’s pretty easy.

The next problem I ran into was that SQL doesn’t natively support a “product” aggregate and doesn’t appear to have a convenient fold mechanism.  I was able to solve it with COALESCE, but that required a separate variable to accumulate the results.  I really wanted to solve this with a simple query.  Then I found another trick…

log(a*b) = log(a)+log(b)

So I could use the built in sum aggregator to find the product.  That is

a*b*c… = exp(log(a) + log(b) + log(c)…)

When you couple this trick with the original you find your answer.

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

Advertisements

Actions

Information

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: