Project Euler Problem 49: Prime Permutations

The source code for this problem can be found here.

Problem Statement

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 Discussion

Let \(\delta = 3330\), the distance between each element in the candidate sequences.

Iterate over four digit prime numbers \(p\) in the range \([1000, 10000 - 2 \delta]\) (guaranteeing that each prime, and the next two in the sequence defined, are precisely four digits in length). Now, given \(p\), build the corresponding candidate sequence \(\lbrace p, p + \delta, p + 2 \delta \rbrace\), and check that each element is prime.

Finally, when a candidate list of primes is identified, check whether the digits in each element are permutations of one another. Any sequence satisfying these condition meets the requirements for this problem.

Note

this algorithm will find both the given solution \(\lbrace 1487,4817,8147 \rbrace\) and the other solution that we seek. We must skip past the known solution if it is the first encountered.

Solution Implementation

from itertools import dropwhile

from lib.digital import digits_of
from lib.numbertheory import is_probably_prime
from lib.sequence import Primes


def solve():
    """ Compute the answer to Project Euler's problem #49 """

    delta = 3330  # difference in arithmetic sequence
    lower_bound = 1000
    upper_bound = 10000 - 2 * delta  # need room to increment by delta twice
    non_target = (1487, 4817, 8147)  # this is a known answer, looking for another

    for prime in dropwhile(lambda p: p < lower_bound, Primes(upper_bound=upper_bound)):

        a, b, c = (prime + i * delta for i in range(3))  # generate the candidate sequence

        if is_probably_prime(b) and is_probably_prime(c):  # we already know that a is prime, no need to check
            digits = {p: sorted(digits_of(p, base=10)) for p in (a, b, c)}  # sorting allows comparison
            if digits[a] == digits[b] == digits[c] and (a, b, c) != non_target:
                base = 10 ** 4
                answer = (a * base ** 2) + (b * base * 1) + (c * base ** 0)
                return answer


expected_answer = 296962999629

solutions.problem49.solve()

Compute the answer to Project Euler’s problem #49