11  Worked examples

Three larger runs, putting the whole pipeline together at \(e^{20}\) and \(e^{21}\): many interval lengths at once, the discrepancy measures across all of them, and a nested animation. The heavy computations were run once and saved; the cells that took minutes to hours are displayed but not executed, and everything downstream retrieves from the database. The folded cell below defines the pick helper of Section 6.2.

Setup: numeric display and the pick helper
import numpy as np

# NumPy 2 displays scalars inside containers as np.float64(...); restore the
# plain numeric display so statistics read cleanly.
np.set_printoptions(legacy="1.25")


def pick(found, lower_bound):
    """Return the retrieved dataset whose data begins at the given lower bound.

    Introduced in the Datasets chapter: accepts either return shape of
    ``retrieve`` (one dataset, or a list of them).
    """
    if isinstance(found, dict):
        found = [found]
    return next(d for d in found if d['header']['lower_bound'] == lower_bound)
import matplotlib.pyplot as plt
import pandas as pd

import primes_in_intervals as pii
from primes_in_intervals import (
    analyze,
    compare,
    intervals,
    nest,
    plot_distribution_frame,
    retrieve,
    save,
    score,
)

All the windows in this chapter are centred at a point \(x_0\) of the form \([e^k]\), and we describe them in the text boxes of the figures as \(x_0 - K < a \le x_0 + K\). The small function below builds such a text box. Given the dataset, the checkpoint, \(H\) and the predictions being drawn, it returns the text, quoting \(\mu\) from the very predictions on the plot. (In the notation of Chapter 8, the window is \(M < a \le M + N\) with \(M = x_0 - K\) and \(N = 2K\).)

def centred_overlay(x0, x0_label, variable=r'$X = \pi(a + H) - \pi(a)$', start='a', extra=''):
    """Return an overlay function for windows centred at x0."""
    def overlay(X, c, H, pred):
        upper = c[1] if isinstance(c, tuple) else c
        s = X['statistics'][c]
        med = int(s['med']) if s['med'] == int(s['med']) else s['med']
        return (variable + '\n\n'
                + fr'$x_0 - K < {start} \leq x_0 + K$' + '\n\n'
                + fr'$H = {H}$, $x_0 = {x0_label}$, $K = {upper - x0}$' + '\n\n'
                + extra
                + fr'$\mu = {pred["mu"]:.5f}$' + '\n\n'
                + r'$\mathbb{E}[X] = $' + f"{s['mean']:.5f}" + '\n\n'
                + r'$\mathrm{Var}(X) = $' + f"{s['var']:.5f}" + '\n\n'
                + fr'median : ${med}$' + '\n\n'
                + fr"mode(s): ${s['mode']}$")
    return overlay

11.1 Example 4

Ten interval lengths over one window about \(e^{20}\).

N = int(np.exp(20))
HH = [20,30,40,50,60,70,80,90,100,200]
step = 10**3
A = N - 10**5
B = N + 10**5
C = list(range(A,B+1,step))

Ten passes over the primes up to half a billion: the computation below took a little under an hour, so it is shown, not run.

exp20 = { H : {} for H in HH}
start = timer()
for H in HH:
    exp20[H] = intervals(C,H,interval_type='overlap')
end = timer()
end - start
3146.539329699939
for H in HH:
    save(exp20[H])

Retrieval brings all ten datasets back. Other datasets share some of these interval lengths, so, as always, we select by lower bound with pick rather than by position; the printed summaries list everything each length matched.

getexp20 = {}
for H in HH:
    getexp20[H] = pick(retrieve(H), A)
Found 2 datasets corresponding to interval of length 20 (overlap intervals).

 [0] 'header' : {'interval_type': 'overlap', 'lower_bound': 485065195, 'upper_bound': 485265195, 'interval_length': 20, 'no_of_checkpoints': 201, 'contents': ['data']}


 [1] 'header' : {'interval_type': 'overlap', 'lower_bound': 1318715734, 'upper_bound': 1318915734, 'interval_length': 20, 'no_of_checkpoints': 200, 'contents': ['data']}

Found 2 datasets corresponding to interval of length 30 (overlap intervals).

 [0] 'header' : {'interval_type': 'overlap', 'lower_bound': 485065195, 'upper_bound': 485265195, 'interval_length': 30, 'no_of_checkpoints': 201, 'contents': ['data']}


 [1] 'header' : {'interval_type': 'overlap', 'lower_bound': 1318715734, 'upper_bound': 1318915734, 'interval_length': 30, 'no_of_checkpoints': 200, 'contents': ['data']}

Found 2 datasets corresponding to interval of length 40 (overlap intervals).

 [0] 'header' : {'interval_type': 'overlap', 'lower_bound': 485065195, 'upper_bound': 485265195, 'interval_length': 40, 'no_of_checkpoints': 201, 'contents': ['data']}


 [1] 'header' : {'interval_type': 'overlap', 'lower_bound': 1318715734, 'upper_bound': 1318915734, 'interval_length': 40, 'no_of_checkpoints': 200, 'contents': ['data']}

Found 2 datasets corresponding to interval of length 50 (overlap intervals).

 [0] 'header' : {'interval_type': 'overlap', 'lower_bound': 485065195, 'upper_bound': 485265195, 'interval_length': 50, 'no_of_checkpoints': 201, 'contents': ['data']}


 [1] 'header' : {'interval_type': 'overlap', 'lower_bound': 1318715734, 'upper_bound': 1318915734, 'interval_length': 50, 'no_of_checkpoints': 200, 'contents': ['data']}

Found 3 datasets corresponding to interval of length 60 (overlap intervals).

 [0] 'header' : {'interval_type': 'overlap', 'lower_bound': 2669017, 'upper_bound': 3869017, 'interval_length': 60, 'no_of_checkpoints': 1201, 'contents': ['data']}


 [1] 'header' : {'interval_type': 'overlap', 'lower_bound': 485065195, 'upper_bound': 485265195, 'interval_length': 60, 'no_of_checkpoints': 201, 'contents': ['data']}


 [2] 'header' : {'interval_type': 'overlap', 'lower_bound': 1318715734, 'upper_bound': 1318915734, 'interval_length': 60, 'no_of_checkpoints': 200, 'contents': ['data']}

