## Project Euler 007 – JavaScript

18 03 2011

Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

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;

<!–

By listing the first six prime numbers:

2, 3, 5, 7, 11, and 13, we can see that

the 6th prime is 13.

What is the 10001st prime number?

–>

<head>

<title>Project Euler 007</title>

</head>

<body>

<script type="text/javascript">

maxPrime = 10001;

primes = new Array(maxPrime);

primes = 2;

primes = 3;

primeCount = 2;

while (primeCount < maxPrime) {

isPrime = false;

candidate = primes[primeCount – 1] + 2;

while (!isPrime) {

isPrime = true;

for (pindex = 0; pindex < primeCount; pindex++) {

prime = primes[pindex];

if (candidate % prime == 0) {

isPrime = false;

break;

}

}

if (!isPrime) { candidate += 2; }

else {

primes[primeCount] = candidate;

primeCount++;

}

}

}

document.write("<b>" + primes[maxPrime-1] + "</b>");

</script>

</body>

</html>

Discussion

Happy JavaScript nth prime finder.

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

## Project Euler 007 – TSQL

17 03 2011

Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

Solution

— By listing the first six prime numbers:

— 2, 3, 5, 7, 11, and 13, we can see that

— the 6th prime is 13.

— What is the 10001st prime number?

SELECT number FROM

(SELECT row_number() OVER (ORDER BY number) as primeindex, number

FROM Number

WHERE isprime = 1) Primes

WHERE Primes.primeindex = 10001

Discussion

On the surface this solution might seem pretty ‘meh’, but I’m a big fan.  It’s obviously going to be my fastest solution because it’s a simple look up – very common in real life scenarios.  I also got to use row_number() and a subquery as a data source which always delight me.

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

## Project Euler 007 – IronRuby

16 03 2011

Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

Solution

#By listing the first six prime numbers:

#2, 3, 5, 7, 11, and 13, we can see that

#the 6th prime is 13.

#What is the 10001st prime number?

primes = [2,3]

while primes.length < 10001 do

candidate = primes[primes.length 1] + 2;

isPrime = false

while !isPrime do

isPrime = true

for prime in primes

if candidate % prime == 0 then

isPrime = false

break

end

end

if !isPrime then

candidate += 2

else

primes.push(candidate)

end

end

end

puts primes[primes.length1]

Discussion

This is pretty much a straight port of the C# solution.  It turns out to be about an order of magnitude slower than the C# version (IronRuby ~11 seconds, C# ~ 1 second).  It still comes up with the correct answer, and it’s well within the 1 minute rule.

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

## Project Euler 007 – C#

15 03 2011

Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

Solution

//By listing the first six prime numbers:

//2, 3, 5, 7, 11, and 13, we can see that

//the 6th prime is 13.

//What is the 10001st prime number?

using System.Collections.Generic;

namespace ProjectEulerCSharp_007

{

class Program

{

static void Main(string[] args)

{

List<long> primes = new List<long>(10) { 2, 3 };

while (primes.Count < 10001)

{

bool isPrime = false;

long candidate = primes[primes.Count – 1] + 2;

while (!isPrime)

{

isPrime = true;

foreach (long prime in primes)

{

if (candidate % prime == 0)

{

isPrime = false;

break;

}

}

if (!isPrime) { candidate += 2; }

else { primes.Add(candidate); }

}

}

System.Console.WriteLine(primes[primes.Count-1]);

}

}

}

Discussion

Getting back to my imperative roots, this problem was pretty easy to solve.

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

## Project Euler 007 – F#

14 03 2011

Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

Solution

(*

By listing the first six prime numbers:

2, 3, 5, 7, 11, and 13, we can see that

the 6th prime is 13.

What is the 10001st prime number?

*)

let primes =

let rec prim n (sofar: list<int>) =

seq { if (sofar |> List.forall (fun i -> n%i <> 0)) then

yield n

yield! prim (n+1) (n :: sofar)

else

yield! prim (n+1) sofar }

prim 2 []

let tenthousandfirst = primes

|> Seq.take 10001

|> Seq.max

printfn "%A" tenthousandfirst

Discussion

The primes function was posted on a forum by Don Syme.  The use of the infinite sequence is just awesome – again.  20+ years of imperative programming has taken it’s toll so it’s going to take a lot more effort on my part to wrap my mind around this functional stuff.  I’ll keep plugging away.

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

## Project Euler 006 – JavaScript

11 03 2011

Problem 6

The sum of the squares of the first ten natural numbers is,

12 + 22 + … + 102 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Solution

(1 + 2 + … + 10)^2 = 55^2 = 3025

Hence the difference between the sum

of the squares of the first ten natural

numbers and the square of the sum is

3025 – 385 = 2640.

Find the difference between the sum of

the squares of the first one hundred natural

numbers and the square of the sum.

–>

<head>

<title>Project Euler 006</title>

</head>

<body >

