Project Euler 010 – F#

4 04 2011

Problem 10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

Solution

(*

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

 

Find the sum of all the primes below two million.

*)

 

open System

 

let start = DateTime.Now

 

let isPrime n =

    let m = bigint (sqrt (float n))

    [2I..m] |> List.exists (fun elem-> n % elem = 0I) |> not

 

let primeList n =

    [2I..n]

    |> List.filter isPrime

 

 

let primes  = primeList (bigint (sqrt 2000000.0))

 

let isPrimeFromList n primes =

    primes |> List.exists (fun elem-> n % elem = 0I) |> not

 

let remainingPrimes = [bigint(sqrt(2000000.0)) .. 2000000I] |> List.filter(fun elem -> isPrimeFromList elem primes)

 

printfn "%A" ((primes |> List.sum) + (remainingPrimes |> List.sum))

 

let elapsed = DateTime.Now – start

printfn "%A" elapsed

 

Discussion

I ran into some difficult with this problem as my previous prime determination algorithms were recursive and ended up overflowing the stack.  This solution takes just under 20 seconds on my laptop.  I broke the prime determination into two sections. 

The first is a really naïve solution that checks all of the numbers up to square root of 2 million.  This will give me all of the primes I need to test for primality on the remaining primes.

The second is then a prime test that uses the list of primes to determine the primality.  It’s not real fast, but it gets the job done.

Please, leave a comment, find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

Advertisements




Project Euler 009 – TSQL

31 03 2011

Problem 9

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

Solution

select a*b*c from PythagoreanTriple

where a + b + c = 1000

 

Discussion

Clearly this problem is easy if you have a table full of Pythagorean triples.  It turns out I do and it is a lot bigger than 1000.

Please, leave a comment, find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).





Project Euler 009 – IronRuby

30 03 2011

Problem 9

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

Solution

exit = false

for a in 1..999 do

    for b in a..999 do

        c = 1000 a b

        if c < b  then break end

           

         if a**2 + b**2 == c**2

            puts a*b*c

            exit = true

            break

         end

    end

    if exit then break end

end

Discussion

Anybody know the proper way to exit an IronRuby program?  Leave a comment, find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).





Project Euler 009 – C#

29 03 2011

Problem 9

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

Solution 1

using System;

namespace ProjectEulerCSharp_009

{

    class Program

    {

        static void Main(string[] args)

        {

            int iterations = 0;

            for (int a = 1; a <= 998; a++)

            {

                for (int b = 1; b <= 998; b++)

                {

                    int c = 1000 – (a + b);

                    iterations++;

                    if (a * a + b * b == c * c)

                    {

                        System.Console.WriteLine("{0}", a*b*c);

                        System.Console.WriteLine(iterations);

                        return;

                    }

                }

            }

        }

    }

}

Solution 2

using System;

namespace ProjectEulerCSharp_009

{

    class Program

    {

        static void Main(string[] args)

        {

            int iterations = 0;

            for (int a = 1; a <= 998; a++)

            {

                for (int b = a + 1; b <= 998; b++)

                {

                    int c = 1000 – (a + b);

                    iterations++;

                    if (a * a + b * b == c * c)

                    {

                        System.Console.WriteLine("{0}", a*b*c);

                        System.Console.WriteLine(iterations);

                        return;

                    }

                }

            }

        }

    }

}

Solution 3

using System;

namespace ProjectEulerCSharp_009

{

    class Program

    {

        static void Main(string[] args)

        {

            int iterations = 0;

            for (int a = 1; a <= 998; a++)

            {

                for (int b = a + 1; a + b < 1000; b++)

                {

                    int c = 1000 – (a + b);

                    iterations++;

                    if (a * a + b * b == c * c)

                    {

                        System.Console.WriteLine("{0}", a*b*c);

                        System.Console.WriteLine(iterations);

                        return;

                    }

                }

            }

        }

    }

}

 

Solution 4

using System;

namespace ProjectEulerCSharp_009

{

    class Program

    {

        static void Main(string[] args)

        {

            int iterations = 0;

            for (int a = 1; a <= 998; a++)

            {

                for (int b = a + 1; a + b < 1000; b++)

                {

                    int c = 1000 – (a + b);

                    if (c <= b) { break; }

                    iterations++;

                    if (a * a + b * b == c * c)

                    {

                        System.Console.WriteLine("{0}", a*b*c);

                        System.Console.WriteLine(iterations);

                        return;

                    }

                }

            }

        }

    }

}

Discussion

I am a big fan of getting the code working then optimizing later.  I wanted to demonstrate that process with those post so I have included 4 iterations of optimizations.

If we were to loop through all of the possible digits from 1 through 998 twice (once for a and once for b) we would end up doing 996,004 iterations.  That’s our baseline.

Solution 1

Because they state that there is only 1 solution, as soon as we find it there is no reason to continue.  The obvious optimization is to exit the loops once we’ve found it.  This brings our iterations to 198,778.

Solution 2

If we realize that we only need to check the numbers where b is greater than a then we can save ourselves and addition 20,000 iterations bringing our new number to 178678.

Solution 3

Knowing that another condition is that a + b + c = 1000 then a + b has to be less than 1000.  This saves nearly 20,000 iterations as well.  We are down to 159,716 iterations.

Solution 4

Finally, knowing that c has to be greater than b we can cut the iterations by 90,000 to : 69676.