Found 2 datasets corresponding to interval of length 70 (overlap intervals).

 [0] 'header' : {'interval_type': 'overlap', 'lower_bound': 485065195, 'upper_bound': 485265195, 'interval_length': 70, 'no_of_checkpoints': 201, 'contents': ['data']}


 [1] 'header' : {'interval_type': 'overlap', 'lower_bound': 1318715734, 'upper_bound': 1318915734, 'interval_length': 70, 'no_of_checkpoints': 200, 'contents': ['data']}

Found 2 datasets corresponding to interval of length 80 (overlap intervals).

 [0] 'header' : {'interval_type': 'overlap', 'lower_bound': 485065195, 'upper_bound': 485265195, 'interval_length': 80, 'no_of_checkpoints': 201, 'contents': ['data']}


 [1] 'header' : {'interval_type': 'overlap', 'lower_bound': 1318715734, 'upper_bound': 1318915734, 'interval_length': 80, 'no_of_checkpoints': 200, 'contents': ['data']}

Found 3 datasets corresponding to interval of length 90 (overlap intervals).

 [0] 'header' : {'interval_type': 'overlap', 'lower_bound': 65559979, 'upper_bound': 65759959, 'interval_length': 90, 'no_of_checkpoints': 203, 'contents': ['data']}


 [1] 'header' : {'interval_type': 'overlap', 'lower_bound': 485065195, 'upper_bound': 485265195, 'interval_length': 90, 'no_of_checkpoints': 201, 'contents': ['data']}


 [2] 'header' : {'interval_type': 'overlap', 'lower_bound': 1318715734, 'upper_bound': 1318915734, 'interval_length': 90, 'no_of_checkpoints': 200, 'contents': ['data']}

Found 3 datasets corresponding to interval of length 100 (overlap intervals).

 [0] 'header' : {'interval_type': 'overlap', 'lower_bound': 2000000, 'upper_bound': 3000000, 'interval_length': 100, 'no_of_checkpoints': 101, 'contents': ['data']}


 [1] 'header' : {'interval_type': 'overlap', 'lower_bound': 485065195, 'upper_bound': 485265195, 'interval_length': 100, 'no_of_checkpoints': 201, 'contents': ['data']}


 [2] 'header' : {'interval_type': 'overlap', 'lower_bound': 1318715734, 'upper_bound': 1318915734, 'interval_length': 100, 'no_of_checkpoints': 200, 'contents': ['data']}

Found 1 dataset corresponding to interval of length 200 (overlap intervals).

 'header' : {'interval_type': 'overlap', 'lower_bound': 485065195, 'upper_bound': 485265195, 'interval_length': 200, 'no_of_checkpoints': 201, 'contents': ['data']}

We analyze, compare and score all ten.

for H in HH:
    analyze(getexp20[H])
    compare(getexp20[H])
    score(getexp20[H])

At the final checkpoint, which covers all two hundred thousand starting points of the window, here are \(\mu\), the discrepancy \(E_1\) of each prediction on the central range, and the ratio \(E_1(F)/E_1(F_0)\), for every length:

rows = {}
for H in HH:
    X = getexp20[H]
    c = max(X['data'])
    s = X['scores'][c]
    rows[H] = {'mu': X['prediction_parameters'][c]['mu'],
               'm range': f"{s['central']['F']['m_lo']}..{s['central']['F']['m_hi']}",
               'E1(Binom)': s['central']['B']['E1'],
               'E1(F0)': s['central']['F0']['E1'],
               'E1(F)': s['central']['F']['E1'],
               'E1(F)/E1(F0)': s['ratio']['central']['E1']}
pd.DataFrame.from_dict(rows, orient='index').rename_axis('H')
mu m range E1(Binom) E1(F0) E1(F) E1(F)/E1(F0)
H
20 1.0 0..5 0.119050 0.147207 0.028567 0.194057
30 1.5 0..6 0.123927 0.150299 0.030081 0.200142
40 2.0 0..8 0.126638 0.149867 0.038652 0.257909
50 2.5 0..8 0.150881 0.176639 0.045277 0.256328
60 3.0 0..9 0.148067 0.173290 0.040332 0.232743
70 3.5 0..10 0.149944 0.174148 0.044112 0.253303
80 4.0 0..12 0.159827 0.185461 0.050952 0.274732
90 4.5 0..13 0.164302 0.187783 0.058393 0.310961
100 5.0 0..14 0.176412 0.201519 0.063056 0.312905
200 10.0 0..20 0.228111 0.252274 0.110444 0.437793

The correction reduces \(E_1\) at every length, by a factor of between two and five. On the whole it helps less as \(H\) grows (the ratio rises from about \(0.2\) at \(H = 20\) to \(0.44\) at \(H = 200\), though not steadily).

Now the plot, for \(H = 90\). Besides \(F\) and \(F_0\) we draw the local expression \(Q(m; \mu, H)\), evaluated at the single averaged parameter; the density of primes barely changes across a window this narrow, so the purple markers of \(Q(m; \mu, H)\) sit almost exactly on the green markers of \(F\).

H = 90 # 20,30,40,50,70,80,200
X = getexp20[H]
C = list(X['distribution'].keys())

plt.rcParams.update({'font.size': 22})
fig, ax = plt.subplots(figsize=(22, 11))
fig.suptitle('Primes in intervals')
plot_distribution_frame(ax, X, C[-1], models=('F', 'F0', 'Q_mu'),
                        overlay=centred_overlay(N, r'[\exp(20)]'), overlay_position=(0.70, 0.18))
plt.rcParams['savefig.facecolor'] = 'white'
plt.show()

11.2 Example 5

The same window about \(e^{20}\), now at the single length \(H = 76\). The computation ran once (several minutes) and was saved:

