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

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


Comments : Leave a Comment »
Tags: ,
Categories : Project Euler

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


Comments : Leave a Comment »
Tags: ,
Categories : Project Euler

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.length–1]

 

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


Comments : Leave a Comment »
Tags: ,
Categories : Project Euler

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


Comments : Leave a Comment »
Tags: ,
Categories : Project Euler

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


Comments : Leave a Comment »
Tags: ,
Categories : Project Euler

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


Comments : Leave a Comment »
Tags: ,
Categories : Project Euler

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


Comments : Leave a Comment »
Tags: ,
Categories : Project Euler

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


Comments : Leave a Comment »
Tags: ,
Categories : Project Euler

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


Comments : Leave a Comment »
Tags: ,
Categories : Project Euler

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


Comments : Leave a Comment »
Tags: ,
Categories : Project Euler

« Previous Entries Next Entries »