Stupid brute force, not masterpiece, which is generally not suitable on really large numbers. But it is easy.
var num = 1000, sum = 0, res = 0;
while(num--){
if(!(num%3) || !(num%5))
res += num;
}
print(res);
// time: 0.02s memory: 4984 kB
Let's use the power of math coprocessor ;)
var numbers = [
3.7107287533902102798797998220837590246510135740250,
4.6376937677490009712648124896970078050417018260538,
............... etc
5.3503534226472524250874054075591789781264330331690
];
var sum = 0;
for(var i = numbers.length - 1; i > -1; --i) {
sum += numbers[i];
}
var result = sum * 10000000000;
print(result.toString().substring(0,10));
// time: 0.01s memory: 4984 kB
Congratulations, the answer you gave to problem 13 is correct.
You are the 67470th person to have solved this problem.
Somebody named... Euler wrote:
"First I noted that for an n by n grid, and n being odd, the number in the top right corner is n2.
A little mathematical analysis told me that the other corners are given by: n2-n+1, n2-2n+2, and n2-3n+3.
Adding these together gives the quadratic, 4n2-6n+6.
Then all I had to do was create a loop from 3 to 1001 in steps of 2 and find the running total
(starting from 1) of the quadratic."
var s = 1;
for(var n = 3; n <= 1001; n += 2) {
s += 4 * Math.pow(n,2) - 6 * n + 6;
}
print(s);
// time: 0.02s memory: 4984 kB
Congratulations, the answer you gave to problem 28 is correct.
You are the 39019th person to have solved this problem.
var limit = 500,
product = 0,
pow_M = 0,
pow_N = 0;
for(var n = 3; n < limit; ++n) {
for(var m = 4; m < limit; ++m) {
product = m * (m + n);
if(product == limit) {
pow_M = Math.pow(m, 2);
pow_N = Math.pow(n, 2);
print((pow_M - pow_N) * (2*(m*n)) * (pow_M + pow_N));
n = limit;
break;
}
}
}
time: 0.01s memory: 4984 kB
Congratulations, the answer you gave to problem 9 is correct.
You are the 99646th person to have solved this problem.
You have earned 1 new award:
Decathlete: Solve ten consecutive problems
First of all I wanted refresh my school math knowledge here.
Then I've wrote the optimized program.
And then I read this:
"24 Jul 2004 01:43 am
bitRAKE (Assembler)
This does not require programming at all.
Compute the prime factorization of each number from 1 to 20, and multiply the greatest power of each prime together:
20 = 2^2 * 5
19 = 19
18 = 2 * 3^2
17 = 17
16 = 2^4
15 = 3 * 5
14 = 2 * 7
13 = 13
11 = 11
All others are included in the previous numbers."
So you better type into Linux command shell 'bc' and then 2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19
Congratulations, the answer you gave to problem 5 is correct.
You are the 131586th person to have solved this problem.
Well...
I'm sure there is a lot of other cheats in Internet.
var num = 600851475143;
var ans = 0;
for(var div = 3; ; div += 2) {
if(!(num % div)) {
do {num /= div;} while (!(num % div));
if(num == 1) {
ans = div;
break;
}
}
}
print(ans);
(time: 0.02s memory: 4984 kB)
Congratulations, the answer you gave to problem 3 is correct.
You are the 127054th person to have solved this problem.
UPDATED at 16 May 2012: Solution with one loop:
var num = 600851475143;
var div = 2;
while (num > 1) {
if (0 == (num % div)) {
num /= div;
div--;
}
div++;
}
print(div);
(time: 0.02s memory: 4984 kB)
OK, just the code without any clarifications because no one reads my blog.
var n = 100; var sqsum = (n * (n + 1) * (2 * n + 1)) / 6; var sumsq = (1 + n) * n / 2; print(sumsq*sumsq - sqsum);
('n' is here just for clarity of formula)
(time: 0.02s memory: 4984 kB on usual PC)
Congratulations, the answer you gave to problem 6 is correct.
You are the 132085th person to have solved this problem.
UPDATED:
krewllobster has also offered an interesting and fast option:
var a = 0, b = 0, x = 1;
while (x < 101) {
a += Math.pow(x,2);
b += x;
x += 1;
}
print(Math.pow(b,2) - a);
(time: 0.01s memory: 4984 kB)
I like Free Software Foundation, Inc.
I like to use the right tool for the right job too.
So to get the number I typed 'bc' in the Linux command line and then '2^1000'.
Well, now I am ready to calculate the sum via JavaScript (SpiderMonkey):
var a="copypasted value from my command line as STRING"; var sum = 0; for(var i = a.length - 1; i > -1; --i) sum += parseInt(a.charAt(i)); print(sum);
(time: 0.02s memory: 4984 kB on usual PC)
Congratulations, the answer you gave to problem 16 is correct.
You are the 70718th person to have solved this problem.
This problem is about permutations and so called central binomial coefficient (the binomial theorem you must remember from the school). And do you remember the Pascal's triangle? If not, check it here. (If you still don't understand what I am talking about you can see the complete solution here).
All you need is to observe that for a NxN grid there are (2n)!/(n!)2 possible ways of getting from one corner to the other one and in our case it will be 40!/(20!)2. If you are still unable to calculate it you can use A000984.
But if you still want to get the answer by yourself, do not rush to crack factorials with your lovely brute force with 350 lines of C++ code, let's start from... little cheat.
We have some ways for cheat.
Of course we could use the J language to get the central binomial coefficient:
(! +:) 20x
or even more shorter:
20!40x
but it isn't real cheat. There is a better way: http://www.google.com/search?q=40+choose+20
Bingo? Btw. tell me truth, did you know that the Google calculator has the operator 'choose'?
Brilliant, isn't? You just command "40 choose 20" and Google gives you the answer: please, master! Try the same way to ask Google for money ;)
Well, now let's start thinking.
Rudy Penteado from Brazil codes in Assembler language. He discovered that:
"This is what I find 2 months ago when I solved it:
Each movement in the horizontal is a zero.
Each movement in the vertical is a one.
1st binary# in this series:
0000000000000000000011111111111111111111
last:
1111111111111111111100000000000000000000
For the numbers in between, the amount of zeros should be the same as ones.
In other words, the ones and zeros have to be rearranged."
Easy, isn't? Try to code this in Assembler.
I won't. I did my solution with some magic too:
var ans = 1; for(var c = 40, d = 1; c > 20; --c, ++d) ans = (ans * c)/d; print(ans);
// time: 0.02s memory: 4984 kB
Congratulations, the answer you gave to problem 15 is correct.
You are the 53180th person to have solved this problem.
"Problem 8
Find the greatest product of five consecutive digits in the 1000-digit number."
Well, this problem can be solved even without computer.
Just use the best tool that you never had: your brain ;)
Use the "Find" command in your favorite text editor to highlight all 9 in the given 1000-digit number.
Is it not easy to find a combination of 99879?
But if you wanna code:
var initial = [the given 1000-digit number as array of integers];
var answer = 0;
var sum = 0;
var bestsum = 0;
var tarr = [5];
for(var c = initial.length - 1; c --> 3;) {
sum = 0;
for(var s = c; s > c-5; --s)
sum += initial[s];
if(sum > bestsum) {
bestsum = sum;
for(var j = c, i = 4; j > c-5; --j, --i)
tarr[i] = initial[j];
}
}
answer = tarr[0] * tarr[1] * tarr[2] * tarr[3] * tarr[4];
print(answer);
p: 10000Amazing!
#include <stdio.h>
int main() {
const int max = 10001;
int count = 0;
unsigned int i, j;
for(i = 2; ; i++) {
for(j = 2; j < i; j++) {
if(i % j == 0)
break;
}
if(i == j) {
count++;
if(count == max)
break;
}
}
printf("%dst prime number is: %d\n", max, i);
}
(http://projecteuler.net/problem=4)
"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."
#include <stdio.h>
#include <stdbool.h>
bool is_palindrome(unsigned int const num) {
unsigned int res = 0;
unsigned int n = num;
while(n > res) {
res = res*10 + n%10;
n /= 10;
}
return n == res;
}
int main() {
int i, j, c = 0;
unsigned int res = 0;
/*
The palindrome can be written as:
abccba
Which then simpifies to:
100000a + 10000b + 1000c + 100c + 10b + a
And then:
100001a + 10010b + 1100c
Factoring out 11, you get:
11(9091a + 910b + 100c)
So the palindrome must be divisible by 11.
Seeing as 11 is prime, at least one of the numbers
must be divisible by 11.
So brute force only with less numbers to be checked:
lets iterate only through the highest 100
*/
for(i = 999; i > 899; --i) {
for(j = 999; j > 899; --j) {
res = i*j;
++c;
if(is_palindrome(res)) {
printf("\nThe largest palindrome is %d \
\nIs product of %d and %d \
\nDetected at iteration %d\n\n", \
res, i, j, c);
i = 899;
break;
}
}
}
return 0;
}
P.S.: If the memory consumption is the cornerstone for you, feel free to experiment with variable types.
There is something wrong with 'is_palindrome' method.
I did a simple test:
#include <stdio.h>
#include <stdbool.h>
bool is_palindrome(unsigned int const num) {
unsigned int res = 0;
unsigned int n = num;
while(n > res) {
res = res*10 + n%10;
n /= 10;
}
return n == res;
}
int main() {
int i;
for(i = 100; i < 600; ++i) {
if(is_palindrome(i))
printf("%d\n", i);
}
return 0;
}
And the output was:
110
220
330
440
550
But 111, 222, 212, 585 etc. are palindromic numbers too!