x0 = int(np.exp(20))
K = 10**5
H = 76
A = x0 - K
B = x0 + K
step = 10**3
C = list(range(A, B + 1, step))
N_exp20_H_76 = intervals(C, H)
N_exp20_H_76 = pick(retrieve(76), 485065195)
Found 1 dataset corresponding to interval of length 76 (overlap intervals).

 'header' : {'interval_type': 'overlap', 'lower_bound': 485065195, 'upper_bound': 485265195, 'interval_length': 76, 'no_of_checkpoints': 201, 'contents': ['data']}
analyze(N_exp20_H_76)['header']
{'interval_type': 'overlap',
 'lower_bound': 485065195,
 'upper_bound': 485265195,
 'interval_length': 76,
 'no_of_checkpoints': 201,
 'contents': ['data', 'distribution', 'statistics']}

The plot shows the default trio, \(F\), \(F_0\) and \(\mathrm{Binom}(H, \mu/H)\), with the centred text box on the final frame. Here \(\mu = 76/20 = 3.8\).

X = N_exp20_H_76
C = list(X['distribution'].keys())

fig, ax = plt.subplots(figsize=(22, 11))
fig.suptitle('Primes in intervals')
plot_distribution_frame(ax, X, C[-1],
                        overlay=centred_overlay(int(np.exp(20)), r'[\exp(20)]'),
                        overlay_position=(0.70, 0.18))
plt.show()

The full animation is saved with save_gif or save_mp4 (or pii animate); the frames step through the two hundred checkpoints of the window.

11.3 Example 6 (nested intervals)

The largest run: nested intervals about \(e^{21}\), thirteen interval lengths from \(20\) to \(140\). The checkpoints are placed symmetrically about \(x_0 = [e^{21}]\), a thousand apart, with \(x_0\) itself excluded, so that nesting pairs them off exactly.

N = int(np.exp(21))
K = 199
k = (K - 1)//2 # = 99
Delta = 10**3
D = []
for j in range(k + 1):
    D.extend([N - (j + 1)*Delta, N + (j + 1)*Delta])
C = sorted(D)
HH = list(range(20,141,10))
EXP21 = {H : {} for H in HH}
for H in HH:
    EXP21[H] = intervals(C, H)
# Takes a few hours...
for H in HH:
    save(EXP21[H])
EXP21 = {}
for H in HH:
    EXP21[H] = pick(retrieve(H), C[0])
Found 2 datasets corresponding to interval of length 20 (overlap intervals).

 [0] 'header' : {'interval_type': 'overlap', 'lower_bound': 485065195, 'upper_bound': 485265195, 'interval_length': 20, 'no_of_checkpoints': 201, 'contents': ['data']}


 [1] 'header' : {'interval_type': 'overlap', 'lower_bound': 1318715734, 'upper_bound': 1318915734, 'interval_length': 20, 'no_of_checkpoints': 200, 'contents': ['data']}

Found 2 datasets corresponding to interval of length 30 (overlap intervals).

 [0] 'header' : {'interval_type': 'overlap', 'lower_bound': 485065195, 'upper_bound': 485265195, 'interval_length': 30, 'no_of_checkpoints': 201, 'contents': ['data']}


 [1] 'header' : {'interval_type': 'overlap', 'lower_bound': 1318715734, 'upper_bound': 1318915734, 'interval_length': 30, 'no_of_checkpoints': 200, 'contents': ['data']}

Found 2 datasets corresponding to interval of length 40 (overlap intervals).

 [0] 'header' : {'interval_type': 'overlap', 'lower_bound': 485065195, 'upper_bound': 485265195, 'interval_length': 40, 'no_of_checkpoints': 201, 'contents': ['data']}


 [1] 'header' : {'interval_type': 'overlap', 'lower_bound': 1318715734, 'upper_bound': 1318915734, 'interval_length': 40, 'no_of_checkpoints': 200, 'contents': ['data']}

Found 2 datasets corresponding to interval of length 50 (overlap intervals).

 [0] 'header' : {'interval_type': 'overlap', 'lower_bound': 485065195, 'upper_bound': 485265195, 'interval_length': 50, 'no_of_checkpoints': 201, 'contents': ['data']}


 [1] 'header' : {'interval_type': 'overlap', 'lower_bound': 1318715734, 'upper_bound': 1318915734, 'interval_length': 50, 'no_of_checkpoints': 200, 'contents': ['data']}

Found 3 datasets corresponding to interval of length 60 (overlap intervals).

 [0] 'header' : {'interval_type': 'overlap', 'lower_bound': 2669017, 'upper_bound': 3869017, 'interval_length': 60, 'no_of_checkpoints': 1201, 'contents': ['data']}


 [1] 'header' : {'interval_type': 'overlap', 'lower_bound': 485065195, 'upper_bound': 485265195, 'interval_length': 60, 'no_of_checkpoints': 201, 'contents': ['data']}


 [2] 'header' : {'interval_type': 'overlap', 'lower_bound': 1318715734, 'upper_bound': 1318915734, 'interval_length': 60, 'no_of_checkpoints': 200, 'contents': ['data']}

Found 2 datasets corresponding to interval of length 70 (overlap intervals).

 [0] 'header' : {'interval_type': 'overlap', 'lower_bound': 485065195, 'upper_bound': 485265195, 'interval_length': 70, 'no_of_checkpoints': 201, 'contents': ['data']}


 [1] 'header' : {'interval_type': 'overlap', 'lower_bound': 1318715734, 'upper_bound': 1318915734, 'interval_length': 70, 'no_of_checkpoints': 200, 'contents': ['data']}

Found 2 datasets corresponding to interval of length 80 (overlap intervals).

 [0] 'header' : {'interval_type': 'overlap', 'lower_bound': 485065195, 'upper_bound': 485265195, 'interval_length': 80, 'no_of_checkpoints': 201, 'contents': ['data']}


 [1] 'header' : {'interval_type': 'overlap', 'lower_bound': 1318715734, 'upper_bound': 1318915734, 'interval_length': 80, 'no_of_checkpoints': 200, 'contents': ['data']}

