Project Euler 003 – TSQL

17 02 2011

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

What is the largest prime factor of the number 600851475143 ?

Solution

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

–What is the largest prime factor of the number 600851475143?

 

— this number is bigger than my database

— so we will add it

CREATE PROCEDURE [dbo].[FactorNumber]

       @number AS BIGINT,

       @originalnumber AS BIGINT

AS

 

DECLARE @isPrime BIT

SET @isPrime = 1

 

DECLARE @factor BIGINT

SET @factor = FLOOR(SQRT(@number))

 

DECLARE @divisor BIGINT

 

WHILE @factor > 1

BEGIN

       IF @number % @factor = 0

       BEGIN

              EXEC FactorNumber @factor, @originalnumber

              — can’t do the math in the function call

              — so I used another variable

              SET @divisor = @number / @factor

              EXEC FactorNumber @divisor, @originalnumber

              SET @isPrime = 0

       END

      

       SET @factor = @factor 1

END

 

— here we store the information for later

IF @isPrime = 1

BEGIN

       INSERT INTO NumberFactor  (number, factor) VALUES (@originalnumber, @number)

END

 

–here are the remaining steps to get the answer

–exec FactorNumber 600851475143, 600851475143

–select MAX(factor) from NumberFactor where number = 600851475143

 

 

Discussion

I’ve included the procedure and the select statement here because this number exceeded my number list.  It follows the same philosophy as some of the previous examples except that it inserts its values into a table instead of returning them to the calling function.  This is why we need to pass the original number in as well.

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





Project Euler 003 – IronRuby

16 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

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

#What is the largest prime factor of the number 600851475143?

 

 

def PrimeFactor(number)

    isPrime = true;

    factors = Array.new

    factorCandidate = Math.sqrt(number).floor

    while factorCandidate > 1 do

        if number % factorCandidate == 0  then

            isPrime = false;

            #kinda like the ‘push’ syntax here

            PrimeFactor(factorCandidate).each {|factor| factors << factor }

            PrimeFactor(number / factorCandidate).each {|factor| factors << factor }

        end

        factorCandidate -= 1

    end

    if isPrime then

        factors.Add(number)

    end

    factors

end

 

factors = PrimeFactor(600851475143)

puts factors.max

 

 

Discussion

Even though I copied and pasted my C# solution here it still took me a while to iron out the kinks.  There are some things I really enjoy about the syntax so far, but I still haven’t discovered the virtue of dynamic typing.  Maybe I will as time passes.

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





Project Euler 003 – C#

15 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

using System.Collections.Generic;

using System;

namespace ProjectEulerCSharp_002

{

    class Program

    {

        static void Main(string[] args)

        {

            List<long> 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();

 

            //show me the money

            System.Console.WriteLine(factors[0]);

        }

   

 

        public static List<long> PrimeFactor(long number)

        {

            //here is our list of prime factors

            List<long> factors = new List<long>();

           

            //assume the number is prime

            //unless we find a factor

            bool isPrime = true;

 

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

            long factorCandidate = (long)Math.Sqrt(number);

            while (factorCandidate > 1)

            {

                //is this a factor?

                if (number % factorCandidate == 0)

                {

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

                    factors.AddRange(

                        PrimeFactor(factorCandidate));

                    //what about the other divisor?

                    factors.AddRange(

                        PrimeFactor(number / factorCandidate));

                    //we know this one isn’t prime

                    isPrime = false;

                }

                //next

                factorCandidate–;

            }

            //we are only adding prime factors

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

            //send ’em back

            return factors;

        }

    }

}

 

Discussion

In contrast to my F# solution this didn’t take much longer than 5 minutes to write.  I didn’t spend any time optimizing it because it ran so fast for the problem already.

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





Project Euler 003 – F#

14 02 2011

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

http://eulersolutions.com/2011/05/18/project-euler-003-f/





Project Euler 002 – JavaScript

11 02 2011

Problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

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 002</title>

