euler.js

/* Project Euler in Javascript
 * (Specifically Rhino JavaScript-C 1.6 2006-11-19)
 * John Evans <john@jpevans.com>
 *
 * To invoke:
 * "js euler.js"
 */


/* Euler #1
 * Answer: 233168
 *
 * 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.
 */
function euler1() {
    var n = 0;
    for (var i=0; i<1000; i++) {
        if ((i % 3 == 0)  || (i % 5 == 0)) {
            n += i;
        }
    }
    return n;
}

/* Euler #2
 * Answer: 4613732
 * 
 * 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, ...
 *
 * Find the sum of all the even-valued terms in the sequence which do not
 * exceed four million.
 */
function euler2() {
    var a = 1, b = 2, n = 2;
    while (true) {
        var c = a + b;
        if (c >= 4000000) {
            break;
        }
        if (c % 2 == 0) {
            n += c;
        }
        a = b;
        b = c;
    }
    return n;
}


// Euler #3:
// Answer: 6857
//
// The prime factors of 13195 are 5, 7, 13 and 29.
//
// What is the largest prime factor of the number 600851475143 ?

function is_prime(n) {
    for (var i=Math.ceil(Math.sqrt(n)); i>2; i--) {
        if (n % i == 0) {
            return false
        }
    }
    return true;
}

function euler3() {
    const target = 600851475143;
    for (var i=Math.ceil(Math.sqrt(target)); i>2; i--) {
        if ((target % i == 0) && is_prime(i)) {
            return i;
        }
    }
    return -1;
}


// Problem #4
// Answer: 906609
//
// 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.

function reverse_string(s) {
    return s.split("").reverse().join("");
}

function is_palindromic_number(n) {
    var s = "" + n;
    return s == reverse_string(s);
}

function euler4() {
    var result = 0;
    for (var i=100; i<1000; i++) {
        for (var j=100; j<1000; j++) {
            var p = i * j;
            if (p > result && is_palindromic_number(p)) {
                result = p;
            }
        }
    }
    return result;
}

// Problem #5
// Answer: 232792560
// Slow: 3m18s.
//
// 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 number that is evenly divisible by all of the
// numbers from 1 to 20?

function lcm(a, b)
{
    for (var i=1;; i++) {
        if ((i % a == 0) && (i % b == 0)) {
            return i;
        }
    }
}

function euler5() {
    var result = lcm(1, 2);
    for (var i=2; i<=20; i++) {
        result = lcm(result, i);
    }
    return result;
}


// Problem #6
// Answer: 25164150
//
// The sum of the squares of the first ten natural numbers is,
//     1² + 2² + ... + 10² = 385
// The square of the sum of the first ten natural numbers is,
//     (1 + 2 + ... + 10)² = 55² = 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.

function euler6() {
    var sum = 0;
    var sum_sq = 0;
    for (var i=1; i<=100; i++) {
        sum = sum + i;
        sum_sq = sum_sq + (i * i);
    }
    return (sum * sum) - sum_sq;
}


// Problem #7
// Answer: 104743
//
// 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?

function euler7() {
    var n = 2;
    var primes = [];
    for (;;) {
        var is_prime = true;
        for (var i=0; i<primes.length; i++) {
            var v = primes[i];
            if (n % v == 0) {
                is_prime = false;
                break
            }
        }
        if (is_prime) {
            if (primes.length >= 10000) {
                return n;
            }
            primes.push(n);
        }
        n = n + 1;
    }
}


// "Main"

EULERS = [
    euler1,
    euler2,
    euler3,
    euler4,
    euler5,
    euler6,
    euler7,
];

if (arguments.length > 0) {
    for (index in arguments) {
        var n = arguments[index]
        print(n + ": " + EULERS[n-1]());
    }
} else {
    for (var i=0, len = EULERS.length; i<len; i++) {
        print(i + ": " + EULERS[i]());
    }
}