Found 3 datasets corresponding to interval of length 90 (overlap intervals).

 [0] 'header' : {'interval_type': 'overlap', 'lower_bound': 65559979, 'upper_bound': 65759959, 'interval_length': 90, 'no_of_checkpoints': 203, 'contents': ['data']}


 [1] 'header' : {'interval_type': 'overlap', 'lower_bound': 485065195, 'upper_bound': 485265195, 'interval_length': 90, 'no_of_checkpoints': 201, 'contents': ['data']}


 [2] 'header' : {'interval_type': 'overlap', 'lower_bound': 1318715734, 'upper_bound': 1318915734, 'interval_length': 90, 'no_of_checkpoints': 200, 'contents': ['data']}

Found 3 datasets corresponding to interval of length 100 (overlap intervals).

 [0] 'header' : {'interval_type': 'overlap', 'lower_bound': 2000000, 'upper_bound': 3000000, 'interval_length': 100, 'no_of_checkpoints': 101, 'contents': ['data']}


 [1] 'header' : {'interval_type': 'overlap', 'lower_bound': 485065195, 'upper_bound': 485265195, 'interval_length': 100, 'no_of_checkpoints': 201, 'contents': ['data']}


 [2] 'header' : {'interval_type': 'overlap', 'lower_bound': 1318715734, 'upper_bound': 1318915734, 'interval_length': 100, 'no_of_checkpoints': 200, 'contents': ['data']}

Found 1 dataset corresponding to interval of length 110 (overlap intervals).

 'header' : {'interval_type': 'overlap', 'lower_bound': 1318715734, 'upper_bound': 1318915734, 'interval_length': 110, 'no_of_checkpoints': 200, 'contents': ['data']}

Found 1 dataset corresponding to interval of length 120 (overlap intervals).

 'header' : {'interval_type': 'overlap', 'lower_bound': 1318715734, 'upper_bound': 1318915734, 'interval_length': 120, 'no_of_checkpoints': 200, 'contents': ['data']}

Found 1 dataset corresponding to interval of length 130 (overlap intervals).

 'header' : {'interval_type': 'overlap', 'lower_bound': 1318715734, 'upper_bound': 1318915734, 'interval_length': 130, 'no_of_checkpoints': 200, 'contents': ['data']}

Found 1 dataset corresponding to interval of length 140 (overlap intervals).

 'header' : {'interval_type': 'overlap', 'lower_bound': 1318715734, 'upper_bound': 1318915734, 'interval_length': 140, 'no_of_checkpoints': 200, 'contents': ['data']}
NEXP21 = {}
for H in HH:
    NEXP21[H] = nest(EXP21[H])
for H in HH:
    analyze(NEXP21[H])

The plot, for \(H = 60\), is the nested version: each frame is one of the hundred nested intervals, the innermost first, the sample growing outward from the centre, with the vertical axis rounded at the third decimal for these smaller proportions. Here \(\mu = 60/21 = 2.857\ldots\).

# HH = [20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140]
X = NEXP21[HH[4]]
C = list(X['distribution'].keys())

plt.rcParams.update({'font.size': 22})
fig, ax = plt.subplots(figsize=(22, 11))
fig.suptitle('Primes in intervals')
plot_distribution_frame(ax, X, C[-1], ylim_decimals=3,
                        overlay=centred_overlay(N, '[e^{21}]'), overlay_position=(0.70, 0.15))
plt.rcParams['savefig.facecolor'] = 'white'
plt.show()

The animation, innermost interval outward:

Animation of the distribution of primes in intervals of length 60 about e^21, the nested sample growing outward from the centre, with the predictions F, F0 and the Binomial marked at each m.

Animated distribution of primes in overlapping intervals of length 60 in nested ranges about e^21.

11.4 Supplementary examples

Four further examples, at sizes where everything runs in seconds, so every cell below computes live: the Nachlass tables in full, the nested pipeline at \(e^{17}\) for overlapping and for prime-starting intervals, and the starting points \(1 \le n \le N\) of the paper’s main statement. (These complement Section 9.0.3’s one-line Goldschmidt table.)

Example 1

Tables from Gauss’s Nachlass. Create data for primes in disjoint intervals of length \(100\) (starting at multiples of \(100\)), up to \(10^7\). Checkpoints every \(10^5\).

By the bye, an interval of the form \([100k, 100k + 100)\) is referred to as a “Centade” in Gauss’s Nachlass. Analogous to the term Decade (a 10-year period from years ’0 to ’9), a Centade is a 100-year period from ’00 to ’99.

C = list(range(0,10*10**6 + 1, 10**5))
H = 100
nachlass = pii.intervals(C,H,'disjoint')

Gauss and Goldschmidt summarize their data in tables of primes up to \(1\) million, between \(1\) and \(2\) million, and so on. Let’s emulate that.

NACHLASS = { }
for i in range(1,11):
    NACHLASS[i] = pii.extract(nachlass, [(i - 1)*10**6, i*10**6] , option='narrow')
    pii.partition(NACHLASS[i])

Let’s display one of these tables: the one for primes between \(2\) and \(3\) million.

NACHLASS3df = pii.display(NACHLASS[3], count='partition', orient='columns')
NACHLASS3df
Table 11.1: Interval type: disjoint. Lower bound: 2000000. Upper bound: 3000000. Interval length: 100. Partial counts: non-cumulative.
  2000000 2100000 2200000 2300000 2400000 2500000 2600000 2700000 2800000 2900000 3000000 totals
0 0 0 0 0 0 0 0 1 0 0 0 1
1 0 3 2 2 4 1 3 4 2 2 2 25
2 0 10 9 9 10 9 5 10 7 15 13 97
3 0 32 27 29 33 37 35 28 43 30 43 337
4 0 69 70 73 86 78 88 70 93 84 65 776
5 0 119 145 138 135 146 136 159 137 141 152 1408
6 0 198 183 179 177 193 193 195 195 179 189 1881
7 0 203 201 205 194 190 179 201 188 222 212 1995
8 0 158 167 168 157 151 172 141 145 131 135 1525
9 0 114 110 113 113 102 88 96 86 110 103 1035
10 0 63 52 44 54 56 57 54 68 53 58 559
11 0 21 18 30 29 25 25 22 24 18 15 227
12 0 8 9 10 7 7 13 17 9 7 11 98
13 0 2 4 0 1 5 6 1 2 6 1 28
14 0 0 3 0 0 0 0 1 0 2 0 6
15 0 0 0 0 0 0 0 0 0 0 1 1
17 0 0 0 0 0 0 0 0 1 0 0 1
prime_tally 0 6872 6857 6849 6791 6770 6808 6765 6717 6747 6707 67883

