Project Euler

Digit Permutation Primes

A digit permutation prime group is a set of primes that are all permutations of the same digits. Find the number of such groups among primes below 10^6 where the group size is at least 4.

Source sync Apr 19, 2026

Problem #0983

Level Level 39

Solved By 52

Languages C++, Python

Answer 984.

Length 203 words

combinatoricsnumber_theorybrute_force

We say two circles on the plane harmonise if the circles intersect at two grid pointsA point with integer coordinates, in which case the two intersection points are called the harmony points.

A set of circles on the plane is called consonant if it satisfies all the following requirements:

There are at least two circles in the set.
The center point of every circle is a grid point.
All circles have the same radius.
No circle is tangent to any other circle.
The circles are connected in the sense that a chain of circles can be formed between every pair of circles such that each circle harmonises with the next circle.

It can be proven that the number of unique harmony points of a consonant set of circles cannot be smaller than the number of circles. If the number of unique harmony points equals the number of circles, we say the consonant set is perfect.

For example, here are two perfect consonant sets of circles:

Let be the minimal radius such that a perfect consonant set of or more circles with radius exists.
You are given and .

Find .

Problem 983: Digit Permutation Primes

Mathematical Analysis

Grouping by Digit Signature

Two primes belong to the same group iff their sorted digit tuples are identical. For example, 1487, 4817, 8147 share the digit set $\{1, 4, 7, 8\}$ .

Proposition. All primes in a permutation group have the same number of digits and the same digit sum (hence the same residue modulo 9).

Density Estimate

Among $\pi(10^6) = 78498$ primes, 6-digit primes (the majority) have roughly $6! / (\text{digit repeats})$ potential permutations, but most are not prime. Groups of size $\ge 4$ are relatively rare.

Derivation

Editorial

Count the number of “digit permutation groups” of size >= 4 among primes below 10^6. A digit permutation group is a set of primes that are anagrams of each other (i.e., they share the same multiset of digits). We count how many such groups contain at least 4 primes. Key observations:. We sieve primes below $10^6$ . We then iterate over each prime, compute sorted digit tuple as key. Finally, group by key using a hash map.

Pseudocode

Sieve primes below $10^6$
For each prime, compute sorted digit tuple as key
Group by key using a hash map
Count groups with $\ge 4$ members

Complexity Analysis

$O(N \log \log N)$ sieve + $O(\pi(N) \log N)$ for grouping.

Answer

\boxed{984.}

C++ project_euler/problem_983/solution.cpp

#include <bits/stdc++.h>
using namespace std;
int main() {
    const int N = 1000000;
    vector<bool> is_p(N, true); is_p[0]=is_p[1]=false;
    for(int i=2;(long long)i*i<N;i++) if(is_p[i]) for(int j=i*i;j<N;j+=i) is_p[j]=false;
    map<string,int> groups;
    for(int p=2;p<N;p++){
        if(!is_p[p]) continue;
        string s=to_string(p); sort(s.begin(),s.end());
        groups[s]++;
    }
    int cnt=0;
    for(auto&[k,v]:groups) if(v>=4) cnt++;
    cout<<cnt<<endl;
    return 0;
}

Python project_euler/problem_983/solution.py

"""
Problem 983: Digit Permutation Primes

Count the number of "digit permutation groups" of size >= 4 among primes below 10^6.

A digit permutation group is a set of primes that are anagrams of each other
(i.e., they share the same multiset of digits). We count how many such groups
contain at least 4 primes.

Key observations:
    - Group primes by their sorted digit tuple
    - Most groups are small (size 1-2)
    - Larger groups tend to appear for numbers with more digits
    - The largest groups tend to use digits that avoid divisibility patterns

Answer: computed by sieve + grouping

Methods:
    - sieve_primes(N): Sieve of Eratosthenes up to N
    - group_by_digits(primes): Group primes by sorted digit tuple
    - count_groups_by_size(groups): Distribution of group sizes
    - largest_groups(groups, top_k): Find the largest permutation groups
"""

from math import isqrt
from collections import defaultdict, Counter


def sieve_primes(N):
    """Return a boolean sieve and list of primes up to N."""
    is_p = bytearray(b'\x01') * N
    is_p[0] = is_p[1] = 0
    for i in range(2, isqrt(N - 1) + 1):
        if is_p[i]:
            is_p[i * i::i] = bytearray(len(is_p[i * i::i]))
    primes = [p for p in range(2, N) if is_p[p]]
    return is_p, primes


def group_by_digits(primes):
    """Group primes by their sorted digit tuple."""
    groups = defaultdict(list)
    for p in primes:
        key = tuple(sorted(str(p)))
        groups[key].append(p)
    return groups


def largest_groups(groups, top_k=10):
    """Return the top_k largest digit permutation groups."""
    sorted_groups = sorted(groups.values(), key=len, reverse=True)
    return sorted_groups[:top_k]

# Verification

N = 10**6
is_p, primes = sieve_primes(N)

# Basic sieve verification
assert is_p[2] and is_p[3] and is_p[5] and is_p[7]
assert not is_p[4] and not is_p[6] and not is_p[9]

groups = group_by_digits(primes)

# Known: {1478, 1487, 4817, 4871, 7481, 7841, 8147, 8741} has 8 primes (if all prime)
# Verify small example: 13, 31 are both prime
assert 13 in groups[tuple(sorted('13'))]
assert 31 in groups[tuple(sorted('13'))]

count = sum(1 for g in groups.values() if len(g) >= 4)
print(count)