Project Euler Solution #49: Prime permutations

Problem 49

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

Solution

The given sequence starts with 1487 and we assume that the second sequence starts with a larger first element. This is a pretty strong assumption, but holds for this problem. We then create triples \((a, b, c)\) with the property \(a=b - 3330=c-6660\), which shows that our upper bound for possible four digit numbers is \(10000 - 6660 = 3340\). To complete this problem, all we have to do is check the quite small search space to let \(a,b,c\) be prime and its digits permutations of each other:

function solution() {
    for (let a = 1489; a < 3340; a++) {

        let b = a + 3330;
        let c = b + 3330;

        if (isPrime(a) && isPrime(b) && isPrime(c) && isPerm(a, b) && isPerm(b, c)) {
            return (a * 10000 + b) * 10000 + c;
        }
    }
    return null;
}

Checking if a number is prime can be done for each number separately, since the search space is pretty small, or with a pre-computed Sieve of Eratosthenes to make each prime check \(O(1)\):

function Sieve(n) {

    const sieve = new Uint8Array(n + 1);

    for (let i = 2; i * i <= n; i++) {

        if (sieve[i] == 0) {
            for (let j = i * i; j <= n; j += i) {
                sieve[j] = 1;
            }
        }
    }
    return function (n) {
        return sieve[n] === 0;
    }
}

const isPrime = Sieve(9999);

The last piece is the permutation check. Intuitively, we could use a set or a bitset to mark each digit as present and compare these sets. But this is only a sufficient condition, as isPerm(122, 211) would give true. For a necessary condition, we add a counter for each digit, which we add up for the first number, and decrease for the second number. If all counters are zero at the end, the given numbers are permutations of each other:

function isPerm(a, b) {

    var cnt = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
    while (a > 0) {
        cnt[a % 10]++;
        a = a / 10 | 0;
    }
    while (b > 0) {
        cnt[b % 10]--;
        b = b / 10 | 0;
    }
    return cnt.every(x => x === 0);
}

It remains to be noted that isPerm is transitive which means that from isPerm(a, b) and isPerm(b, c) directly follows that isPerm(a, c). This allows us to skip the third test, as it is implied by the other two.