JavaScript Implementation of Problem 46
View source code here on GitHub!
Includes
Problem Solution
- p0046()
Project Euler Problem 46
Didn't even need to rearrange the formula to solve it trivially
Revision 1:
It turns out that rearranging the formula let me cut the time by ~50x
Problem:
It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.
9 = 7 + 2×1^2 15 = 7 + 2×2^2 21 = 3 + 2×3^2 25 = 7 + 2×3^2 27 = 19 + 2×2^2 33 = 31 + 2×1^2
It turns out that the conjecture was false.
What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?
- Returns:
number --
1/**
2 * Project Euler Problem 46
3 *
4 * Didn't even need to rearrange the formula to solve it trivially
5 *
6 * Revision 1:
7 *
8 * It turns out that rearranging the formula let me cut the time by ~50x
9 *
10 * Problem:
11 *
12 * It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and
13 * twice a square.
14 *
15 * 9 = 7 + 2×1^2
16 * 15 = 7 + 2×2^2
17 * 21 = 3 + 2×3^2
18 * 25 = 7 + 2×3^2
19 * 27 = 19 + 2×2^2
20 * 33 = 31 + 2×1^2
21 *
22 * It turns out that the conjecture was false.
23 *
24 * What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?
25 *
26 * @return {number}
27 */
28exports.p0046 = function() {
29 const cachedPrimes = Array.from(primes.primes(6000));
30 for (let goal = 35; ; goal += 2) {
31 if (primes.isPrime(goal)) {
32 continue;
33 }
34 let done = false;
35 for (const p of cachedPrimes) {
36 if (p >= goal) {
37 continue;
38 }
39 for (let x = 1; x < Math.sqrt((goal - p) / 2) + 1; x++) {
40 if (p + 2 * x * x === goal) {
41 done = true;
42 break;
43 }
44 }
45 if (done) {
46 break;
47 }
48 }
49 if (!done) {
50 return goal;
51 }
52 }
53 return -1;
54};
55
56const primes = require('./lib/primes.js');