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

–>

<title>Project Euler 007</title>

<body>

<script type="text/javascript">

maxPrime = 10001;

primes = new Array(maxPrime);

primes[0] = 2;

primes[1] = 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.

## 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.

## 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.

## 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; }

}

}

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

}

}

}

Discussion

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

## 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.

## 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.

–>

<title>Project Euler 006</title>

<body >

<script type="text/javascript">

n = 100;

</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.

## Project Euler 006 – IronRuby

9 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.

n = 100

answer = (n*(n+1) / 2)**2 (n*(n+1)*(2*n+1)) / 6

Discussion

And there’s your trick.  Incidentally, I need to create a cheat sheet for the math functions in all of these languages.  ** is not in my vocabulary.  It’s nice though.

## 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.

## 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