admissible prime sets

definition

A finite set of integers H = {h₁, ..., h_k} is called admissible if, for every prime p, the residues h₁, ..., h_k modulo p do not cover all residue classes. Equivalently, there is no prime that is forced to divide at least one of n+h₁, ..., n+h_k for every integer n.

Admissibility is the basic local condition needed for the numbers n+h₁, ..., n+h_k to be simultaneously prime. The classical prime k-tuple conjecture predicts that every admissible set occurs infinitely often as a pattern of primes.

A natural computational problem is therefore the following: for a given interval length n, I try to maximize the number of surviving positions (the 1s), with the additional condition that both endpoints of the interval must survive. If ρ(n) positions can be kept, they form an admissible set spanning the whole interval, so its diameter is automatically n - 1. Thus, improvements in ρ(n) directly lead to improved upper bounds for the corresponding H_k.

calculations

The computational idea is simple: I take an interval of fixed length and, for every prime, cross out one residue class. In the end I want as many positions as possible to survive, including both endpoints of the interval.

Sounds easy, but it is not. Even for fairly small interval lengths, a complete search becomes astronomically expensive. As far as I know, an exhaustive search has nevertheless been carried out for interval lengths up to 2331.

One particularly nice milestone is n = 3159. This is the first length for which ρ(3159) > π(3159). According to the Hardy–Littlewood heuristic, an interval of this length containing 447 primes should only start to appear around numbers of order 10¹¹⁹⁸ – so the primes involved would have roughly 1200 decimal digits.

results

The results are available in two forms. The CSV files below give a compact overview of the best known diameters and the number of patterns found for them, while the complete collection of individual patterns is available further below in compact form. At present the collection contains 141,126,192 patterns for 1361 ≤ n ≤ 9999. Further tests are still running, so I expect that a few more patterns will be found. The current status is from 24 September 2026, an increase of 9,652,950 patterns compared with the results from 18 September 2026.

A useful external reference is the table of narrow admissible tuples maintained at MIT, which lists the best diameters currently recorded there for given values of k. Comparing my present computations with that table, I found 25 values of k for which my admissible patterns appear to give a smaller diameter than the value currently listed. Since these are computational results and the external table may change, I regard them as provisional improvements until independently checked. The corresponding 25 patterns are available in this ZIP archive.

The data is also closely related to two integer sequences in the OEIS. A008407 (CSV) gives the smallest known diameter s(u) of an admissible u-tuple, while A083409 (CSV) gives the number of constellations attaining that diameter. Both files are stored in the simple format u,s(u).

For interval lengths n > 2331 my search is no longer exhaustive, so the A083409 counts should be regarded as lower bounds on the number of patterns found at the listed diameter. Beyond u = 342, the A008407 entries are best-known upper bounds rather than proven minima.

For completeness, the full interval-by-interval pattern counts, indexed by u = (n + 1) / 2 up to u = 5000, are available here.

compact representation of the patterns

The CSV files above contain only summary information. The complete collection of individual admissible patterns is available in the three archives below. Since storing more than 100 million patterns as full 0/1 strings would be unnecessarily large, I use a compact representation based on the residue classes that generate each pattern. The following sections explain this format in detail.

The collection is split by interval length into three archives: n < 8000, 8000 < n < 9000, and 9000 < n < 10000.

I treat the prime 2 separately. Once one parity class is removed, only every second position of the original interval remains. An interval of odd length n is therefore represented internally by a pattern of length

k = (n + 1) / 2,   or equivalently   n = 2k - 1.

For the odd primes I use the first ten primes

3, 5, 7, 11, 13, 17, 19, 23, 29, 31

as a base wheel. Their product is

P = 3·5·7·11·13·17·19·23·29·31 = 100280245065.

With respect to these ten primes, starts that differ by a multiple of P have the same residue structure. I therefore only need one canonical start s modulo P. Equivalently, s fixes all ten values s mod p at once by the Chinese Remainder Theorem. Residue choices for larger primes are stored separately.

I do not store reflected patterns a second time. If a pattern of length k starts at s, then the reflected pattern has start

s_mirror = (-s-k+1) mod P = (P - ((s+k-1) mod P)) mod P.

The two records describe the same 0/1 pattern in opposite directions, so I keep only one orientation. With both starts taken as representatives in 0,...,P-1, I always use the smaller of s and s_mirror.

expanded compact record

After decompression, one pattern is represented by a row of the form

k, s, m, r_(m+1), r_(m+2), ...

Here k is the compressed pattern length, s is the canonical start, and m tells me how many initial odd primes use residue class 0. If

p₁ = 3, p₂ = 5, p₃ = 7, ...

then for all 1 ≤ i ≤ m I set r_i = 0. For the following primes I store the residues r_m+1, r_m+2, ... explicitly.

A value of -1 means that I do not need an additional deletion for that prime: the positions that are still alive already miss at least one residue class modulo p. Trailing -1 entries are omitted completely.

I process the primes in increasing order and set a residue to -1 whenever the final pattern can still be reproduced without using that prime. This is the convention I use to make the compact description canonical and, at the same time, much smaller.

reconstructing the k-bit pattern

I start with an array A of k ones, indexed by j = 0,...,k-1. For each odd prime p_i with a stored residue r_i ≠ -1, I set to zero every position satisfying

(s + j) mod p_i = r_i.

Equivalently, I delete positions

j ≡ r_i - s  (mod p_i).

For the first m odd primes, r_i = 0, so I simply delete the positions for which (s + j) mod p_i = 0. After all stored primes have been processed, the surviving entries of A are exactly the 1s of the admissible pattern of length k.

A = [1, 0, 1, 1, 0, ...]

restoring the original interval of length n

The factor 2 was removed at the beginning by keeping only one parity class. With the convention used in my files, I restore the original interval by inserting a zero between every two consecutive entries of A:

A = [a₀, a₁, a₂, ..., a_k-1] becomes B = [a₀, 0, a₁, 0, a₂, 0, ..., 0, a_k-1]

The resulting array B has length n = 2k - 1. The inserted zeros are the residue class removed by the prime 2, and the number of 1s is unchanged.

front coding of consecutive records

There is one more compression step. Consecutive patterns often have a long common prefix, so I front-code the rows. The first integer c on each physical file line tells me how many entries to copy from the previously expanded row. I then append only the changed suffix stored on the new line.

previous expanded row: [x₀, x₁, x₂, x₃, x₄, ...]
stored next line: [c, x_c, x_c+1, ...]

Here the x-indices in the example are zero-based: the first c values x₀,...,x_c-1 are copied, and the stored suffix starts with x_c. If the copied prefix extends beyond the explicitly stored end of the previous record, I interpret the missing entries as -1.

Combining the parity reduction, the wheel modulo the first ten odd primes, the omission of unnecessary residue classes, and front coding lets me store millions of admissible patterns in a surprisingly small file while still being able to reconstruct every 0/1 pattern exactly.

One small edge case is worth mentioning for anyone writing a decoder. In a more general wheel representation, a short interval may cross the origin of the periodic wheel. It is then natural to write its start as a small negative integer instead of as the equivalent large residue close to P. Such a start is perfectly valid; all congruences are interpreted modulo the corresponding prime (or modulo P for the base wheel). This edge case does not occur in the files published here with the product of the first ten odd primes, but a general-purpose decoder should still be prepared to handle negative start values.