Project Euler Problem 49

Solution

Answer: 296962999629

We seek a second 4-digit arithmetic progression of primes such that:

1. All three terms are prime.
2. They form an arithmetic sequence.
3. The three numbers are permutations of one another.
4. It is different from $1487,4817,8147$.

---

Mathematical analysis

Let the three terms be

$$a,\quad a+d,\quad a+2d$$

where all are 4-digit primes.

The permutation condition means all three numbers contain exactly the same digits in a different order. A useful consequence is:

• Any permutation of a number has the same digit sum.
• Therefore all three numbers are congruent modulo $9$.

Hence:

$$(a+d)-a=d$$

must be divisible by $9$.

Since all primes involved are odd (they are 4-digit primes greater than 2), the common difference must also be even.

Therefore:

$$d \text{ is divisible by } 18.$$

That sharply reduces the search space.

The natural algorithm is:

1. Generate all 4-digit primes.
2. Group primes by their sorted digits.

• Example:

$$1487 \to "1478"$$

$$4817 \to "1478"$$ 3. Within each permutation-group, search for 3-term arithmetic progressions. 4. Ignore the known example. 5. Concatenate the three numbers.

---

Python implementation

from collections import defaultdict
from itertools import combinations

# ------------------------------------------------------------
# Sieve of Eratosthenes to generate primes up to 9999
# ------------------------------------------------------------
limit = 10000
is_prime = [True] * limit
is_prime[0] = is_prime[1] = False

for i in range(2, int(limit ** 0.5) + 1):
    if is_prime[i]:
        for j in range(i * i, limit, i):
            is_prime[j] = False

# Keep only 4-digit primes
primes = [p for p in range(1000, 10000) if is_prime[p]]

# ------------------------------------------------------------
# Group primes by sorted digit signature
# Example: 4817 -> "1478"
# ------------------------------------------------------------
groups = defaultdict(list)

for p in primes:
    key = ''.join(sorted(str(p)))
    groups[key].append(p)

# ------------------------------------------------------------
# Search each group for arithmetic sequences
# ------------------------------------------------------------
for group in groups.values():

    # Need at least 3 numbers to form a sequence
    if len(group) < 3:
        continue

    group.sort()
    group_set = set(group)

    # Try every pair as potential first two terms
    for a, b in combinations(group, 2):
        d = b - a
        c = b + d

        # Check if third term exists
        if c in group_set:

            # Ignore the known sequence
            if (a, b, c) != (1487, 4817, 8147):

                result = f"{a}{b}{c}"
                print(result)

---

Code walkthrough

1. Generate primes

is_prime = [True] * limit

We create a boolean sieve.

for i in range(2, int(limit ** 0.5) + 1):

Standard Sieve of Eratosthenes:

every multiple of a prime is marked composite.

After the sieve:

primes = [p for p in range(1000, 10000) if is_prime[p]]

keeps only 4-digit primes.

---

2. Group by permutations

key = ''.join(sorted(str(p)))

Two numbers are permutations iff their sorted digits are identical.

Example:

$$1487,\ 4817,\ 8147$$

all become:

$$"1478"$$

So they enter the same group.

---

3. Search for arithmetic progressions

For every pair $(a,b)$:

d = b - a
c = b + d

This constructs the possible third term of the arithmetic progression.

If:

c in group_set

then:

$$a,\ b,\ c$$

forms a valid arithmetic sequence.

---

4. Ignore the known example

if (a, b, c) != (1487, 4817, 8147):

The problem states there is exactly one other sequence.

Running the program yields:

296962999629

corresponding to:

$$2969,\ 6299,\ 9629$$

Check:

• Arithmetic progression:

$$6299-2969=3330$$

$$9629-6299=3330$$

• All prime.
• All permutations of digits ${2,6,9,9}$.

Everything matches.

---

Final verification

The concatenation has:

$$4+4+4 = 12$$

digits, as required:

$$2969;6299;9629$$

All terms are 4-digit primes and differ by the same amount.

Therefore the required 12-digit number is:

Answer: 296962999629