</head>

<body >

    <script type="text/javascript">

            answer = 0;

            fib0 = 1;

            fib1 = 1;

            fib2 = 2;

            while (fib2 < 4000000)

            {

                answer += fib2;

 

                fib0 = fib1 + fib2;

                fib1 = fib0 + fib2;

                fib2 = fib0 + fib1;

            }

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

    </script>

</body>

</html>

Discussion

C based languages have such similar syntax that this is a copy from the C# solution.  Of course, I had to remove the type declarations because it’s not strongly typed.  Oh, and I guess I do output to HTML.

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





Project Euler 002–TSQL

10 02 2011

Problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Solution

–By considering the terms in the Fibonacci sequence\

–whose values do not exceed four million, find the

–sum of the even valued terms.

 

–this is a trivial query to write

select SUM(number) from Number

where number < 4000000

and isfibonacci = 1

and number % 2 = 0

 

Discussion

Once again, I have a large database of numbers with properties associated with them.  That makes this solution fairly uninteresting. 

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





Project Euler 002 – IronRuby

9 02 2011

Problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Solution

#By considering the terms in the Fibonacci sequence

#whose values do not exceed four million, find the

#sum of the even valued terms.

 

 

# this uses the same technique

# as the c# implementation

# I find this initialization

# syntax interesting

answer = 0

fib0, fib1, fib2 = 1, 1, 2;

while fib2 < 4000000

   

    answer += fib2

    #odd + even = odd

    fib0 = fib1 + fib2;

    #odd + even = odd

    fib1 = fib0 + fib2;

    #odd + odd = even

    fib2 = fib0 + fib1;

end

 

puts answer

 

Discussion

This is obviously a port of the C# solution.  The one piece I find interesting is

fib0, fib1, fib2 = 1,1,2;

Seems to be equivalent to

fib0 = 1, fib1 = 1, fib2 = 2;

For cutting and pasting large lists, the first option might be more attractive?  Why not use an array in that case?  I suppose I’ll learn more as I continue down the path.

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





Project Euler 002 – C#

8 02 2011

Problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Solution

namespace ProjectEulerCSharp_002

{

    //By considering the terms in the Fibonacci sequence

    //whose values do not exceed four million, find the

    //sum of the even valued terms.

    class Program

    {

        static void Main(string[] args)

        {

            int answer = 0;

            //typically when calculating fibonacci series

            //it’s performed two elements at a time

            //this is not a requirement

            int fib0 = 1;

            int fib1 = 1;

            int fib2 = 2;

            while (fib2 < 4000000)

            {

                //we know the fib2

                //is always even

                //and represents ALL

                //evens in the series

                //see the ‘proof’ below

                answer += fib2;

 

                //odd + even = odd

                fib0 = fib1 + fib2;

                //odd + even = odd

                fib1 = fib0 + fib2;

                //odd + odd = even

                fib2 = fib0 + fib1;

            }

 

            System.Console.WriteLine(answer);

        }

    }

}

Discussion

As I mentioned in the F# solution, an obvious optimization is to sum as you go.  I’ve also taken it a step further and removed the check for evenness because every third Fibonacci is even.  I layout a rough proof in my comments above.

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





Project Euler 002 – F#

7 02 2011

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

http://eulersolutions.com/2011/05/17/project-euler-002-f/





Project Euler 001 – JavaScript

5 02 2011

Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

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 001</title>

</head>

<body>

    <script type="text/javascript">

        //Add all the natural numbers below one

        //thousand that are multiples of 3 or 5.

        //this one is pretty similar to c#

        answer = 0

        for (three = 0; three < 1000; three += 3) { answer += three; }

        for (five = 0; five < 1000; five += 5) { answer += five; }

        for (fifteen = 0; fifteen < 1000; fifteen += 15)

          { answer -= fifteen; }

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

    </script>

</body>

</html>

 

Discussion

Last solution of the week.    Nothing too special here.

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