Here’s the original: Gauss/Goldschmidt were only short by \(21\) primes in the end!

Facsimile of the Nachlass table tallying primes per Centade between two and three million.

Gauss’s and Goldschmidt’s tallies for the third million, from the Nachlass.

Example 2

Let’s look at a series of nested intervals centred at \(x_0 = [e^{17}] = 24{,}154{,}952\). Every starting point is within \(10^4\) of \(x_0\), and \(\log t\) changes by less than \(10^{-3}\) over such a window, so the density of primes throughout it is \(1/17\) to high accuracy, and the averaged parameter is \(\mu = H/17\) to seven decimal places. We’ll get data for intervals of length \(64, 68, 72, 76, 80\), for which \(\mu\) is about \(3.76\), \(4\), \(4.24\), \(4.47\) and \(4.71\).

N = int(np.exp(17))
HH = [64, 68, 72, 76, 80]
C = list(range(N - 10**4,N + 10**4 + 1, 10**2))
EXP17 = {}
for H in HH:
    EXP17[H] = pii.intervals(C, H, 'overlap')

Right now we have data for the intervals \((x_0 - 10^4, x_0 - 10^4 + 100k]\), \(k = 1,\ldots,200\). Let’s reconfigure the data to consider nested intervals \((x_0 - 100k, x_0 + 100k]\), \(k = 1,\ldots,100\), all centred at \(x_0\). We’ll analyze the data (get the distributions and statistics) while we’re at it.

EXP17NEST = {}
for H in HH:
    EXP17NEST[H] = pii.nest(EXP17[H])
    pii.analyze(EXP17NEST[H])

Let’s display what we have for \(H = 76\) for instance.

EXP17_76_NESTtable = pii.display(EXP17NEST[76])
EXP17_76_NESTtable.tail(5)
B - A A B H 0 1 2 3 4 5 6 7 8 9 10
95 19200 24145352 24164552 76 140 448 1562 2806 4296 4080 3392 1624 682 144 26
96 19400 24145252 24164652 76 140 448 1570 2836 4368 4134 3428 1624 682 144 26
97 19600 24145152 24164752 76 140 448 1572 2862 4382 4178 3508 1658 682 144 26
98 19800 24145052 24164852 76 140 448 1572 2864 4426 4260 3570 1668 682 144 26
99 20000 24144952 24164952 76 140 448 1584 2892 4550 4288 3578 1668 682 144 26

Let’s compare the data (for \(H = 76\)) to the three predictions of Chapter 8. There is a pleasing parallel between them. The naive prediction based purely on Cramér’s model is the Binomial distribution \(\mathrm{Binom}(H,\mu/H)\), whose probability mass function, for \(\mu\) of constant size and \(H\) large, expands as \[ \binom{H}{m}\left(\frac{\mu}{H}\right)^m\left(1 - \frac{\mu}{H}\right)^{H - m} = \frac{e^{-\mu}\mu^m}{m!}\left\{1 - \frac{C_2(m; \mu)}{2H} + O\left(\frac{1}{H^2}\right)\right\}, \qquad C_2(m; u) = (m - u)^2 - m. \] The local expression of Section 8.1 is \[ Q(m; \mu, H) = \frac{e^{-\mu}\mu^m}{m!}\left\{1 - \frac{C_2(m; \mu)}{2H}\big(\log H + \log 2\pi + \gamma - 1\big)\right\}. \] So the correction has exactly the shape of the Binomial’s first-order term, but it is larger by the factor \(\log H + \log 2\pi + \gamma - 1\), which is about \(5.7\) when \(H = 76\). The primes deviate from the Poisson law in the same direction as the independent Bernoulli trials of Cramér’s model do, but several times more strongly. The prediction \(F\) averages this local expression over the window, and \(F_0\) averages the Poisson term alone.

The table below shows tuples \((a,b,c,d)\), where \(a\) is the actual number, \(b\) is the Binomial prediction, \(c\) is \(F\), and \(d\) is \(F_0\). We’ll just show the last five rows, as the table is a bit long and hard to read.