<script type="text/javascript">

n = 100;

answer=.25*Math.pow(n,4)+1/6*Math.pow(n,3)-.25*Math.pow(n,2)-1/6*n;

document.write("<b>" + answer + "</b>");

</script>

</body>

</html>

Discussion

You’ll notice that this is fast, but different from the IronRuby solution given a couple of days ago. if you know that this is a 4th order polynomial then you can solve for the coefficients using simple linear algebra techniques.  That is, assume the solution is in the form of

ax4 + bx3 + cx2 + dx + e

Then you just need to solve for a, b, c, d, and e. This is a pretty trivial tasks if you have the right tools at your disposal.   Since there are 5 unknowns here we need 5 equations. Let’s plug 0 in first.

a*0 + b*0 + c * 0 + d * 0 + e = 0

This means that e = 0 so now we actually only have 4 unknowns a, b, c, and d.  If you repeat this process by replacing x with your number (1,2,3,4) and setting the right side of the equation to the square(sums) – sum(squares) then you will get this matrix:

 n4 n3 n2 n s 1 1 1 1 0 16 8 4 2 4 81 27 9 3 22 256 64 16 4 70

Where s is the solution to sum(n)2 – sum(n2). If you plug this into a solver you will get:

(1/4, 1/6, –1/4, –1/6)

The only real trick is determining that a 4th order polynomial will be adequate to solve the problem.  If you are really curious how to do that, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

## Project Euler 006 – TSQL

10 03 2011

Problem 6

The sum of the squares of the first ten natural numbers is,

12 + 22 + … + 102 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Solution

— The sum of the squares of

— the first ten natural numbers is,

— 1^2 + 2^2 + … + 10^2 = 385

— The square of the sum of the

— first ten natural numbers is,

— (1 + 2 + … + 10)^2 = 55^2 = 3025

— Hence the difference between the sum

— of the squares of the first ten natural

— numbers and the square of the sum is

— 3025 – 385 = 2640.

— Find the difference between the sum of

— the squares of the first one hundred natural

— numbers and the square of the sum.

select power(sum(number),2) sum([square])

from Number

where number <= 100

Discussion

Just like the other solutions, this one is quite simple.  It is aided by the fact that when I populated my database I included all of the squares in the number table as well.

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

## Project Euler 006 – C#

8 03 2011

Problem 6

The sum of the squares of the first ten natural numbers is,

12 + 22 + … + 102 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Solution

//The sum of the squares of

//the first ten natural numbers is,

//1^2 + 2^2 + … + 10^2 = 385

//The square of the sum of the

//first ten natural numbers is,

//(1 + 2 + … + 10)^2 = 55^2 = 3025

//Hence the difference between the sum

//of the squares of the first ten natural

//numbers and the square of the sum is

//3025 – 385 = 2640.

//Find the difference between the sum of

//the squares of the first one hundred natural

//numbers and the square of the sum.

namespace ProjectEulerCSharp_006

{

class Program

{

static void Main(string[] args)

{

int sumsqrs = 0;

int sqrsums = 0;

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

{

sumsqrs += i * i;

sqrsums += i;

}

sqrsums *= sqrsums;

System.Console.WriteLine(sqrsums – sumsqrs);

}

}

}

Discussion

No trick today.

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

## Project Euler 006 – F#

7 03 2011

Problem 6

The sum of the squares of the first ten natural numbers is,

12 + 22 + … + 102 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Solution

(*

The sum of the squares of

the first ten natural numbers is,

1^2 + 2^2 + … + 10^2 = 385

The square of the sum of the

first ten natural numbers is,

(1 + 2 + … + 10)^2 = 55^2 = 3025

Hence the difference between the sum

of the squares of the first ten natural

numbers and the square of the sum is

3025 – 385 = 2640.

Find the difference between the sum of

the squares of the first one hundred natural

numbers and the square of the sum.

*)

let sqr x = x*x

let numbers = [1..100]

let sumofsqrs x = x

|> List.map sqr

|> List.sum

let sqrofsum x = x

|> List.sum

|> sqr

let answer x = sqrofsum x – sumofsqrs x

printfn "%A" (answer numbers)

Discussion

The F# solution is rather elegant once again.  There is a common math ‘trick’, but for only 100 elements there is no reason to shy away from the brute force solution.  Later this week we’ll see the trick.

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

## Project Euler 005 – JavaScript

4 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

<!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;

<!–

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?

–>

<head>

<title>Project Euler 005</title>

</head>

<body >

<script type="text/javascript">

factors = [16, 9, 5, 7, 11, 13, 17, 19];

answer = 1;

for (i = 0; i < factors.length; i++) {

answer *= factors[i];

}

document.write("<b>" + answer + "</b>");

</script>

</body>

</html>

Discussion

I looked into a reduce function for JavaScript but it seemed more difficult than a simple loop in this case.  So that’s what you got – a simple loop.

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