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)

solutions.problem49.solve()