Skip to content

Instantly share code, notes, and snippets.

@kyle-wendling

kyle-wendling/jsbin.geki.html

Created February 10, 2014 20:55
Show Gist options
  • Save kyle-wendling/8923972 to your computer and use it in GitHub Desktop.
Save kyle-wendling/8923972 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
jsbin.geki.html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Project Eulertitle</title>
</head>
<body>
<button onclick="euler_one()">Try Euler One</button>
<p id="euler_one">Euler one answer is...</p>
<button onclick="euler_two()">Try Euler Two</button>
<p id="euler_two">Euler two answer is...</p>
<button onclick="euler_three()">Try Euler Three</button>
<p id="euler_three">Euler three answer is...</p>
<button onclick="euler_four()">Try Euler Four</button>
<p id="euler_four">Euler four answer is...</p>
<button onclick="euler_five()">Try Euler Five</button>
<p id="euler_five">Euler five answer is...</p>
<button onclick="euler_six()">Try Euler Six</button>
<p id="euler_six">Euler six answer is...</p>
<button onclick="euler_seven()">Try Euler 7</button>
<p id="euler_seven">Euler 7 answer is...</p>
<button onclick="euler_eight()">Try Euler 8</button>
<p id="euler_eight">Euler 8 answer is...</p>
<button onclick="euler_nine()">Try Euler 9</button>
<p id="euler_nine">Euler 9 answer is...</p>
<button onclick="euler_ten()">Try Euler 10</button>
<p id="euler_ten">Euler 10 answer is...</p>
<button onclick="euler_14()">Try Euler 14</button>
<p id="euler_14">Euler 14 answer is...</p>
<button onclick="euler_15()">Try Euler 15</button>
<p id="euler_15">Euler 15 answer is...</p>
<button onclick="euler_16()">Try Euler 16</button>
<p id="euler_16">Euler 16 answer is...</p>
<button onclick="euler_16()">Try Euler 16</button>
<p id="euler_18">Euler 16 answer is...</p>
<button onclick="euler_48()">Try Euler 48</button>
<p id="euler_48">Euler 48 answer is...</p>
</body>
</html>
Raw
jsbin.geki.js
//project euler - Kyle Wendling
/*
Multiples of 3 and 5
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.
*/
//woo right on first try
function euler_one()
{
var x=5;
var y=3;
var count_to = 1000;
var answer=1;
for(i=1;i<count_to;i++) {
if(i%3 === 0 || i%5 === 0) {
answer += i;
}
}
document.getElementById("euler_one").innerHTML+=answer;
return answer;
}
/*
Even Fibonacci numbers
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.
*/
//woo right on first try
function euler_two()
{
var even_sum=0;
var answer="";
var up_to = 4000000; //4 mill
function fib(x) {
if (x === 0) {
return 0;
} else if (x === 1) {
return 1;
} else {
return fib(x-1)+fib(x-2);
}
}
fib_total = 0;
for(i=0;fib_total < up_to;i++) {
fib_total = fib(i);
if(fib_total%2 === 0 && fib_total < up_to) {
even_sum += fib_total;
}
}
answer = even_sum;
document.getElementById("euler_two").innerHTML+=answer;
}
/*
Largest prime factor
Problem 3
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
*/
//woo right on first try, not optimized, modern cpu go
function euler_three() {
//factorization - I know nothing about it, here we go
var prime_factors_of = 600851475143;
//var prime_factors_of = 12;
var factors_of = [];
var prime_factors = [];
function factorize(x) {
var factors = [];
check_to = Math.ceil(x/2)+1;
for(i=2;i<check_to;i++) {
if(x%i === 0) {//its divisible!
factors.push(i);
}
}
return factors;
}
//very naive implementation, will enhance as I learn about primes
function is_prime(x) {
//special case for 2, and speeds things up
if(x%2 === 0) return false;
check_to = Math.ceil(x/2);
for(i=2;i<=check_to;i++) {
if(x%i === 0) {//its divisible!
return false;
}
}
return true; //it is prime!
}
factors_of = factorize(prime_factors_of);
//ok we have the factors check if prime
for (index = 0; index < factors_of.length; ++index) {
if(is_prime(factors_of[index])) {
prime_factors.push(factors_of[index]);
}
}
document.getElementById("euler_three").innerHTML+="factors: " + factors_of;
document.getElementById("euler_three").innerHTML+=" prime factors: " + prime_factors;
document.getElementById("euler_three").innerHTML+=" largest prime factor: " + prime_factors.pop();
}
/*
Largest palindrome product
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.
*/
//woo, right on first try, not optimal though I'm sure
function euler_four() {
function is_pal(test_me) {
test_len = test_me.toString().length;
var test_str = test_me.toString();
var first_half = test_str.slice(0,test_len/2);
//get second half and reverse it, have to array to str
var second_half = test_str.slice(Math.ceil(test_len/2),test_len).split("").reverse().join(""); //Math.ceil rounds up, so can handle odd len, skips middle #
if(first_half == second_half) {
return true;
}
return false;
}
var largest_pal = 0; var large_i = 0; var large_j = 0;
//naive countdown, start at the top, first we find is largest
for(i=999;i>800;i--) {
for(j=999;j>800;j--) {
if(is_pal(i*j) && (i*j > largest_pal)) {
large_i = i; large_j = j;
largest_pal = i*j;}
}
}
document.getElementById("euler_four").innerHTML+="largest_pal: " + largest_pal + " with i: "+ large_i +" and j:"+ large_j;
}
/*
Smallest multiple
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?
*/
//woo, right on first try, this is incredibly stupid though, you could just find the prime factors and *, but this way is fun
function is_prime_number(x) {
//special case for 2, and speeds things up
if(x%2 === 0) return false;
var check_to = Math.ceil(x/2);
for(var i=2;i<=check_to;i++) {
if(x%i === 0) {//its divisible!
return false;
}
}
return true; //it is prime!
}
function euler_five() {
var div_up_to = 20;
var test_num = div_up_to;
var true_every_time = true;
var smallest_div = false;
var start_count = 1;
var count = 1;
while(smallest_div === false) {
//factorial LCD time yo
test_num = ((div_up_to-1) * (div_up_to-2) * (div_up_to-3)) * start_count++;
true_every_time = true;
for(i=div_up_to;i>1;i--) {
if(test_num%i !== 0) {
true_every_time = false;
break;
}
}
if(true_every_time) smallest_div = true;
count++;
}
document.getElementById("euler_five").innerHTML+="smallest LCM: " + test_num + " tried " + (count-1);
}
/*
Sum square difference
Problem 6
The sum of the squares of the first ten natural numbers is,
1^2 + 2^2 + ... + 10^2 = 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.
*/
//woo, right on first try, too easy?
function euler_six() {
var sq_up_to = 100;
var sum_squares = 0;
var square_of_sum = 0;
var count = 1;
for(var i=0;i<=sq_up_to;i++) {
sum_squares+=i*i;
square_of_sum += i;
}
square_of_sum = square_of_sum * square_of_sum;
var diff = square_of_sum - sum_squares;
document.getElementById("euler_six").innerHTML+="sum_squares: " + sum_squares + " square_of_sum " + square_of_sum +" diff: " + diff;
}
/*
10001st prime
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 10 001st prime number?
*/
//woo, right on first try,
function euler_seven() {
var find_up_to = 10001;
var found = 0;
var count = 0;
while(found < find_up_to) {
count++;
if(is_prime_number(count)) {
//console.log(count + " found" +found);
found+=1;
}
}
document.getElementById("euler_seven").innerHTML+="nth prime: " + find_up_to + " is " + count;
}
/*
Largest product in a series
Problem 8
Find the greatest product of five consecutive digits in the 1000-digit number.
7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450
*/
function euler_eight() {
var big_number = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
var td1, td2, td3, td4, td5 = 0;
var test_prod, big_prod = 0;
//go through the big number
for(var i=0;i<big_number.length-4;i++) { //0based careful
td1 = parseInt(big_number.slice(i,i+1),10);
td2 = parseInt(big_number.slice(i+1,i+2),10);
td3 = parseInt(big_number.slice(i+2,i+3),10);
td4 = parseInt(big_number.slice(i+3,i+4),10);
td5 = parseInt(big_number.slice(i+4,i+5),10);
test_prod = td1 * td2 * td3 *td4 * td5;
if(test_prod >= big_prod) big_prod = test_prod;
}
document.getElementById("euler_eight").innerHTML+="big_prod: " + big_prod;
}
/*
Special Pythagorean triplet
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.
*/
function euler_nine() {
function py_force(match_int) {
var max = 500;
var c = 0;
//brute force baby
for(var a=1;a<max;a++) {
for(var b=1;b<max;b++) {
c = Math.sqrt((a*a) + (b*b));
if((a + b + c) === match_int) {
return [a,b,c];
}
}
}
}
py_arr = py_force(1000);
document.getElementById("euler_nine").innerHTML+="Pythagorean triplet: " + py_arr;
document.getElementById("euler_nine").innerHTML+=" Pythagorean triplet product: " + (py_arr[0]*py_arr[1]*py_arr[2]).toString();
}
/*
Summation of primes
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.
*/
//we're starting to get serious about primes, writing sieve of eratosthenes, and maybe wheel factorization http://jsbin.com/ gives bad results. Note screwed up reading problem first time, saved
function euler_ten() {
var nth_prime = 2000000;
var primes_under = 2000000;
function is_prime_faster(test_num) {
if(test_num%2 === 0) return false;
var test_to = Math.floor(Math.sqrt(test_num));
//check only sqrt of n
for(var i=3;i<=test_to;i=i+2) {
//check only every odd
if(test_num%i === 0) return false;
}
return true;
}
function find_sum_below(under_num) {
var sum_primes = 0;
for(var i=3;i<under_num;i+=2) {
if(is_prime_faster(i)) {
sum_primes += i;
}
}
return sum_primes +2; //we skip 2, add it back
}
function find_primes_up_to(nth_prime) {
var found=2, count=2, sum_primes=0;
while(found < nth_prime+1) {
count++;
if(is_prime_faster(count)) {
found++;
}
}
return count;
}
var large_prime = find_primes_up_to(nth_prime);
document.getElementById("euler_ten").innerHTML+=
"find_sum_below: "+find_sum_below(primes_under);
}
/*
Longest Collatz sequence
Problem 14
The following iterative sequence is defined for the set of positive integers:
n → n/2 (n is even)
n → 3n + 1 (n is odd)
Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?
NOTE: Once the chain starts the terms are allowed to go above one million.
No Probs - first try
*/
function euler_14() {
function collatz_len(n) //naive implementation
{
var len = 0;
while(n !== 1) {
if (n%2 === 0) {
n = n / 2; len++;
} else {
n = 3*n + 1; len++;
}
}
return len;
}
var longest = 0; longest_num = 0;
for(var i = 1000000; i>1; i--) {
var len = collatz_len(i);
if(len > longest) {
longest = len;
longest_num = i;
console.log(longest_num + " " + len);
}
}
document.getElementById("euler_14").innerHTML+=
"longest collatz num at: "+longest_num;
}
/*
Lattice paths
Problem 15
Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
How many such routes are there through a 20×20 grid?
it appears this problem is equivalent to a multichoose, must move right, so all right moves sum to lattice size +1, move can be any number, so count all permutations
*/
function euler_15() {
function factorial(n)
{
if (n <= 1) return 1;
return n*factorial(n-1);
}
function multichoose(n, k) {
return factorial(n+k-1) / (factorial(k)*factorial(k));
}
document.getElementById("euler_15").innerHTML+=
"multichoose: "+multichoose(21,20);
}
/*
Power digit sum
Problem 16
215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 2^1000?
Make our own power function and number type w/ an array
*/
function euler_16() {
function by_the_power_of_two(n) { //grayskull!
var twos_array = [1]; var carry = [];
for(var i = 0; i < n; i++) {
var times = twos_array.length;
for(var k = 0; k < times; k++) {
twos_array[k] = twos_array[k] * 2;
if(carry[k] && carry[k] === 1) {
twos_array[k]+=carry[k];
carry[k] = 0;
}
if(twos_array[k] >= 10) {//carry the 1
twos_array[k] = twos_array[k]%10; //keep only remainder
if((k+1) >= times) {
twos_array[k+1] = 1;
} else {
carry[k+1] = 1;
}
}
}
}
return twos_array;
}
var answer = by_the_power_of_two(1000).reverse();
var sum = 0;
for(var i in answer) { sum += answer[i]; }
document.getElementById("euler_16").innerHTML+=
"two to the power of 1k!: "+answer.join("");
document.getElementById("euler_16").innerHTML+=
" sum: "+sum;
}
/*
Self powers
Problem 48
The series, 1^1 + 2^2 + 3^3 + ... + 10^10 = 10405071317.
Find the last ten digits of the series, 1^1 + 2^2 + 3^3 + ... + 1000^1000.
//can't use jsbin, it quits too fast
*/
function euler_48() {
var power_to = 1000;
function power_multi(n, exp) { //grayskull!
var out_array = [1]; var rem = 0;
for(var i = 0; i < exp; i++) {
var times = out_array.length;
for(var k = 0; k < times; k++) {
out_array[k] = out_array[k] * n + rem;
if(out_array[k] >= 10) {
rem = Math.floor(out_array[k]/10);
out_array[k] = out_array[k]%10;
} else {
rem = 0;
}
}
if(rem !==0) { //add the remaineder
out_array[out_array.length] = rem;
rem = 0;
}
//take care of rem in lsd, bit weird array twiddling, subop? only will work up to 999 power (3 digit rem)
var trem_arr = out_array[out_array.length-1].toString().split('');
for(var s in trem_arr) { trem_arr[s] = Number(trem_arr[s]); }
trem_arr = trem_arr.reverse(); //js arrays are so bad
out_array[out_array.length-1] = trem_arr[0];
if(trem_arr.length >= 2) out_array.push(trem_arr[1]);
if(trem_arr.length === 3) { out_array.push(trem_arr[2]);
}
}
return out_array.reverse(); //return it like reg #
}
function sum_array(sum_arr, arr) {
if(arr.length > sum_arr.length) return;
sum_arr=sum_arr.reverse();
arr=arr.reverse();
var rem = 0;
for(var i = 0; i < sum_arr.length; i++) {
if(arr.length > i) {
sum_arr[i] = sum_arr[i] + arr[i] + rem;
} else {
sum_arr[i] = sum_arr[i] + rem;
}
if(sum_arr[i] >= 10) { //should work 2 digit rem
rem = Math.floor(sum_arr[i]/10);
sum_arr[i] = sum_arr[i]%10;
} else {
rem = 0;
}
}
return sum_arr.reverse();
}
var answer = [];
var answer_sum_arr, temp_arr = [];
for(var count = power_to; count > 0; count--) {
console.log("count:"+count);
if(count === power_to) {
answer_sum_arr = power_multi(count,count);
console.log("answer_sum_arr:"+answer_sum_arr);
} else {
temp_arr = power_multi(count,count);
answer_sum_arr = sum_array(answer_sum_arr,temp_arr);
}
}
console.log("final answer_sum_arr:"+answer_sum_arr);
var len = answer_sum_arr.length;
var answer48 = answer_sum_arr.slice(len-10,len).join("");
console.log("last 10 answer_sum_arr:"+answer48);
//document.getElementById("euler_48").innerHTML+=
// "sum: "+sum;
//alt solution using boring modulo
var date0 = new Date();
var sum = 0;
var modulo = 10000000000;
for(var i = 0;i<=1000;i++){
var number = i;
for(var j = 0;j<i-1;j++){
number = number%modulo;
number = number * i;
}
sum+=number;
sum = sum%modulo;
}
var date1 = new Date();
console.log(sum,'took:',date1-date0,'ms');
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment