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.

Project Euler 005 – IronRuby

2 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?

#I had to shorten this to fit on the blog

#correctly so

#r = result

#e = element

answer = [16,9,5,7,11,13,17,19].inject(1) {|r, e| r * e }

Discussion

Well, that was easy.  I really enjoy inject style methods for operating on arrays..

Project Euler 005 – C#

1 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?

namespace ProjectEulerCSharp_005

{

class Program

{

static void Main(string[] args)

{

//have we found the answer yet?

//let’s start off by saying "no"

bool notFound = true;

//20 seems like as good of a

//starting spot as any

long candidate = 20;

while(notFound)

{

//I am incrementing up front

//so that my loop exits elegantly

candidate++;

//here I am assuming that this candidate

//is the answer.  I set it back when I

//find a divisor that it doesn’t work for

notFound = false;

//this is not too important, but it’s a good

//they are more likely to fail

for (int divisor = 2; divisor <= 20; divisor++)

{

if (candidate % divisor != 0)

{

notFound = true;

break;

}

}

}

System.Console.WriteLine(candidate);

}

}

}

Discussion

The brute force approach is pretty silly, but it does work and within the 1 minute rule.  It takes about 7.5 seconds on my 6 month old laptop.  When this problem was announced (November 2001) the same code would have probably taken over 10 minutes to complete – at least according to my back of the napkin estimation of Moore’s law.  🙂

Project Euler 005 – F#

28 02 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?

*)

(* I have put this list in the format of

2^4, 3^2, 5^1 …

*)

let factorsWeCareAboutLessThan20 = [pown 2 4;pown 3 2;5;7;11;13;17;19]

(* multiply them all together *)

|> List.fold(fun elem acc -> elem * acc)  1

Discussion

This is a pretty simple problem if you know what you’re looking for.  We want to find the least common multiple of (1,2,3..20).

The key observation here is that anything that is divisible by 16 (24) is also divisible by 2, 4 (22), and 8 (23).  Restating this as a question: What is the highest power of 2 we need to concern ourselves with?  25 = 32  which is too big (bigger than 20).  24 = 16 so that’s just right.  Rinse and repeat with other primes.

Later this week we might look at a more automated approach… if you’re lucky.

Project Euler 004–JavaScript

25 02 2011

Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Solution

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"&gt;

<html xmlns="http://www.w3.org/1999/xhtml"&gt;

<title>Project Euler 004</title>

<body >

<script type="text/javascript">

function IsPalindrome(number)

{

numberStr = number.toString();

// simple palindrome test

// we only have to go through the first

// half of the letters

for (c = 0; c < numberStr.length-c; c++)

{

if (numberStr[c] !=

numberStr[numberStr.length-c-1]) {

return false;

}

}

return true;

}

//here’s a familiar loop

for(i = 100; i < 1000; i++)

{

for(j = i; j < 1000; j++)

{

product = i*j;

&& IsPalindrome(product))

}

}

</script>

</body>

</html>

Discussion

Nothing too special here, but this is the one solution that didn’t use some sort of built in “reverse” function.  Still works.

Project Euler 004 – TSQL

24 02 2011

Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Solution

–A palindromic number reads the same both ways.

–The largest palindrome made from the product of

–two 2-digit numbers is 9009 = 91  99.

–Find the largest palindrome made from the

–product of two 3-digit numbers.

— this is a fun query

— we join the number table to

— itself ensuring that the right

— number is greater than or equal

— to the left number

SELECT MAX(LeftNumber.number * RightNumber.number)

FROM Number LeftNumber

INNER JOIN Number RightNumber

ON LeftNumber.number <= RightNumber.number

— then we limit the numbers to 3 digits

— an obvious (and better) method for this is

— LeftNumber.number >= 100

— and LeftNumber.number <= 999

— but this technique is more interesting

WHERE LEN(CAST(LeftNumber.number AS VARCHAR)) = 3

and LEN(CAST(RightNumber.number AS VARCHAR)) = 3

