/** * projectEuler.js * http://code.google.com/p/mathjs/ * * License: Creative Commons Attribution-Share Alike 3.0 Unported. * http://creativecommons.org/licenses/by-sa/3.0/ * * @projectDescription The solution to Project Euler using ECMAscript. * @author Rolando Garza rolandog@gmail.com */ /*global ActiveXObject: true, window: true, XMLHttpRequest: true, alert: true, confirm: true */ "use strict"; /** * An array containing proposed algorithms for solving Project Euler problems. */ var http = { /** * Gets a file and calls a function. * @param(Number) a A Number. */ get: function get(url) { var AJAX; if (window.XMLHttpRequest) { AJAX = new XMLHttpRequest(); } else { AJAX = new ActiveXObject("Microsoft.XMLHTTP"); } if (AJAX) { AJAX.open("GET", url, false); AJAX.send(null); return AJAX.responseText; } else { return false; } }, /** * Adds a function to the onload event. * @param(Function) f A Function. */ onLoad: function onLoad(f) { var old = window.onload; if (typeof(old) !== 'function') { window.onload = f; } else { window.onload = function () { old(); f(); }; } } }, pEProblems = [ "If we list all the natural numbers below 10 that are multiples of 3 or 5, we \nget 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the \nmultiples of 3 or 5 below 1000.", "Each new term in the Fibonacci sequence is generated by adding the previous \ntwo terms. By starting with 1 and 2, the first 10 terms will be:\n\n1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...\n\nFind the sum of all the even-valued terms in the sequence which do not exceed \nfour million.", "The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime \nfactor of the number 600851475143 ?", "A palindromic number reads the same both ways. The largest palindrome made from \nthe product of two 2-digit numbers is 9009 = 91 * 99. Find the largest \npalindrome made from the product of two 3-digit numbers.", "2520 is the smallest number that can be divided by each of the numbers from \n1 to 10 without any remainder. What is the smallest number that is evenly \ndivisible by all of the numbers from 1 to 20?", "The sum of the squares of the first ten natural numbers is, 1^2 + 2^2 + ...\n+ 10^2 = 385. The square of the sum of the first ten natural numbers is, (1 +\n2 + ... + 10)^2 = 55^2 = 3025. Hence the difference between the sum of the \nsquares of the first ten natural numbers and the square of the sum is 3025 - 385\n= 2640. Find the difference between the sum of the squares of the first one \nhundred natural numbers and the square of the sum.", "By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see \nthat the 6th prime is 13. What is the 10001st prime number?", "Find the greatest product of five consecutive digits in the 1000-digit number.", "A Pythagorean triplet is a set of three natural numbers, a < b < c, for which, \na^2 + b^2 = c^2. For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2. There exists \nexactly one Pythagorean triplet for which a + b + c = 1000. \nFind the product abc.", "The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the \nprimes below two million.", "In the 20x20 grid below, four numbers along a diagonal line have been marked \nin red. The product of these numbers is 26 * 63 * 78 * 14 = 1788696. What is \nthe greatest product of four adjacent numbers in any direction (up, down, left, \nright, or diagonally) in the 20x20 grid?", "The sequence of triangle numbers is generated by adding the natural numbers. \nSo the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first \nten terms would be: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... Let us list the \nfactors of the first seven triangle numbers:\n\n 1: 1 \n 3: 1,3\n 6: 1,2,3,6\n10: 1,2,5,10\n15: 1,3,5,15\n21: 1,3,7,21\n28: 1,2,4,7,14,28\n\nWe can see that 28 is the first triangle number to have over five divisors. What \nis the value of the first triangle number to have over five hundred divisors?", "Work out the first ten digits of the sum of the following one-hundred 50-digit\n numbers.", "The following iterative sequence is defined for the set of positive integers: \n\nn = n/2 (n is even); n = 3n + 1 (n is odd). \n\nUsing the rule above and starting with 13, we generate the following sequence: \n\n13 40 20 10 5 16 8 4 2 1 \n\nIt can be seen that this sequence (starting at 13 and finishing at 1) contains \n10 terms. Although it has not been proved yet (Collatz Problem), it is thought \nthat all starting numbers finish at 1. Which starting number, under one million, \nproduces the longest chain? NOTE: Once the chain starts the terms are allowed \nto go above one million.", "Starting in the top left corner of a 2x2 grid, there are 6 routes (without \nbacktracking) to the bottom right corner. How many routes are there through a \n20x20 grid?", "2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26. What is the \nsum of the digits of the number 2^1000?", "If the numbers 1 to 5 are written out in words: one, two, three, four, five, \nthen there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total. If all the numbers \nfrom 1 to 1000 (one thousand) inclusive were written out in words, how many \nletters would be used?\nNOTE: Do not count spaces or hyphens. For example, 342 \n(three hundred and forty-two) contains 23 letters and 115 (one hundred and \nfifteen) contains 20 letters. The use of 'and' when writing out numbers is in \ncompliance with British usage.", "Find the maximum total from top to bottom of the triangle below:\n\n75\n95 64\n17 47 82\n18 35 87 10\n20 04 82 47 65\n19 01 23 75 03 34\n88 02 77 73 07 63 67\n99 65 04 28 06 16 70 92\n41 41 26 56 83 40 80 70 33\n41 48 72 33 47 32 37 16 94 29\n53 71 44 65 25 43 91 52 97 51 14\n70 11 33 28 77 73 17 78 39 68 17 57\n91 71 52 38 17 14 91 43 58 50 27 29 48\n63 66 04 68 89 53 67 30 73 16 69 87 40 31\n04 62 98 27 23 09 70 98 73 93 38 53 60 04 23", "You are given the following information, but you may prefer to do some research \nfor yourself. 1 Jan 1900 was a Monday. Thirty days has September, April, June \nand November. All the rest have thirty-one, Saving February alone, Which has \ntwenty-eight, rain or shine. And on leap years, twenty-nine. A leap year occurs \non any year evenly divisible by 4, but not on a century unless it is divisible \nby 400. How many Sundays fell on the first of the month during the twentieth \ncentury (1 Jan 1901 to 31 Dec 2000)?", "n! means n * (n * 1) ... * 3 * 2 * 1. Find the sum of the digits in the number \n100!", "Let d(n) be defined as the sum of proper divisors of n (numbers less than n \nwhich divide evenly into n). If d(a) = b and d(b) = a, where a !== b, then a and \nb are an amicable pair and each of a and b are called amicable numbers. For \nexample, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and \n110 Therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; \nso d(284) = 220. Evaluate the sum of all the amicable numbers under 10000.", "Using names.txt (right click and 'Save Link/Target As...'), a 46K text file \ncontaining over five-thousand first names, begin by sorting it into alphabetical \norder. Then working out the alphabetical value for each name, multiply this \nvalue by its alphabetical position in the list to obtain a name score. For \nexample, when the list is sorted into alphabetical order, COLIN, which is worth \n3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain \na score of 938 * 53 = 49714. What is the total of all the name scores in the \nfile?", "A perfect number is a number for which the sum of its proper divisors is exactly \nequal to the number. For example, the sum of the proper divisors of 28 would be \n1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number. A number whose \nproper divisors are less than the number is called deficient and a number whose \nproper divisors exceed the number is called abundant. As 12 is the smallest \nabundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written \nas the sum of two abundant numbers is 24. By mathematical analysis, it can be \nshown that all integers greater than 28123 can be written as the sum of two \nabundant numbers. However, this upper limit cannot be reduced any further \nby \nanalysis even though it is known that the greatest number that cannot be \nexpressed as the sum of two abundant numbers is less than this limit. Find the \nsum of all the positive integers which cannot be written as the sum of two \nabundant numbers.", "A permutation is an ordered arrangement of objects. For example, 3124 is one \npossible permutation of the digits 1, 2, 3 and 4. If all of the permutations are \nlisted numerically or alphabetically, we call it lexicographic order. The \nlexicographic permutations of 0, 1 and 2 are:\n\n012 021 102 120 201 210\n\nWhat is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, \n6, 7, 8 and 9?", "What is the first term in the Fibonacci sequence to contain 1000 digits?", "A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:1/2 = 0.5\n1/3 = 0.(3)\n1/4 = 0.25\n1/5 = 0.2\n1/6 = 0.1(6)\n1/7 = 0.(142857)\n1/8 = 0.125\n1/9 = 0.(1)\n1/10 = 0.1\n\nWhere 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.\nFind the value of d 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.", "Euler published the remarkable quadratic formula:\n\nn² + n + 41\n\nIt turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.\n\nUsing computers, the incredible formula n² 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, 79 and 1601, is 126479.\n\nConsidering quadratics of the form:\n\nn² + an + b, where |a| 1000 and |b| 1000\n\nwhere |n| is the modulus/absolute value of n\ne.g. |11| = 11 and |4| = 4\nFind the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.", "Starting with the number 1 and moving to the right in a clockwise direction a \n5 by 5 spiral is formed as follows:\n\n21 22 23 24 25\n20 7 8 9 10\n19 6 1 2 11\n18 5 4 3 12\n17 16 15 14 13\n\nIt can be verified that the sum of the numbers on the diagonals is 101.\n\nWhat is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?", "Consider all integer combinations of a^b for 2<=a<=5 and 2<=b<=5:\n\n2^2=4, 2^3=8, 2^4=16, 2^5=32\n3^2=9, 3^3=27, 3^4=81, 3^5=243\n4^2=16, 4^3=64, 4^4=256, 4^5=1024\n5^2=25, 5^3=125, 5^4=625, 5^5=3125\nIf they are then placed in numerical order, with any repeats removed, we get \nthe following sequence of 15 distinct terms:\n\n4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125\n\nHow many distinct terms are in the sequence \ngenerated by a^b for 2 <= a <= 100 and 2 <= b <= 100?", "Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:\n\n1634 = 1^4 + 6^4 + 3^4 + 4^4\n8208 = 8^4 + 2^4 + 0^4 + 8^4\n9474 = 9^4 + 4^4 + 7^4 + 4^4\nAs 1 = 1^4 is not a sum it is not included.\n\nThe sum of these numbers is 1634 + 8208 + 9474 = 19316.\n\nFind the sum of all the numbers that can be written as the sum of fifth powers of their digits.", 31, 32, "The fraction 49/98 is a curious fraction, as an inexperienced mathematician in \nattempting to simplify it may incorrectly believe that 49/98 = 4/8, which is \ncorrect, is obtained by cancelling the 9s.\n\nWe shall consider fractions like, 30/50 = 3/5, to be trivial examples.\n\nThere are exactly four non-trivial examples of this type of fraction, less than \none in value, and containing two digits in the numerator and denominator.\n\nIf the product of these four fractions is given in its lowest common terms, find \nthe value of the denominator.", 34, "The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.\n\nThere are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.\n\nHow many circular primes are there below one million?", "The decimal number, 585 = 1001001001 (binary), is palindromic in both bases.\n\nFind the sum of all numbers, less than one million, which are palindromic in base 10 and base 2", 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, "The series, 1^1 + 2^2 + 3^3 + ... + 10^10 = 10405071317.\nFind the last ten digits of the series, 1^1 + 2^2 + 3^3 + ... + 1000^1000.", undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, "Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows." ], projectEuler = [ function Problem_1() { var multiples = [], i; for (i = 0; i < 1000; i += 1) { if (i % 3 === 0 || i % 5 === 0) { multiples.push(i); } } return Math.sum(multiples); }, function Problem_2() { var fib = Math.fibonacci(4000000), s = 0, i, l = fib.length; for (i = 0; i < l; i += 1) { if (fib[i] % 2 === 0) { s += fib[i]; } } return s; }, function Problem_3() { var r = Math.factors(600851475143); return r.pop(); }, function Problem_4() { var i = 101, j, palindromes = [], m = Math, ascending = m.js.ascending, ij; function isPalindrome(a) { a = "" + a; var l = a.length, k = 0, fl = m.floor, lim = fl(l / 2); do { if (a.charAt(k) !== a.charAt(l - 1 - k)) { return false; } k += 1; } while (k < lim); return true; } do { j = 101; do { ij = i * j; if (isPalindrome(ij)) { palindromes.push(ij); } j += 1; } while (j <= 999); i += 1; } while (i <= 999); return palindromes.sort(ascending).pop(); }, function Problem_5() { var i, n = []; for (i = 20; i > 0; i -= 1) { n.push(i); } return Math.lcm(n); }, function Problem_6() { var i = 1, ns = 0, sqs = 0; do { ns += i; sqs += i * i; i += 1; } while (i <= 100); return ns * ns - sqs; }, function Problem_7() { var primes = [2], i = 3, l = 1, isPrime = Math.isPrime; do { if (isPrime(i)) { l = primes.push(i); } i += 2; } while (l < 10001); return primes[10000]; }, function Problem_8() { var n, i = 0, max = 0, l, c; n = "73167176531330624919225119674426574742355349194934"; n += "96983520312774506326239578318016984801869478851843"; n += "85861560789112949495459501737958331952853208805511"; n += "12540698747158523863050715693290963295227443043557"; n += "66896648950445244523161731856403098711121722383113"; n += "62229893423380308135336276614282806444486645238749"; n += "30358907296290491560440772390713810515859307960866"; n += "70172427121883998797908792274921901699720888093776"; n += "65727333001053367881220235421809751254540594752243"; n += "52584907711670556013604839586446706324415722155397"; n += "53697817977846174064955149290862569321978468622482"; n += "83972241375657056057490261407972968652414535100474"; n += "82166370484403199890008895243450658541227588666881"; n += "16427171479924442928230863465674813919123162824586"; n += "17866458359124566529476545682848912883142607690042"; n += "24219022671055626321111109370544217506941658960408"; n += "07198403850962455444362981230987879927244284909188"; n += "84580156166097919133875499200524063689912560717606"; n += "05886116467109405077541002256983155200055935729725"; n += "71636269561882670428252483600823257530420752963450"; n = n.split(""); l = n.length; do { n[i] = +n[i]; i += 1; } while (i < l); i = 0; do { c = n[i] * n[i + 1] * n[i + 2] * n[i + 3] * n[i + 4]; max = max < c ? c : max; i += 1; } while (i < l - 4); return max; }, function Problem_9() { var a, b, c = 400; do { b = 300; do { a = 100; do { if (a * a + b * b === c * c && a + b + c === 1000) { return a * b * c; } a += 1; } while (a < b); b += 1; } while (b < c); c += 1; } while (c < 500); }, function Problem_10() { var m = Math, p = m.primes, l = m.howManyPrimes, nP = m.nextPrime, i, j; i = p[l - 1]; j = 0; if (i < 2000000) { j = m.sum(m.primes) - i; while (i < 2000000) { j += i; i = nP(); } } else { j = m.sum(p.slice(0, p.lessThan(2000000) + 1)); } return j; }, function Problem_11() { var a = [ [8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8], [49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62, 0], [81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65], [52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 36, 91], [22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80], [24, 47, 32, 60, 99, 3, 45, 2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50], [32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70], [67, 26, 20, 68, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21], [24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72], [21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95], [78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92], [16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57], [86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58], [19, 80, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 40], [4, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66], [88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69], [4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36], [20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 4, 36, 16], [20, 73, 35, 29, 78, 31, 90, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54], [1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48] ], j, i = 0, m = 0, c; do { j = 0; do { if (j < 17) { c = a[i][j] * a[i][j + 1] * a[i][j + 2] * a[i][j + 3]; m = m < c ? c : m; } if (j < 17 && i >= 3) { c = a[i][j] * a[i - 1][j + 1] * a[i - 2][j + 2] * a[i - 3][j + 3]; m = m < c ? c : m; } if (i >= 3) { c = a[i][j] * a[i - 1][j] * a[i - 2][j] * a[i - 3][j]; m = m < c ? c : m; } if (i >= 3 && j >= 3) { c = a[i][j] * a[i - 1][j - 1] * a[i - 2][j - 2] * a[i - 3][j - 3]; m = m < c ? c : m; } if (j >= 3) { c = a[i][j] * a[i][j - 1] * a[i][j - 2] * a[i][j - 3]; m = m < c ? c : m; } if (j >= 3 && i < 17) { c = a[i][j] * a[i + 1][j - 1] * a[i + 2][j - 2] * a[i + 3][j - 3]; m = m < c ? c : m; } if (i < 17) { c = a[i][j] * a[i + 1][j] * a[i + 2][j] * a[i + 3][j]; m = m < c ? c : m; } if (i < 17 && j < 17) { c = a[i][j] * a[i + 1][j + 1] * a[i + 2][j + 2] * a[i + 3][j + 3]; m = m < c ? c : m; } j += 1; } while (j < 20); i += 1; } while (i < 20); return m; }, function Problem_12() { var i = 2, d, l, md = Math.divisors, t; do { t = i * (i + 1) / 2; d = md(t); l = d.length; i += 1; } while (l < 500); return t; }, function Problem_13() { var numbers = [ 37107287533902102798797998220837590246510135740250, 46376937677490009712648124896970078050417018260538, 74324986199524741059474233309513058123726617309629, 91942213363574161572522430563301811072406154908250, 23067588207539346171171980310421047513778063246676, 89261670696623633820136378418383684178734361726757, 28112879812849979408065481931592621691275889832738, 44274228917432520321923589422876796487670272189318, 47451445736001306439091167216856844588711603153276, 70386486105843025439939619828917593665686757934951, 62176457141856560629502157223196586755079324193331, 64906352462741904929101432445813822663347944758178, 92575867718337217661963751590579239728245598838407, 58203565325359399008402633568948830189458628227828, 80181199384826282014278194139940567587151170094390, 35398664372827112653829987240784473053190104293586, 86515506006295864861532075273371959191420517255829, 71693888707715466499115593487603532921714970056938, 54370070576826684624621495650076471787294438377604, 53282654108756828443191190634694037855217779295145, 36123272525000296071075082563815656710885258350721, 45876576172410976447339110607218265236877223636045, 17423706905851860660448207621209813287860733969412, 81142660418086830619328460811191061556940512689692, 51934325451728388641918047049293215058642563049483, 62467221648435076201727918039944693004732956340691, 15732444386908125794514089057706229429197107928209, 55037687525678773091862540744969844508330393682126, 18336384825330154686196124348767681297534375946515, 80386287592878490201521685554828717201219257766954, 78182833757993103614740356856449095527097864797581, 16726320100436897842553539920931837441497806860984, 48403098129077791799088218795327364475675590848030, 87086987551392711854517078544161852424320693150332, 59959406895756536782107074926966537676326235447210, 69793950679652694742597709739166693763042633987085, 41052684708299085211399427365734116182760315001271, 65378607361501080857009149939512557028198746004375, 35829035317434717326932123578154982629742552737307, 94953759765105305946966067683156574377167401875275, 88902802571733229619176668713819931811048770190271, 25267680276078003013678680992525463401061632866526, 36270218540497705585629946580636237993140746255962, 24074486908231174977792365466257246923322810917141, 91430288197103288597806669760892938638285025333403, 34413065578016127815921815005561868836468420090470, 23053081172816430487623791969842487255036638784583, 11487696932154902810424020138335124462181441773470, 63783299490636259666498587618221225225512486764533, 67720186971698544312419572409913959008952310058822, 95548255300263520781532296796249481641953868218774, 76085327132285723110424803456124867697064507995236, 37774242535411291684276865538926205024910326572967, 23701913275725675285653248258265463092207058596522, 29798860272258331913126375147341994889534765745501, 18495701454879288984856827726077713721403798879715, 38298203783031473527721580348144513491373226651381, 34829543829199918180278916522431027392251122869539, 40957953066405232632538044100059654939159879593635, 29746152185502371307642255121183693803580388584903, 41698116222072977186158236678424689157993532961922, 62467957194401269043877107275048102390895523597457, 23189706772547915061505504953922979530901129967519, 86188088225875314529584099251203829009407770775672, 11306739708304724483816533873502340845647058077308, 82959174767140363198008187129011875491310547126581, 97623331044818386269515456334926366572897563400500, 42846280183517070527831839425882145521227251250327, 55121603546981200581762165212827652751691296897789, 32238195734329339946437501907836945765883352399886, 75506164965184775180738168837861091527357929701337, 62177842752192623401942399639168044983993173312731, 32924185707147349566916674687634660915035914677504, 99518671430235219628894890102423325116913619626622, 73267460800591547471830798392868535206946944540724, 76841822524674417161514036427982273348055556214818, 97142617910342598647204516893989422179826088076852, 87783646182799346313767754307809363333018982642090, 10848802521674670883215120185883543223812876952786, 71329612474782464538636993009049310363619763878039, 62184073572399794223406235393808339651327408011116, 66627891981488087797941876876144230030984490851411, 60661826293682836764744779239180335110989069790714, 85786944089552990653640447425576083659976645795096, 66024396409905389607120198219976047599490197230297, 64913982680032973156037120041377903785566085089252, 16730939319872750275468906903707539413042652315011, 94809377245048795150954100921645863754710598436791, 78639167021187492431995700641917969777599028300699, 15368713711936614952811305876380278410754449733078, 40789923115535562561142322423255033685442488917353, 44889911501440648020369068063960672322193204149535, 41503128880339536053299340368006977710650566631954, 81234880673210146739058568557934581403627822703280, 82616570773948327592232845941706525094512325230608, 22918802058777319719839450180888072429661980811197, 77158542502016545090413245809786882778948721859617, 72107838435069186155435662884062257473692284509516, 20849603980134001723930671666823555245252804609722, 53503534226472524250874054075591789781264330331690 ], m = Math, s = m.sum(numbers), p = m.ceil(m.log(s) / m.LN10); return m.floor(s / m.pow(10, p - 10)); }, function Problem_14() { function sequence(n) { var l = 1; if (n === 1) { return l; } do { switch (n % 2) { case 0: n /= 2; l += 1; break; case 1: n = 3 * n + 1; l += 1; break; } } while (n !== 1); return l; } var i = 13, maxl = 0, a, maxn = 0; do { a = sequence(i); if (a > maxl) { maxl = a; maxn = i; } i += 1; } while (i < 1000000); return maxn; }, function Problem_15() { var size = 20, limit, m = Math, factorial = m.factorial, pow = m.pow; limit = factorial(2 * size) / pow(factorial(size), 2); return limit; }, function Problem_16() { var m = Math, sum = m.bigInt.sum, pow = m.bigInt.pow; return sum(pow(2, 1000).split("")); }, function Problem_17() { var i, r = "", m = Math; for (i = 1; i <= 1000; i += 1) { r += m.toText(i).replace(/\W/g, ""); } return r.length; }, function Problem_18() { var i, j, k, sampleSize = 6, tarray, total = 0, triangle = "75\n95 64\n17 47 82\n18 35 87 10\n20 04 82 47 65\n19 01 23 75 03 34\n88 02 77 73 07 63 67\n99 65 04 28 06 16 70 92\n41 41 26 56 83 40 80 70 33\n41 48 72 33 47 32 37 16 94 29\n53 71 44 65 25 43 91 52 97 51 14\n70 11 33 28 77 73 17 78 39 68 17 57\n91 71 52 38 17 14 91 43 58 50 27 29 48\n63 66 04 68 89 53 67 30 73 16 69 87 40 31\n04 62 98 27 23 09 70 98 73 93 38 53 60 04 23"; triangle = triangle.split("\n"); for (i in triangle) { if (triangle.hasOwnProperty(i) && triangle[i]) { triangle[i] = triangle[i].split(" "); for (j in triangle[i]) { if (triangle[i].hasOwnProperty(j) && triangle[i][j]) { triangle[i][j] = +triangle[i][j]; } } } } function sample(array, depth, index, limit) { limit = depth + limit > array.length ? array.length - depth:limit; var temp = []; while (limit) { limit -= 1; temp.push(array[depth + limit].slice(index, index + limit + 1)); } return temp.reverse(); } function findTotals(object, i, j) { i = i === undefined ? 0 : i; j = j === undefined ? 0 : j; var results = {}, subResult0 = {}, subResult1 = {}, r; if (i < object.length - 1) { subResult0 = findTotals(object, i + 1, j); subResult1 = findTotals(object, i + 1, j + 1); for (r in subResult0) { if (subResult0.hasOwnProperty(r) && subResult0[r]) { results["0" + r] = object[i][j] + subResult0[r]; results["1" + r] = object[i][j] + subResult1[r]; } } return results; } else { return {"": object[i][j]}; } } function findMax(object) { var tname, tmax = 0, n; for (n in object) { if (object.hasOwnProperty(n) && object[n] && object[n] > tmax) { tmax = object[n]; tname = n; } } return [tname, tmax]; } i = 0; j = 0; k = Math.ceil(triangle.length / sampleSize); while (k) { tarray = findMax(findTotals(sample(triangle, i, j, sampleSize))); total += tarray[1]; i += sampleSize; j += tarray[0].split("1").length - 1; if (triangle[i] !== undefined) { j += triangle[i][j + 1] > triangle[i][j] ? 1 : 0; } k -= 1; } return total; //Brute force //return findMax(findTotals(triangle))[1]; }, function Problem_19() { var i, j, c = 0; for (i = 1901; i <= 2000; i += 1) { for (j = 1; j <= 12; j += 1) { c += new Date("" + i + "/" + j + "/1").getDay() === 0 ? 1 : 0; } } return c; }, function Problem_20() { var i = 0, m = Math, a = m.bigInt.factorial(100).split(""), al = a.length; do { a[i] = +a[i]; i += 1; } while (i < al); return m.sum(a); }, function Problem_21() { function d(n) { var m = Math; return m.sum(m.divisors(n, true)); } function amicable(a) { var b = d(a); if (d(b) === a && a !== b) { return true; } return false; } var c = [], i; for (i = 1; i < 10000; i += 1) { if (amicable(i)) { c.push(i); } } return Math.sum(c); }, function Problem_22() { var names = http.get("names.txt"), i, score = 0; function p(a) { return "ABCDEFGHIJKLMNOPQRSTUVWXYZ".indexOf(a); } function v(a) { return a.length - 1 ? 1 + p(a.charAt(0)) + v(a.slice(1)) : 1 + p(a); } names.replace(/"/g, ''); names = names.split(",").sort(); for (i = 0; i < names.length; i += 1) { score += v(names[i]) * (i + 1); } return score; }, function Problem_23() { var abundant = [12], i = 1, h = 0, j = 12, k, l = 1, s = [], t, m = Math, sum = m.sum, d = m.divisors, a; do { if (i > j) { //if our number is greater than the cache, initially 12 a = i; do { if (sum(d(a, true)) - a > 0) { //if the sum of the divisors is greater than i abundant.push(a); //then it is abundant l += 1; break; } a += 1; } while (a < 28123); j = a; // next abundant so that i <= j is true } if (l - 1) {//when we start using something greater than 12 as reference k = l / 2 | 0; //good starting point for the guess t = true; do { if (abundant.indexOf(i - abundant[k]) > -1) { t = false; break; //stops the iterations, since we've found a compliment } k += 1; } while (k < l); if (t) { s.push(i); //pushes numbers that had no compliments } } else { s.push(i); //will push numbers 1 - 12 } i += 1; //post increment, to prevent testing of i = 28123 } while (i < 28123); return sum(s); }, function Problem_24() { return [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].permutations(999999).join(""); }, function Problem_25() { var a = "1", b = "1", c = "2", i = 3, sum = Math.bigInt.sum, l = "1"; while (l < 1000) { a = b; b = c; c = sum(a, b); l = c.length; i += 1; } return i; }, function Problem_26() { var d, r = "", rs = [], maxR = 1, dR = Math.decimalRepresentation; for (d = 1; d < 1000; d += 1) { r = dR(1, d); rs.push(r); maxR = r.length > rs[maxR - 1].length ? d : maxR; } return maxR; }, function Problem_27() { var n, a, b, ai = 0, bi = 0, m = 0, am, bm, ca, bc, ac, M = Math, p = M.isPrime, is, lb, la, r, c; p(1000001); bc = M.primes.slice(0, M.primes.lessThan(1000) + 1).reverse(); ac = M.between(1, 1000); ac = ac.negative().concat(ac); la = ac.length - 1; lb = bc.length - 1; do { b = bc[bi]; ai = 0; do { n = 0; c = 0; a = ac[ai]; do { ca = n * n + a * n + b; n += 1; c += 1; is = p(ca); } while (is); if (c > m) { m = c; am = a; bm = b; r = a * b; } ai += 1; } while (ai < la); bi += 1; } while (bi < lb); return "(" + m + ") " + am + " * " + bm + " = " + r; }, function Problem_28() { /* * l is the array length, then used as the limit * n is first used as a counter, then is used as the spiral number. * m is the very middle of the array, and a direction helper * c & d are the array indexes * e & f are the direction indicators (+1, 0 or -1) */ var l = 1001, n = l, a = new Array(l), m = l / 2 | 0, c, d, e, f; //creating our array of arrays do { a[n - 1] = new Array(l); n -= 1; } while (n); //setting the first value to 1, as well the direction for the spiral //sets n to 1, the middle [m, m] to n, f to 1, e to 0 e = (f = (a[m][m] = (n = 1))) - 1; //sets c and d to start at the middle d = (c = m); //the limit l *= l; //fill the array! do { //join e and f to determine direction and if other values exist switch (e + "" + f) { case "10": e = (!a[c][d - 1]) ? 0: e; f = (!a[c][d - 1]) ? -1: f; break; case "0-1": e = (!a[c - 1][d]) ? -1: e; f = (!a[c - 1][d]) ? 0: f; break; case "-10": e = (!a[c][d + 1]) ? 0: e; f = (!a[c][d + 1]) ? 1: f; break; case "01": e = (!a[c + 1][d]) ? 1: e; f = (!a[c + 1][d]) ? 0: f; break; } c += e; d += f; a[c][d] = (n += 1); } while (n !== l); n = (c = 0); d = (l = a.length) - 1; do { n += a[c][c]; n += (c === m && d === m) ? 0 : a[c][d]; c += 1; d -= 1; } while (c < l); return n; }, function Problem_29() { function rep(a, b) { var c = a; b -= 1; do { c = c.concat(a); b -= 1; } while (b); return c.sort(); } var l = 100, a = l, b, d = [], f = Math.factors; do { b = l; do { d.push(rep(f(a), b).join('*')); b -= 1; } while (b - 1); a -= 1; } while (a - 1); return d.unique().length; }, function Problem_30() { /* i is the lower limit; the upper limit, l, is where a number 'n', made out of 9's, is equal * to or bigger than the sum of each 9 to the 5th power. * m is the number split into an array; n, a counter. * s is the sum, and p is the cached form of numbers 0-9 ^ 5 */ var i = 2, l = 354294, m, n, s, r = 0, p = { "0": 0, "1": 1, "2": 32, "3": 243, "4": 1024, "5": 3125, "6": 7776, "7": 16807, "8": 32768, "9": 59049 }; do { s = 0; n = (m = ("" + i).split("")).length - 1; //i = 123; m = ['1', '2', '3']; n = 2; do { s += p[m[n]]; n -= 1; } while (n + 1); //the sum of each number to the 5th power if (s === i) { r += i; } i += 1; } while (i < l); return r; }, undefined, undefined, function Problem_33() { var a, a0, a1, b, b0, b1, c, c00, c01, c10, c11, n = [], d = []; a = 10; do { b = a + 1; do { a0 = +(a + "")[0]; a1 = +(a + "")[1]; b0 = +(b + "")[0]; b1 = +(b + "")[1]; c = a / b; c00 = a0 / b0 === c && a1 === b1; c01 = a0 / b1 === c && a1 === b0; c10 = a1 / b0 === c && a0 === b1; c11 = a1 / b1 === c && a0 === b0; if (a1 + b1) { if ((c00 || c01) || (c10 || c11)) { n.push(a); d.push(b); } } b += 1; } while (b < 99); a += 1; } while (a < 98); //16,19,26,49 / 64,95,65,98 return d; }, function Problem_34() { function separate(a) { var b = ('' + a).split(''), l = b.length; do { l -= 1; b[l] = +b[l]; } while (l); return b; //splits 123 into [1, 2, 3] } function factorial(n) { if (!n) { return 1; } if (!(n - 1)) { return 1; } if (!(n - 2)) { return 2; } if (!(n - 3)) { return 6; } if (!(n - 4)) { return 24; } if (!(n - 5)) { return 120; } if (!(n - 6)) { return 720; } if (!(n - 7)) { return 5040; } if (!(n - 8)) { return 40320; } if (!(n - 9)) { return 362880; } } function isCurious(n) { var a = separate(n), b = 0, l = a.length; do { l -= 1; b += factorial(a[l]); } while (l); return b === n; } var i = 3000000, s = 0; do { i -= 1; if (isCurious(i)) { s += i; } } while (i > 3); return s; }, function Problem_35() { var i = 0, m = Math, j = m.howManyPrimes, mnp = m.nextPrime, ps, r = 0; function isCircular(n) { //this function is inferring that n is already a prime var c = (n + "").split(""), l = c.length - 1, d = [], p = true, isPrime = Math.isPrime; if (l) { //if l isn't 0, proceed. do { c.push(c.shift()); // rotates 123 to 231 d.push(+(c.join(""))); //pushes the rotations into an array l -= 1; } while (l); l = d.length; do { l -= 1; //substracts from the counter p = p && isPrime(d[l]); //checks to see if it's a prime number } while (l && p);//if l=0 or any number isn't a prime number, break } return p; } mnp = m.nextPrime; do { j = mnp(); } while (j < 1000000); j = m.howManyPrimes; ps = m.primes; do { r += isCircular(ps[i]) ? 1 : 0; i += 1; } while (i < j); return r; }, function Problem_36() { var i = 999999, r = 0, p = function p(a) { var l, k = 0, lim; lim = (l = a.length) % 2 ? l - 1 : l; do { if (a.charAt(k) !== a.charAt(l - 1 - k)) { return false; } k += 1; } while (k < lim); return true; }; do { if (p(i + "")) { if (p(i.toString(2))) { r += i; } } i -= 2; } while (i > 0); return r; }, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, function Problem_48() { var r = 0, i = 1, m = Math.bigInt; do { r = m.sum(r, m.pow(i, i)); } while (i < 1000); return r.slice(r.length - 10); }, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, function Problem_67() { var i, j, triangle; triangle = http.get("triangle.txt").split("\n"); while (triangle[triangle.length - 1] === "") { triangle.pop(); } for (i in triangle) { if (triangle.hasOwnProperty(i) && triangle[i]) { triangle[i] = triangle[i].split(" "); for (j in triangle[i]) { if (triangle[i].hasOwnProperty(j) && triangle[i][j]) { triangle[i][j] = +triangle[i][j]; } } } } triangle.reverse(); for (i = 1; i < triangle.length; i += 1) { for (j = 0; j < triangle[i].length; j += 1) { triangle[i][j] += Math.max(triangle[i - 1][j], triangle[i - 1][j + 1]); } } return triangle.reverse()[0][0]; } ], answers, times; answers = [233168, 4613732, 6857, 906609, 232792560, 25164150, 104743, 40824, 31875000, 142913828922, 70600674, 76576500, 5537376230, 837799, 137846528820, 1366, 10881, 1074, 171, 648, 31626, 871198282, 4179871, 2783915460, 4782, 983, -59231, 669171001, 9183, 443839, undefined, undefined, undefined, 40730, 55, 872187, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, 9110846700, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, 7273]; times = [0, 0, 0, 151, 0, 0, 31, 2, 14, 1423, 1, 1844, 1, 4410, 0, 272, 67, 3, 104, 69, 593, 259, 1034792, 180000, 7830, 1000, 1974, 330, 2109, 2234, undefined, undefined, undefined, 4000, 10000, 143, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, 7425095, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, 27]; if (Math.js !== undefined) { Math.js.format = function format(t) { var u, r = Math.decimalRepresentation; if (t > 3600000) { t = r(t, 3600000); u = "hours"; } else if (t > 60000) { t = r(t, 60000); u = "minutes"; } else if (t > 1000) { t = r(t, 1000); u = "seconds"; } else { t = "" + t; u = "milliseconds"; } return [t, u]; }; Math.js.get = function Math_js_get(id) { return document.getElementById(id); }; Math.js.before = function Math_js_before(reference, node) { reference.parentNode.insertBefore(node, reference); }; Math.js.after = function Math_js_after(reference, node) { Math.js.before(reference.nextSibling, node); }; Math.js.remove = function Math_js_remove(node) { node.parentNode.removeChild(node); }; Math.js.next = function Math_js_next(reference) { Math.js.remove(reference.nextSibling); }; Math.js.text = function Math_js_text(b) { return document.createTextNode(b); }; Math.js.element = function Math_js_element(b) { return document.createElement(b); }; Math.js.append = function Math_js_append(b, c) { b.appendChild(c); }; Math.js.create = function Math_js_create(d, b, i) { var m = Math.js, r = m.element(d); if (i !== undefined) { r.id = i; } if (b !== undefined) { m.append(r, m.text(b)); } return r; }; } /** * Solves the selected problem. */ function solve(n) { var t0, t1, problem, answer, p, time, conf, s, f, format, t, e, a, c, m, g, units; //get the formating and DOM manipulating functions, to save space m = Math.js; e = m.element; a = m.append; c = m.create; t = m.text; g = m.get; f = m.format; //get the document area and clean it up p = document.getElementById("problem"); if (p) { p.parentNode.removeChild(p); } //check if it isn't an empty string as an argument, if not, make it a number if (n === "") { return false; } else if (typeof(n) === "string") { n = +n; } //get the function, and its answer and calculation times problem = projectEuler[n - 1]; answer = answers[n - 1]; time = times[n - 1]; //change the formating function into a string format = time !== undefined ? "takes " + f(time).join(" ") + ", more or less, on a 1.5 GHz laptop using Google Chrome. " : "might take a while. "; conf = time >= 4200 || time === undefined ? confirm("The algorithm " + format + "Do you want to run it anyway?\nIf you don't the answer will still be displayed, but you won't get that warm, fuzzy sensation of puting your own number-crunching computer to work.") : true; if (conf) { t0 = new Date(); answer = problem(); t1 = new Date(); time = f(t1 - t0)[0]; units = f(t1 - t0)[1]; } else { t0 = f(time); time = t0[0]; units = t0[1]; } p = c("p", undefined, "problem"); a(p, c("h3", "Problem: " + n)); a(p, c("pre", pEProblems[n - 1])); a(p, e("br")); a(p, c("strong", "Answer: ", "answer")); a(p, t(answer + ", ")); a(p, c("strong", "Time: ", "time")); a(p, t(time)); a(p, c("small", " " + units, "units")); a(p, t(".")); a(p, e("br")); a(p, c("pre", problem)); a(p, e("br")); s = g("solution"); a(s, p); } /** * Displays the chosen functions. */ function display(n) { var m = Math.js, Mf = m.functions, p, f, i, t, e, a, c, g, format; //get the formating and DOM manipulating functions, to save space e = m.element; a = m.append; c = m.create; t = m.text; g = m.get; format = m.format; p = g("function"); if (p) { m.remove(p); } for (i = 0; i < Mf.length; i += 1) { if (Mf[i].name === n) { f = Mf[i]; } } p = c("p", undefined, "function"); a(p, c("h3", "Function: " + f.name)); a(p, c("pre", f)); a(g("source"), p); } function populateLists() { var i, m = Math.js, g = m.get, r = m.remove, pl = g("plist"), fl = g("flist"), a = [], e, f, url; for (e in Math) { if (typeof(Math[e]) === "object") { for (f in Math[e]) { if (typeof(Math[e][f]) === "function") { a.push(Math[e][f]); } } } else if (typeof(Math[e]) === "function") { a.push(Math[e]); } } a.sort(); m.functions = a; function option(n, t) { var o = m.element("option"), txt = t + n; o.value = "" + n; txt = m.text(txt); m.append(o, txt); return o; } for (i = 0; i < projectEuler.length; i += 1) { if (projectEuler[i] !== undefined) { m.append(pl, option(i + 1, "Problem ")); } } if (a[0].name !== undefined) { for (i = 0; i < a.length; i += 1) { m.append(fl, option(a[i].name, "")); } } else { r(fl); r(g("flabel")); } function parseURL(url) { var fields = {'username' : 4, 'password' : 5, 'port' : 7, 'scheme' : 2, 'authority' : 6, 'path' : 8, 'url' : 0, 'query' : 9, 'fragment' : 10}, json = {}, parsed, p, q, queries; parsed = url.match(/^((\w+):\/\/)?((\w+):?(\w+)?@)?([^\/\?:]+):?(\d+)?(\/?[^\?#]+)?\??([^#]+)?#?(\w*)/); for (p in fields) { if (fields.hasOwnProperty(p) && parsed[fields[p]]) { json[p] = parsed[fields[p]]; } } if (json.query !== undefined) { queries = json.query.split("&"); json.query = {}; for (q in queries) { if (queries.hasOwnProperty(q) && queries[q]) { p = queries[q].split("="); json.query[p[0]] = p[1] !== undefined ? p[1] : null; } } } return json; } url = parseURL(document.location.href); if (url.query) { if (url.query.solve) { solve(url.query.solve); } if (url.query.display) { display(url.query.display); } } } http.onLoad(populateLists);