Detailed mathematical approach

Problem Summary

We are told that \(1487, 4817, 8147\) is a three-term arithmetic progression of four-digit primes, and that all three numbers are permutations of the same four digits. The task is to find the other four-digit prime progression with the same property and concatenate its three terms into one 12-digit integer.

The crucial point is that two conditions must hold at the same time: the numbers must lie in arithmetic progression, and they must belong to the same digit-permutation class. The successful solution comes from organizing the search around that shared digit structure instead of generating permutations blindly.

Mathematical Approach

The implementations treat the problem as a search over four-digit primes. For each prime \(p\), the digits are sorted into a canonical key, and primes with the same key are collected together. Inside one such class, a three-term arithmetic progression is easy to test.

Digit-Signature Classes

Define the digit signature of a four-digit number \(p\) by sorting its decimal digits in nondecreasing order. If we write this signature as \(\sigma(p)\), then

$\sigma(p)=\text{sorted digits of }p.$

Two four-digit numbers are permutations of one another exactly when they have the same signature. So the search space naturally splits into classes

$G_s=\{p:\ 1000 \le p \le 9999,\ p \text{ is prime},\ \sigma(p)=s\}.$

Any valid answer must lie entirely inside one class \(G_s\). That turns the original problem into a much smaller collection of subproblems: for each signature class of primes, determine whether it contains a three-term arithmetic progression.

An Arithmetic Progression Becomes a Membership Test

Suppose a class \(G_s\) is sorted increasingly, and choose two elements \(a<b\) from it. If they are the first two terms of a three-term arithmetic progression, then the third term is forced:

$b-a=d,\qquad c=b+d=2b-a.$

So there is no need to guess all three numbers independently. For every pair \((a,b)\) inside one signature class, compute \(c=2b-a\) and check whether \(c\) is also in the same class. If it is, then all required properties are already satisfied:

$a,\ b,\ c \in G_s \implies \text{all three are four-digit primes with the same digits.}$

The only extra bound worth checking is \(c \le 9999\), because the progression must stay among four-digit numbers.

Useful Congruence Facts

Sharing a digit signature means sharing the same digit sum. Therefore every number in a fixed class \(G_s\) is congruent modulo \(9\). If \(a,b,c\) all belong to one class, then

$a \equiv b \equiv c \pmod 9,$

so any common difference \(d\) in a valid progression must satisfy

$d \equiv 0 \pmod 9.$

There is another immediate restriction: every four-digit prime is odd, so the difference between any two of them in an arithmetic progression must be even. Hence every valid common difference is a multiple of both \(2\) and \(9\), and therefore

$18 \mid d.$

The code does not explicitly use this divisibility test, but it explains why such progressions are rare and why a simple grouped search finishes quickly.

Worked Examples

The famous example belongs to the signature class \(\sigma=1478\). Inside that class we have

$1487,\ 4817,\ 8147,$

and indeed

$4817-1487=3330,\qquad 8147-4817=3330.$

The same search also finds the other class with the required structure, namely \(\sigma=2699\). In that class,

$2969,\ 6299,\ 9629$

are all prime, all use the same digits, and form the arithmetic progression

$6299-2969=3330,\qquad 9629-6299=3330.$

Concatenating these three terms gives the required 12-digit result \(296962999629\).

How the Code Works

Generating the Four-Digit Primes

The C++, Python, and Java implementations iterate through every integer from \(1000\) to \(9999\). Each candidate is tested for primality by trial division: even numbers are handled immediately, and odd divisors are checked only up to \(\sqrt{n}\). Every surviving prime is then sent to the grouping phase.

Building the Signature Groups

For each four-digit prime, the decimal digits are sorted to form the canonical signature. A map from signature to list of primes collects all primes with the same multiset of digits. This is the implementation form of the mathematical classes \(G_s\).

Searching for the Nontrivial Progression

Each group with at least three elements is sorted. The implementation scans all pairs \(a<b\) in that group, computes \(c=2b-a\), discards the pair if \(c\) leaves the four-digit range, and otherwise checks whether \(c\) is still in the same group. Once a valid triple is found, the known example beginning with \(1487\) is skipped, and the remaining triple is concatenated in order \(abc\).

Because the search is performed inside a prime-only group, the membership test for \(c\) automatically confirms the prime condition and the permutation condition at the same time. That is why the code stays short while still matching the mathematics exactly.

Complexity Analysis

Let \(R=9000\) be the number of four-digit integers checked. The primality phase uses trial division, so its worst-case running time is \(O(R\sqrt{9999})\), which is tiny at this scale. Sorting four digits is constant-time work, so grouping the primes adds only linear overhead in the number of primes found.

If the signature classes are \(G_1,G_2,\dots\), the progression search costs

$\sum_i \binom{|G_i|}{2}$

pair checks, plus a membership lookup for the computed third term. In the C++ and Java implementations that lookup is logarithmic in the class size after sorting; in the Python implementation it is linear in the class size, but the classes are so small that the practical cost is still negligible. Memory usage is \(O(P)\), where \(P\) is the number of four-digit primes stored across all groups.

Footnotes and References

1. Problem page: Project Euler 49
2. Prime numbers: Wikipedia - Prime number
3. Arithmetic progressions: Wikipedia - Arithmetic progression
4. Permutations: Wikipedia - Permutation
5. Primality testing by trial division: Wikipedia - Primality test
6. Modular arithmetic: Wikipedia - Modular arithmetic