pii.compare(EXP17NEST[76])
EXP17_76_NESTcompare = pii.display(EXP17NEST[76], comparisons='absolute').tail(5)
EXP17_76_NESTcompare
B - A A B H 0 1 2 3 4 5 6 7 8 9 10
95 19200 24145352 24164552 76 (140, 191.558699, 53.705239, 219.659212) (448, 909.903823, 572.001957, 982.005891) (1562, 2132.587093, 1854.550519, 2195.071999) (2806, 3287.738448, 3374.630177, 3271.087694) (4296, 3750.076681, 4178.113956, 3655.921553) (4080, 3375.069026, 3852.023233, 3268.823988) (3392, 2496.14481, 2772.650054, 2435.594353) (1624, 1560.090512, 1590.907981, 1555.505643) (682, 840.986295, 722.808621, 869.253157) (144, 397.132419, 243.827027, 431.785884) (26, 166.299201, 42.903146, 193.03369)
96 19400 24145252 24164652 76 (140, 193.554102, 54.264669, 221.947329) (448, 919.381988, 577.96031, 992.235119) (1570, 2154.801542, 1873.868754, 2217.937332) (2836, 3321.985723, 3409.782575, 3305.161524) (4368, 3789.13998, 4221.635976, 3694.004069) (4134, 3410.225995, 3892.148475, 3302.874238) (3428, 2522.146318, 2801.531825, 2460.965128) (1624, 1576.341455, 1607.47994, 1571.708827) (682, 849.746569, 730.337878, 878.307878) (144, 401.269215, 246.366891, 436.283653) (26, 168.031484, 43.350054, 195.044458)
97 19600 24145152 24164752 76 (140, 195.549505, 54.824098, 224.235445) (448, 928.860152, 583.918664, 1002.464347) (1572, 2177.01599, 1893.186988, 2240.802665) (2862, 3356.232998, 3444.934972, 3339.235354) (4382, 3828.203278, 4265.157997, 3732.086585) (4178, 3445.382964, 3932.273717, 3336.924488) (3508, 2548.147827, 2830.413597, 2486.335902) (1658, 1592.592398, 1624.051898, 1587.912011) (682, 858.506843, 737.867134, 887.362598) (144, 405.406011, 248.906756, 440.781423) (26, 169.763768, 43.796962, 197.055225)
98 19800 24145052 24164852 76 (140, 197.544908, 55.383528, 226.523562) (448, 938.338317, 589.877017, 1012.693575) (1572, 2199.230439, 1912.505223, 2263.667998) (2864, 3390.480274, 3480.087369, 3373.309184) (4426, 3867.266577, 4308.680017, 3770.169101) (4260, 3480.539933, 3972.398959, 3370.974738) (3570, 2574.149336, 2859.295368, 2511.706677) (1668, 1608.843341, 1640.623857, 1604.115195) (682, 867.267117, 745.396391, 896.417319) (144, 409.542807, 251.446621, 445.279193) (26, 171.496051, 44.24387, 199.065993)
99 20000 24144952 24164952 76 (140, 199.540311, 55.942958, 228.811679) (448, 947.816482, 595.835371, 1022.922803) (1584, 2221.444888, 1931.823457, 2286.533331) (2892, 3424.727549, 3515.239767, 3407.383014) (4550, 3906.329876, 4352.202037, 3808.251617) (4288, 3515.696902, 4012.524201, 3405.024988) (3578, 2600.150844, 2888.17714, 2537.077452) (1668, 1625.094284, 1657.195815, 1620.318379) (682, 876.027391, 752.925648, 905.472039) (144, 413.679603, 253.986486, 449.776963) (26, 173.228334, 44.690777, 201.076761)

Which prediction is closest, and by how much, is hard to see by glancing at the above table. The discrepancy measures of Section 8.4 answer it. Here is \(E_1\) for every tenth nested interval, on the central range, with the ratio \(E_1(F)/E_1(F_0)\):

pii.score(EXP17NEST[76])
Cn = list(EXP17NEST[76]['nested_interval_data'].keys())
rows = {}
for c in Cn[9::10]:
    s = EXP17NEST[76]['scores'][c]
    rows[c[1] - c[0]] = {name: s['central'][name]['E1'] for name in ('B', 'F', 'F0')}
    rows[c[1] - c[0]]['E1(F)/E1(F0)'] = s['ratio']['central']['E1']
pd.DataFrame.from_dict(rows, orient='index').rename_axis('N')
B F F0 E1(F)/E1(F0)
N
2000 0.252903 0.205301 0.273137 0.751640
4000 0.226536 0.179351 0.246018 0.729014
6000 0.244190 0.177684 0.267351 0.664608
8000 0.261960 0.166351 0.288065 0.577476
10000 0.233260 0.144351 0.259365 0.556553
12000 0.252460 0.155696 0.278565 0.558922
14000 0.214460 0.126070 0.240565 0.524058
16000 0.230710 0.133851 0.256815 0.521194
18000 0.218015 0.107979 0.244121 0.442316
20000 0.238860 0.128823 0.264965 0.486188

The older scoreboard winners gives, for each nested interval, the squared errors and the values of \(m\) at which each prediction’s count is closest to the actual count:

pii.winners(EXP17NEST[76])
EXP17_76_NESTwinners = pii.display(EXP17NEST[76], winners='show')
EXP17_76_NESTwinners.tail(10)
B - A A B H B sq error F sq error F0 sq error 1 2 3 B wins for m in F wins for m in F0 wins for m in most wins 2nd most wins least wins
90 18200 24145852 24164052 76 2.064317e+06 7.311341e+05 2.543409e+06 F B F0 [0] [1, 2, 4, 5, 6, 7, 8, 9, 10] [3] F BF0 BF0
91 18400 24145752 24164152 76 2.086650e+06 7.573589e+05 2.569252e+06 F B F0 [0] [1, 2, 4, 5, 6, 7, 8, 9, 10] [3] F BF0 BF0
92 18600 24145652 24164252 76 2.098268e+06 7.336675e+05 2.592654e+06 F B F0 [0] [1, 2, 4, 5, 6, 7, 8, 9, 10] [3] F BF0 BF0
93 18800 24145552 24164352 76 2.282776e+06 8.394240e+05 2.798942e+06 F B F0 [0] [1, 2, 4, 5, 6, 7, 8, 9, 10] [3] F BF0 BF0
94 19000 24145452 24164452 76 2.402493e+06 8.762179e+05 2.941348e+06 F B F0 [0] [1, 2, 4, 5, 6, 7, 8, 9, 10] [3] F BF0 BF0
95 19200 24145352 24164552 76 2.484292e+06 8.942258e+05 3.041489e+06 F B F0 [0] [1, 2, 4, 5, 6, 7, 8, 9, 10] [3] F BF0 BF0
96 19400 24145252 24164652 76 2.599513e+06 9.315693e+05 3.178316e+06 F B F0 [0] [1, 2, 4, 5, 6, 7, 8, 9, 10] [3] F BF0 BF0
97 19600 24145152 24164752 76 2.733792e+06 1.017456e+06 3.327595e+06 F B F0 [0] [1, 2, 4, 5, 6, 7, 8, 9, 10] [3] F BF0 BF0
98 19800 24145052 24164852 76 2.955308e+06 1.141022e+06 3.575408e+06 F B F0 [0] [1, 2, 4, 5, 6, 7, 8, 9, 10] [3] F BF0 BF0
99 20000 24144952 24164952 76 3.044339e+06 1.146790e+06 3.687316e+06 F B F0 [0] [1, 2, 4, 5, 6, 7, 8, 9, 10] [3] F BF0 BF0

Finally, let’s make an animated plot, with one frame for each of the intervals considered. Here is its final frame, drawn live:

