Project Euler Problem 49 Solution

Project Euler Problem 49 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

This script is designed to solve Project Euler Problem 49, which involves identifying prime numbers that are permutations of each other and form arithmetic sequences. The goal is to find sets of prime numbers that not only share the same digits but also exhibit a common difference between them, ultimately forming a sequence of length K.

This solution addresses the problem by finding sequences of primes that fulfill three main conditions:

They are permutations (i.e. the primes contain the same digits in a different order).
They form an arithmetic progression (i.e. the difference between consecutive primes is constant).
The sequence contains a specified number of terms, represented by $K$, with the first term less than $N$.

1. Setup and Prime Generation

The code begins by importing necessary modules and reading the input:

from collections import defaultdict
import Euler

N, K = map(int, input().split())
p = Euler.prime_sieve(1_000_000)

The line $N, K = \text{map(int, input().split())}$ reads two integers from input: $N$ (the threshold for the first term of the sequence) and $K$ (the length of the arithmetic progression).
$p = Euler.prime\_sieve(1\,000\,000)$ generates all prime numbers below 1,000,000 using a sieve algorithm provided by the Euler module.

2. Grouping Primes by Their Digit Permutations

To easily identify primes that are permutations of each other, each prime is converted to a canonical form. This is done by:

Converting the prime to a string.
Sorting its digits.
Joining the sorted digits back into a string.

For example, the prime $1487$ becomes $\text{'1478'}$.

The following code snippet performs this grouping:

g = defaultdict(list)

for q in p:
    g[''.join(sorted(str(q)))].append(q)

Here, the primes are grouped in the dictionary g by their sorted digit strings.

3. Searching for Valid Arithmetic Sequences

The next step is to iterate through each group of primes (which are all permutations of each other) and search for arithmetic sequences.

res = []
for lst in g.values():
    for i in range(len(lst)):
        for j in range(i+1, len(lst)):
            d = lst[j] - lst[i]
            seq = [lst[i] + k*d for k in range(K)]
            if all(x in lst for x in seq) and lst[i] < N:
                res.append(''.join(map(str, seq)))

Iterating Over Groups: The code loops over each list lst in g.values(), where each list consists of primes that are digit permutations of each other.
Pairwise Comparison: For every distinct pair of primes (with indices $i$ and $j$ such that $j > i$), the common difference is computed as: $d = \text{lst}[j] - \text{lst}[i]$.
Constructing the Sequence: An arithmetic sequence of $K$ terms is formed using: $\text{seq} = [\text{lst}[i] + k \cdot d \text{ for } k \text{ in range}(K)]$.
Validation Checks:
- Permutation Check: The condition $\text{all}(x \in \text{lst for } x \in \text{seq})$ ensures every term in the generated sequence exists in lst � meaning all terms are permutations of one another.
- Threshold Check: The condition $\text{lst}[i] < N$ ensures that the first term of the sequence is less than $N$.
Storing the Result: If both conditions are met, the sequence is converted into a concatenated string (e.g., $1487\,4817\,8147$ becomes "148748178147") and appended to the res list.

4. Sorting and Printing the Results

Finally, the found sequences are sorted and printed:

print("\n".join(sorted(res, key=lambda s: int(s[:len(s)//K]))))

Sorting: The sequences are sorted based on their first term. Each result is a concatenated string of $K$ numbers. The key function $ \lambda s: \text{int}(s[:\text{len}(s)//K]) $ extracts the substring representing the first prime by dividing the full length by $K$. This substring is then converted to an integer to ensure numerical sorting.
Printing: The sorted results are joined with newline characters and printed, each on its own line.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 49

HackerRank Project Euler 49: You are given $N$, (2,000≤ N ≤ 1,000,000) and $K$, (3≤ K≤ 4) find all $K$ size sequences where first element is less than $N$, and $K$ elements are permutations of each other, are prime and are in Arithmetic Progression.

Python Source Code

from collections import defaultdict
import Euler
N, K = map(int, input().split())
p = Euler.prime_sieve(1_000_000)
g = defaultdict(list)

for q in p: g[''.join(sorted(str(q)))].append(q)
res = []
for lst in g.values():
    for i in range(len(lst)):
        for j in range(i+1, len(lst)):
            d = lst[j]-lst[i]
            seq = [lst[i]+k*d for k in range(K)]
            if all(x in lst for x in seq) and lst[i] < N:
                res.append(''.join(map(str, seq)))

print("\n".join(sorted(res, key=lambda s: int(s[:len(s)//K]))))

Last Word

The prime_sieve function will be imported instead of hard coded into the source code. This provides flexibility to include different sieves as required to solve a problem.