— finally, the clever part is determining

— the palindromicity of the product

and(CAST(LeftNumber.number * RightNumber.number AS VARCHAR)

= REVERSE(CAST(LeftNumber.number * RightNumber.number AS VARCHAR)))

Discussion

I am quite happy with this solution.

Project Euler 004 – IronRuby

23 02 2011

Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Solution

# A palindromic number reads the same both ways.

# The largest palindrome made from the product of

# two 2-digit numbers is 9009 = 91  99.

# Find the largest palindrome made from the

# product of two 3-digit numbers.

# placeholder

#loop through each 3-digit number

for i in 100..999 do

for j in i..999 do

product = i*j

# the palindrome test is simple here

# since we are using the same technique

# as the F# and C# functions

if product.to_s().reverse == product.to_s() &&

end

end

end

Discussion

I have to admit, Ruby makes this code pretty simple.

Project Euler 004 – C#

22 02 2011

Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Solution

using System.Collections.Generic;

//A palindromic number reads the same both ways.

//The largest palindrome made from the product of

//two 2-digit numbers is 9009 = 91  99.

//Find the largest palindrome made from the

//product of two 3-digit numbers.

namespace ProjectEulerCSharp_004

{

class Program

{

static void Main(string[] args)

{

//simple placeholder for our

//biggest palindrome

int maxPalindrome = 0;

//loop through each 3-digit number

for (int i = 100; i < 1000; i++)

{

//this is a slight optimization

//over our F# solution because

// 100 * 101 = 101 * 100 so we

// don’t need to perform the second

// multiplication

for (int j = i; j < 1000; j++)

{

int product = i * j;

//used an extension method to test for

//palindromicity (is that a word)

if (product.IsPalindrome()

&& product > maxPalindrome)

{

maxPalindrome = product;

}

}

}

System.Console.WriteLine(maxPalindrome);

}

}

// extension methods are awesome

public static class Extensions

{

// here we create a function called

// IsPalindrome that uses the same

// technique as the F# function

public static bool IsPalindrome(this int i)

{

// get a convenient list of chars

List<char> chars =

new List<char>(i.ToString().ToCharArray());

// reverse them

chars.Reverse();

// are we a palindrome?

return i == int.Parse(new string(chars.ToArray()));

}

}

}

Discussion

My favorite part of this solution is the use of the extension method.  Why don’t we use those all the time?  Of course, the generic List structure offers some helpful routines as well.

Project Euler 004 – F#

21 02 2011

This has content has been moved. Please find it here:

http://eulersolutions.com/2011/05/19/project-euler-004-f/

Project Euler 003 – JavaScript

18 02 2011

Problem 3

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

What is the largest prime factor of the number 600851475143 ?

Solution

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"&gt;

<html xmlns="http://www.w3.org/1999/xhtml"&gt;

<title>Project Euler 003</title>

<body >

<script type="text/javascript">

function PrimeFactor(number)

{

//here is our list of prime factors

factors = new Array();

//assume the number is prime

//unless we find a factor

isPrime = true;

//here is the upper limit of what we need to test

factorCandidate = Math.round(Math.sqrt(number), 0);

while (factorCandidate > 1)

{

//is this a factor?

if (number % factorCandidate == 0)

{

//if so, what are it’s factors?

divisor = number / factorCandidate;

factors.concat(PrimeFactor(factorCandidate));

factors.concat(PrimeFactor(divisor));

isPrime = false;

}

//next

factorCandidate–;

}

//we are only adding prime factors

if (isPrime) { factors.push(number); }

return factors;

}

factors = PrimeFactor(600851475143);

// this sorts the numbers in ascending order

factors.sort();

// this reverses the list so the biggest one

// is on top.

factors.reverse();

</script>

</body>

</html>

Discussion

Debugging JavaScript is not my forte.  The concat function was handy here, but I don’t think that JavaScript is going to get much better for me unless I spend some time getting better tools.