That makes us about 14 times faster than the original version.  There are going to be some additional optimizations you can make, but how fast do you need it?   On my laptop, the difference is imperceptible.  I could have left it at the original and been quite happy.

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





Project Euler 009 – F#

28 03 2011

Problem 9

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

Solution

(*

A Pythagorean triplet is a set of three natural numbers, a  b  c, for which,

 

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

 

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product abc.

 

*)

 

let testints = [1..998]

let answer = [for a in testints do

                for b in testints do

                    if b >= a

                       && a + b < 1000

                       && a*a + b*b = (1000-a-b)*(1000-a-b) then

                        yield a * b * (1000-a-b)]

             |> List.head

            

 

 

printfn "%A" answer

 

Discussion

I adapted this solution from my C# solution.  It’s actually not as clean as my C# solution which betrays its imperative origins.  I’m not sure I could come up with a much worse way to accomplish this task and yet it still runs quite snappy.  This is going to be roughly 1,000,000 iterations.  The b >= a makes several iterations pretty snappy.  Still, changing the b loop to

for b in [a..998] do

will would be a better decision.  While we’re at it, we could change testints too.  Perhaps tomorrow will have some additional discussion on optimizations.

 

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





Project Euler 008 – JavaScript

25 03 2011

Problem 8

Find the greatest product of five consecutive digits in the 1000-digit number.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

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;

<head>

    <title>Project Euler 008</title>

</head>

<body>

    <script type="text/javascript">

        dgts = "73167176531330624919225119674426574742355349194934" +

                 "96983520312774506326239578318016984801869478851843" +

                 "85861560789112949495459501737958331952853208805511" +

                 "12540698747158523863050715693290963295227443043557" +

                 "66896648950445244523161731856403098711121722383113" +

                 "62229893423380308135336276614282806444486645238749" +

                 "30358907296290491560440772390713810515859307960866" +

                 "70172427121883998797908792274921901699720888093776" +

                 "65727333001053367881220235421809751254540594752243" +

                 "52584907711670556013604839586446706324415722155397" +

                 "53697817977846174064955149290862569321978468622482" +

                 "83972241375657056057490261407972968652414535100474" +

                 "82166370484403199890008895243450658541227588666881" +

                 "16427171479924442928230863465674813919123162824586" +

                 "17866458359124566529476545682848912883142607690042" +

                 "24219022671055626321111109370544217506941658960408" +

                 "07198403850962455444362981230987879927244284909188" +

                 "84580156166097919133875499200524063689912560717606" +

                 "05886116467109405077541002256983155200055935729725" +

                 "71636269561882670428252483600823257530420752963450";

        answer = 0;

        for (i = 0; i < dgts.length – 5; i++) {

            product = dgts[i]*dgts[i+1]*dgts[i+2]*dgts[i+3]*dgts[i+4];

            if (product > answer) {

                answer = product;

            }

        }

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

    </script>

</body>

</html>

Discussion

Voila.

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





Project Euler 008 – TSQL

24 03 2011

Problem 8

Find the greatest product of five consecutive digits in the 1000-digit number.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Solution

declare @digits varchar(MAX)

set @digits =

73167176531330624919225119674426574742355349194934

96983520312774506326239578318016984801869478851843

85861560789112949495459501737958331952853208805511

12540698747158523863050715693290963295227443043557

66896648950445244523161731856403098711121722383113

62229893423380308135336276614282806444486645238749

30358907296290491560440772390713810515859307960866

70172427121883998797908792274921901699720888093776

65727333001053367881220235421809751254540594752243

52584907711670556013604839586446706324415722155397

53697817977846174064955149290862569321978468622482

83972241375657056057490261407972968652414535100474

82166370484403199890008895243450658541227588666881

16427171479924442928230863465674813919123162824586

17866458359124566529476545682848912883142607690042

24219022671055626321111109370544217506941658960408

07198403850962455444362981230987879927244284909188

84580156166097919133875499200524063689912560717606

05886116467109405077541002256983155200055935729725

71636269561882670428252483600823257530420752963450′

 

declare @returnpattern varchar(2);

set @returnpattern = char(13) + char(10)

 

set @digits = replace(@digits, @returnpattern, )

 

declare @currentDigit int

set @currentDigit = 1

declare @sql varchar(max)

 

while(@currentDigit <= len(@digits))

begin

       set @sql = ‘insert into Problem_008 (ordinal, digit) values (‘ + str(@currentdigit) + ‘, ‘ + substring(@digits, @currentDigit, 1) + ‘)’

       exec(@sql)

       set @currentDigit = @currentDigit + 1

end

 

GO

 

select max(product) from

(select

       digit

       * (select digit from Problem_008 a where a.ordinal = Problem_008.ordinal + 1)

       * (select digit from Problem_008 a where a.ordinal = Problem_008.ordinal + 2)

       * (select digit from Problem_008 a where a.ordinal = Problem_008.ordinal + 3)

       * (select digit from Problem_008 a where a.ordinal = Problem_008.ordinal + 4) as product

from Problem_008

where ordinal < (select count(*) from Problem_008) 3) Products

 

 

Discussion

This one is going to take a bit of explanation.  I parse the thousand digit number for it’s component digits and insert them into a database table with their ordinals.  After the digits are in a table it’s a simple query.

Clearly, I didn’t need to insert the digits into a table to get the result, but as with all of the TSQL solutions I want to solve it as if the information exists in the database if possible.

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