Project Euler # 49 Prime permutations in Python

Question

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?

from time import time


def sieve(n):
    """generates primes up to n."""
    s = [True] * (n + 1)
    for p in range(2, n):
        if s[p]:
            yield p
            for i in range(p * p, n, p):
                s[i] = False


def is_permutation(n1, n2):
    """returns True if n1 is permutation of n2"""
    to_str_1 = str(n1)
    to_str_2 = str(n2)
    if n1 == n2:
        return False
    to_str_1_digits = {digit: to_str_1.count(digit) for digit in to_str_1}
    to_str_2_digits = {digit: to_str_2.count(digit) for digit in to_str_2}
    if not to_str_1_digits == to_str_2_digits:
        return False
    return True


def get_permutations(n):
    """generates tuples of 3 permutations each within range n."""
    primes = set(sieve(n))
    for prime1 in primes:
        for prime2 in primes:
            if is_permutation(prime1, prime2):
                for prime3 in primes:
                    if is_permutation(prime3, prime1) and is_permutation(prime3, prime2):
                        yield prime1, prime2, prime3


def check_subtraction(n):
    """checks permutations within range n for subtraction rules.
    returns valid permutations."""
    permutations = get_permutations(n)
    for x, y, z in permutations:
        if abs(x - y) == abs(y - z):
            return x, y, z


if __name__ == '__main__':
    start_time = time()
    x, y, z = sorted(check_subtraction(10000))
    print(str(x) + str(y) + str(z))
    print(f'Time: {time() - start_time} seconds.')

Answer 1

Micro optimisations in is_permutation

In is_permutation, you could call the str functions after checking whether n1 == n2.

Also, you could simplify the end of the function with a single return to_str_1_digits == to_str_2_digits.

Taking into account these comments and shortening a bit the variable names, we get:

def is_permutation(n1, n2):
    """returns True if n1 is permutation of n2"""
    if n1 == n2:
        return False
    str1 = str(n1)
    str2 = str(n2)
    digits1 = {digit: str1.count(digit) for digit in str1}
    digits2 = {digit: str2.count(digit) for digit in str2}
    return digits1 == digits2

Improving the algorithm

We generate a set of primes and iterate over it with nested loops. A faster way would be to be able to group primes which correspond to the same permutation.

An efficient way to do it would be to use a dictionnary mapping a hashable value to the list of primes being permutations of each other. That value should be chosen to be some kind of signature which would be the same if and only if values are permutations. For instance, we could use the string representation of prime p sorted alphabetically: ''.join(sorted(str(p))).

Once they are grouped, we can easily get the different permutations:

def get_permutations(n):
    """generates tuples of 3 permutations each within range n."""
    permut_primes = dict()
    for p in sieve(n):
        permut_primes.setdefault(''.join(sorted(str(p))), []).append(p)
    for perms in permut_primes.values():
        for a, b, c in itertools.combinations(perms, 3):
            assert c > b > a
            yield a, b, c

This also needs a minor change in check_substraction to ensure we do not find the already provided result:

def check_subtraction(n):
    """checks permutations within range n for subtraction rules.
    returns valid permutations."""
    permutations = get_permutations(n)
    for x, y, z in permutations:
        if abs(x - y) == abs(y - z) and x != 1487:
            return x, y, z

The corresponding code is more than 500 times faster than the original code.