JavaScript Implementation of Problem 60

View source code here on GitHub!

p0060()

Project Euler Problem 60

Problem:

The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

Returns:

number --

 1/**
 2 * Project Euler Problem 60
 3 *
 4 * Problem:
 5 *
 6 * The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the
 7 * result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four
 8 * primes, 792, represents the lowest sum for a set of four primes with this property.
 9 *
10 * Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.
11 *
12 * @return {number}
13 */
14exports.p0060 = function() {
15    const iterator = primes.primes();
16    const cachedPrimes = [3];
17    iterator.next(); // 2 is excluded because higher even numbers can't be prime
18    iterator.next();
19    iterator.next(); // 5 is excluded because if a number ends with 5, it's divisible by 5
20    const compat = new Map();
21    for (const x of iterator) {
22        const strX = String(x);
23        for (const y of cachedPrimes) {
24            if (primes.isPrime(Number(`${strX}${y}`)) && primes.isPrime(Number(`${y}${strX}`))) {
25                for (const [a, b, c] of iters.combinations(compat.get(y) || new Set(), 3)) {
26                    // remember these checks are commutative
27                    if (compat.get(b).has(a) && compat.get(c).has(a) && compat.get(c).has(b)) {
28                        const strA = String(a);
29                        const strB = String(b);
30                        const strC = String(c);
31                        const concatenations = [
32                            Number(`${strA}${strX}`),
33                            Number(`${strX}${strA}`),
34                            Number(`${strB}${strX}`),
35                            Number(`${strX}${strB}`),
36                            Number(`${strC}${strX}`),
37                            Number(`${strX}${strC}`),
38                        ];
39                        if (concatenations.every(primes.isPrime)) {
40                            return x + y + a + b + c;
41                        }
42                    }
43                }
44                if (!compat.has(x)) {
45                    compat.set(x, new Set());
46                }
47                compat.get(x).add(y);
48                if (!compat.has(y)) {
49                    compat.set(y, new Set());
50                }
51                compat.get(y).add(x);
52            }
53        }
54        cachedPrimes.push(x);
55    }
56    return -1;
57};
58
59const iters = require('./lib/iters.js');
60const primes = require('./lib/primes.js');

Tags: optimization