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





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





Project Euler 004–JavaScript

25 02 2011

Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

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

</head>

<body >

    <script type="text/javascript">

 

        function IsPalindrome(number)

        {

            numberStr = number.toString();

            // simple palindrome test

            // we only have to go through the first

            // half of the letters

            for (c = 0; c < numberStr.length-c; c++)

            {

                if (numberStr[c] !=

                    numberStr[numberStr.length-c-1]) {

                    return false;

                }

            }

            return true;

        }

 

        answer = 0

        //here’s a familiar loop

        for(i = 100; i < 1000; i++)

        {

            for(j = i; j < 1000; j++)

            {

                product = i*j;

                if ((product > answer)

                && IsPalindrome(product))

                { answer = product; }

            }

        }

 

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

    </script>

</body>

</html>

 

 

Discussion

Nothing too special here, but this is the one solution that didn’t use some sort of built in “reverse” function.  Still works.  Smile

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





Project Euler 003 – JavaScript

18 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

<!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 003</title>

</head>

<body >

    <script type="text/javascript">

 

        function PrimeFactor(number)

        {

            //here is our list of prime factors

            factors = new Array();

           

            //assume the number is prime

            //unless we find a factor

            isPrime = true;

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

            factorCandidate = Math.round(Math.sqrt(number), 0);

            while (factorCandidate > 1)

            {

                //is this a factor?

                if (number % factorCandidate == 0)

                {

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

                    divisor = number / factorCandidate;

                    factors.concat(PrimeFactor(factorCandidate));

                    factors.concat(PrimeFactor(divisor));

                    isPrime = false;

                }

                //next

                factorCandidate–;

            }

            //we are only adding prime factors

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

           

            return factors;

        }

 

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

 

        answer = factors[0];

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

    </script>

</body>

</html>

 

Discussion

Debugging JavaScript is not my forte.  The concat function was handy here, but I don’t think that JavaScript is going to get much better for me unless I spend some time getting better tools.

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





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