# HH = [64, 68, 72, 76, 80]
X = EXP17NEST[HH[3]]
C = list(X['distribution'].keys())

plt.rcParams.update({'font.size': 22})
fig, ax = plt.subplots(figsize=(22, 11))
fig.suptitle('Primes in intervals')
plot_distribution_frame(ax, X, C[-1], ylim_decimals=3,
                        overlay=centred_overlay(N, '[e^{17}]'), overlay_position=(0.70, 0.15))
plt.rcParams['savefig.facecolor'] = 'white'
plt.show()

And the animation itself:

Animation of the distribution of primes in intervals of length 76 about e^17, the nested sample growing outward, with the predictions F, F0 and the Binomial marked at each m.

Animated distribution of primes in overlapping intervals of length 76 in nested ranges about e^17.

Example 3

Let’s go through the steps of Example 2, but instead of counting all intervals of the form \((a, a + H]\) as \(a\) runs over all integers in the range \((x_0 - 10^4, x_0 + 10^4]\), let’s consider only intervals of the form \((p, p + H]\) as \(p\) runs over only the primes in that range. We have not worked through the details of the second-order term in this case, but to first order we should still see the Poisson distribution.

First we generate the data using the 'prime_start' option in our intervals function.

N = int(np.exp(17))
HH = [64, 68, 72, 76, 80]
C = list(range(N - 10**4,N + 10**4 + 1, 10**2))
PSEXP17 = {}
for H in HH:
    PSEXP17[H] = pii.intervals(C, H, 'prime_start')

Let’s centre the intervals at \(x_0\) with the nest function.

PSEXP17NEST = {}
for H in HH:
    PSEXP17NEST[H] = pii.nest(PSEXP17[H])
    pii.analyze(PSEXP17NEST[H])

Let’s have a look at the data in a table.

PSEXP17_76_NESTtable = pii.display(PSEXP17NEST[76])
PSEXP17_76_NESTtable.tail(5)
pi(B) - pi(A) A B H 0 1 2 3 4 5 6 7 8 9
95 1160 24145352 24164552 76 8 35 102 187 269 268 178 80 29 4
96 1172 24145252 24164652 76 8 35 103 190 273 272 178 80 29 4
97 1187 24145152 24164752 76 8 35 104 191 275 277 183 81 29 4
98 1201 24145052 24164852 76 8 35 104 192 282 281 185 81 29 4
99 1212 24144952 24164952 76 8 35 105 196 287 282 185 81 29 4

Although \(F\) and \(F_0\) were derived for overlapping intervals, and the second-order term for intervals starting at primes might well be different, we can nevertheless compare the data to them…

pii.compare(PSEXP17NEST[76])
PSEXP17_76_NESTcompare = pii.display(PSEXP17NEST[76], comparisons='absolute').tail(5)
PSEXP17_76_NESTcompare
pi(B) - pi(A) A B H 0 1 2 3 4 5 6 7 8 9
95 1160 24145352 24164552 76 (8, 11.573338, 3.244692, 13.271077) (35, 54.973356, 34.558452, 59.329523) (102, 128.843804, 112.045761, 132.618933) (187, 198.634198, 203.883907, 197.628215) (269, 226.567133, 252.427718, 220.878594) (268, 203.91042, 232.726404, 197.491449) (178, 150.808749, 167.514274, 147.150492) (80, 94.255468, 96.117357, 93.978466) (29, 50.809589, 43.669688, 52.517378) (4, 23.993417, 14.731216, 26.087064)
96 1172 24145252 24164652 76 (8, 11.693062, 3.278257, 13.408364) (35, 55.542046, 34.915953, 59.943276) (103, 130.17667, 113.204855, 133.990853) (190, 200.689034, 205.99305, 199.672645) (273, 228.910931, 255.039039, 223.163545) (272, 206.019838, 235.133918, 199.534464) (178, 152.368839, 169.24718, 148.672739) (80, 95.230525, 97.111675, 94.950657) (29, 51.335205, 44.121443, 53.060661) (4, 24.241625, 14.883608, 26.35693)
97 1187 24145152 24164752 76 (8, 11.842717, 3.320215, 13.579973) (35, 56.252908, 35.362829, 60.710468) (104, 131.842754, 114.653722, 135.705753) (191, 203.25758, 208.62948, 202.228182) (275, 231.840678, 258.303191, 226.019733) (277, 208.656611, 238.143311, 202.088233) (183, 154.318953, 171.413313, 150.575547) (81, 96.449346, 98.354572, 96.165896) (29, 51.992226, 44.686137, 53.739766) (4, 24.551884, 15.074098, 26.694263)
98 1201 24145052 24164852 76 (8, 11.982396, 3.359375, 13.740141) (35, 56.91638, 35.779914, 61.426514) (104, 133.397766, 116.005999, 137.306327) (192, 205.654889, 211.090148, 204.61335) (282, 234.575109, 261.349732, 228.68551) (281, 211.117599, 240.952078, 204.471751) (185, 156.139058, 173.435037, 152.351501) (81, 97.586912, 99.514609, 97.300119) (29, 52.605445, 45.213185, 54.373596) (4, 24.84146, 15.251888, 27.009107)
99 1212 24144952 24164952 76 (8, 12.092143, 3.390143, 13.865988) (35, 57.437679, 36.107623, 61.989122) (105, 134.61956, 117.068501, 138.56392) (196, 207.538489, 213.02353, 206.487411) (287, 236.72359, 263.743443, 230.780048) (282, 213.051232, 243.158967, 206.344514) (185, 157.569141, 175.023535, 153.746894) (81, 98.480714, 100.426066, 98.191294) (29, 53.08726, 45.627294, 54.871606) (4, 25.068984, 15.391581, 27.256484)

…and see how far off each of these not-really-predictions is:

pii.score(PSEXP17NEST[76])
c = list(PSEXP17NEST[76]['nested_interval_data'].keys())[-1]
pd.DataFrame(PSEXP17NEST[76]['scores'][c]['central']).loc[['E1', 'E2', 'Einf']]
B F F0
E1 0.228532 0.127334 0.252768
E2 0.086119 0.048043 0.095390
Einf 0.056888 0.032047 0.062422

With only about twelve hundred intervals in the widest window (one for each prime in it), the data are noisy, and no conclusion should be drawn from these numbers. Here is the final frame, with \(F\) and \(F_0\) drawn alongside the Binomial and a caveat boxed at the top:

# HH = [64, 68, 72, 76, 80]
X = PSEXP17NEST[HH[3]]
C = list(X['distribution'].keys())
c = C[-1]
PI = sum(X['nested_interval_data'][c].values())

fig, ax = plt.subplots(figsize=(22, 11))
fig.suptitle('Primes in intervals')
plot_distribution_frame(ax, X, c, models=('F', 'F0', 'B_const'),
                        note='NB: $F$ and $F_0$ might not be applicable' + '\n' + 'in this case, without modification.',
                        overlay=centred_overlay(N, '[e^{17}]',
                                                variable=r'$X = \pi(p + H) - \pi(p)$, $p$ prime',
                                                start='p',
                                                extra=fr'$\pi(x_0 + K) - \pi(x_0 - K) = {PI}$' + '\n\n'),
                        overlay_position=(0.70, 0.15))
plt.show()

Animation of the distribution of primes in intervals of length 76 whose left endpoints are prime, about e^17, with F, F0 and the Binomial marked at each m and a caveat that F and F0 may not apply.

Animated distribution of primes in prime-starting intervals of length 76 in nested ranges about e^17.

Example 4

Every window so far has been narrow and far from the origin, so that the density of primes hardly changes across it. The paper’s main statement concerns instead all the starting points \(1 \le n \le N\), that is, \(M = 0\), across which the density \(1/\log t\) changes considerably. The predictions \(F\) and \(F_0\) average over that change exactly as they are defined, and nothing else about them needs adjusting. Here we take \(N = 10^7\) and \(H = 45\), which is \(3(\log N - 1)\) rounded to the nearest integer, so that the mean number of primes in an interval is close to \(3\).

In this setting \(\lambda = H/(\log N - 1)\) (Section 8.1). The prime number theorem gives \[ \frac{1}{N}\int_2^N \frac{dt}{\log t} = \frac{1}{\log N} + \frac{1}{(\log N)^2} + O\left(\frac{1}{(\log N)^3}\right) = \frac{1}{\log N - 1} + O\left(\frac{1}{(\log N)^3}\right), \] so \(\lambda\) is a two-term approximation to \(\mu\). The \(-1\) comes from averaging \(1/\log t\) over all \(t\) up to \(N\), most of which are smaller than \(N\); the density near \(N\) is \(1/\log N\).

Besides \(F\) and \(F_0\) we evaluate the local expressions \(Q(m; \lambda, H)\) and \(Q(m; \mu, H)\), and the Binomial of Cramér’s model with its varying density, \[ B_{\mathrm{avg}}(m) = \frac{1}{N}\int_e^N \binom{H}{m}\left(\frac{1}{\log t}\right)^m\left(1 - \frac{1}{\log t}\right)^{H - m}dt, \] the lower limit \(e\) keeping the probability \(1/\log t\) at most \(1\). With the density this far from constant, \(\mathrm{Binom}(H, \mu/H)\) would be a poor stand-in for Cramér’s model, and \(B_{\mathrm{avg}}\) takes its place.

The function run_cumulative counts the primes in \((n, n + H]\) for \(1 \le n \le N\) at each of a list of checkpoints \(N\), in one pass, and build_frames computes and scores the predictions at each checkpoint. This takes a few seconds.

from primes_in_intervals import build_frames, plot_cumulative_frame, run_cumulative

H = 45
cumulative = run_cumulative(H, checkpoints=[10**5, 10**6, 10**7])
models = ('F', 'F0', 'B_avg', 'Q_lambda', 'Q_mu')
frames = build_frames(cumulative, overlay_from=1, models=models)

Here is \(E_1\) for each prediction and each checkpoint, on the global range of Section 8.4, so that each sum covers essentially the whole of each prediction:

pd.DataFrame({f.N: {'mu': f.predictions['mu'], 'lambda': f.predictions['lambda'],
                    **{name: f.scores['global'][name]['E1'] for name in models}}
              for f in frames}).T.rename_axis('N')
mu lambda F F0 B_avg Q_lambda Q_mu
N
100000 4.332944 4.280445 0.121493 0.323014 0.276428 0.102700 0.102424
1000000 3.538193 3.511370 0.076730 0.250709 0.212824 0.063924 0.060958
10000000 2.992128 2.976565 0.049975 0.199310 0.167316 0.045322 0.043880

\(F\) improves on both \(F_0\) and \(B_{\mathrm{avg}}\), by a factor of between three and four at \(N = 10^7\). The local expressions \(Q(m; \lambda, H)\) and \(Q(m; \mu, H)\) do a little better still at these sizes: the average \(F\) arises naturally in the argument, but it need not be the most accurate approximation at a particular finite \(N\).

The final checkpoint:

plt.rcParams.update({'font.size': 22})
fig, ax = plt.subplots(figsize=(22, 11))
fig.suptitle('Primes in intervals')
plot_cumulative_frame(ax, frames[-1], H, models=('F', 'F0', 'B_avg'), y_max=0.35)
plt.show()

The animation shows the same comparison at every checkpoint from \(N = 10^4\) to \(N = 10^7\), the checkpoints about five per cent apart. As \(N\) grows, the primes thin out and the mean falls, from about \(5.5\) at the start to about \(3\) at the end.

Animation of the proportion of starting points n from 1 to N for which the interval of length 45 after n contains m primes, as N grows from ten thousand to ten million, with the predictions F (green squares), F0 (blue triangles) and the averaged Binomial (teal crosses) marked at each m.

Animated cumulative distribution of primes in intervals of length 45 starting at 1 through N, as N grows from ten thousand to ten million.

From the shell, pii cumulative-run, pii cumulative-frames, pii cumulative-plot and pii cumulative-animate carry out the same experiment for any \(H\) and \(N\), with the checkpoints running from \(N = 1\) (see docs/cli.md).