The Collision Periodic Table

No one will ever write out the fractions of a prime with a thousand digits. One question about them can be answered anyway, exactly, without doing any division. Ask how many of those fractions begin with a doubled digit, the way $0.33\ldots$ and $0.77\ldots$ do. The answer is a tenth of the prime, rounded down, plus a small correction somewhere between $-9$ and $+8$, and the correction depends on nothing but the prime’s last two digits.

The corrections fill a table of forty cells, one for each ending a prime past a hundred can have. The Collision Fluctuation Sum needed only the table’s average and turned it into a slow drift across all the primes. The Centered Collision Sum went a step further and subtracted a separate average for each last digit. Neither one printed the table, and neither said why its numbers balance so neatly. They average exactly $-1/2$, and exactly twenty of the forty are negative. The largest and smallest, $+8$ at the ending $09$ and $-9$ at the ending $91$, both trace back to the eight fractions of nine.

At $109$ the count can still be done by hand. Its fractions run from $1/109=0.00917\ldots$ up to $108/109=0.99082\ldots$, and a fraction counts when its first two decimal places agree.

 1/109 = 0.00917…    match
 2/109 = 0.01834…    no match
12/109 = 0.11009…    match
13/109 = 0.11926…    match

Eighteen of the $108$ qualify. Sorted by their first digit, the fractions fall into ten bins of ten or eleven apiece, and the smaller size, ten, serves as the yardstick. So $109$ comes out eight above it.

Move nine hundred further along to $1009$. There are now $1008$ fractions, the bins hold a hundred or a hundred and one, and $108$ of the fractions begin with a doubled digit. That is eight above the yardstick again.

The two lists barely resemble each other. Every fraction sits somewhere new, and every row of the picture holds a different number of dots. The two denominators share the ending $09$, and the correction cares about nothing else.

Forty endings

Write $C_b(N)$ for the number of doubled beginnings in base $b$ at denominator $N$. Subtracting the smaller bin size leaves the correction, or collision deviation,

$$S_b(N)=C_b(N)-\left\lfloor\frac{N-1}{b}\right\rfloor.$$

The denominator must share no factor with the base, which in decimal means it ends in $1$, $3$, $7$ or $9$. With ten possible tens digits in front, there are forty endings, and each one carries a single fixed value of $S_{10}$.

To read a prime’s entry, find its tens digit down the side and its last digit across the top. For $109$ that is the $+8$ in the top right corner. The $-9$ in the bottom left belongs to $191$, and to $991$, and to every number ending in $91$ however many digits come before.

The primes are not essential. $50{,}009$ is $43\times1163$, and of its $50{,}008$ fractions exactly $5{,}008$ begin with a doubled digit, eight above a bin size of $5{,}000$, just as the cell at $09$ says. The table belongs to long division itself. Primes are the denominators we happen to care about most, and each one picks out a cell by its ending.

When ten is a primitive root of the denominator, as it is for $109$, the count also has an older name. Multiplying by ten then walks through the entire repeating block of $1/N$, so the count is the number of places where a digit of that block is followed by itself. The $108$-digit block of $1/109$ has eighteen such places. Agreement between a sequence and its own shift is a periodic Hamming correlation, studied in general by Lempel and Greenberger, and Kak and Chatterjee looked at it for the reciprocals of primes. The table needs neither the primitive root nor the prime.

All forty entries as numbers

The tens digit runs down the side and the units digit across the top. These are the corrections, not the counts themselves.

First digit	1	3	7	9
0	0	+2	0	+8
1	−1	−1	+1	−1
2	0	−2	+6	0
3	−1	−1	−3	−1
4	−4	0	−2	0
5	−1	+1	−1	+3
6	0	+2	0	0
7	−1	−7	+1	−1
8	0	−2	0	0
9	−9	−1	−3	−1

Eight entries are positive, twelve are zero and twenty are negative. The cell at $01$ holds zero, which is what the floor formula gives there and also what $101$ gives, with ten doubled beginnings against a bin size of ten.

A hundred more fractions

The repetition is easiest to see on a line. Lay the fractions out along the interval from zero to one and cut it into a hundred equal pieces. The first piece holds everything beginning $0.00$, the next everything beginning $0.01$, and so on up to $0.99$. A fraction begins with a doubled digit exactly when it lands in one of ten pieces

$$00,\quad11,\quad22,\quad\ldots,\quad99.$$

Raise the denominator by a hundred and each of the hundred pieces gains exactly one fraction, the ninety that don’t count along with the ten that do. The ten matching pieces gain one each, so the count climbs by ten. The bin size is a tenth of the denominator and climbs by ten as well, which leaves the difference where it was. That is the sense in which the table is periodic. The correction at $N$ comes back at $N+100$, at $N+200$, and at every denominator ending in those two digits.

The dots themselves don’t stay put. Every fraction moves when the denominator changes, and only the number in each piece goes up by one. The floor function makes this exact. Piece $j$ holds

$$\left\lfloor\frac{(j+1)N}{100}\right\rfloor -\left\lfloor\frac{jN}{100}\right\rfloor$$

fractions, less one in the last piece, where the formula would otherwise count the endpoint $1$. Replacing $N$ by $N+100$ adds $j+1$ to the first floor and $j$ to the second, so the piece gains exactly one. Since $N$ shares no factor with $100$, no fraction ever lands on a cut between two pieces, and nothing needs rounding one way or the other.

Every base works the same way. There are $b^2$ pieces, $b$ of them matching, and adding $b^2$ to the denominator adds $b$ to the count and $b$ to the bin size. A single finite function $T_b$ therefore holds every correction in that base,

$$S_b(N)=T_b(N\bmod b^2).$$

In decimal it has forty entries, and the denominator can be as long as it likes.

Seventeen fills what eighty-three leaves empty

Read the table in pairs and a second pattern shows up. Two endings that add to a hundred always have entries that add to $-1$.

$$\begin{aligned} T_{10}(09)+T_{10}(91)&=8-9=-1,\\ T_{10}(27)+T_{10}(73)&=6-7=-1,\\ T_{10}(41)+T_{10}(59)&=-4+3=-1. \end{aligned}$$

The pair $17$ and $83$ shows where the missing one comes from. Both denominators are under a hundred, so their fractions sit more than a hundredth apart and no piece can hold two of them. The end pieces $00$ and $99$ stay empty at both, because the smallest fraction is above $0.01$ and the largest is below $0.99$. That leaves the eight interior pieces from $11$ to $88$, and each of them gets a fraction from exactly one of the two denominators.

Seventeen supplies two matches and eighty-three supplies six, for eight in all. Their bin sizes are one and eight, which make nine. The two corrections, $+1$ and $-2$, have no choice but to add to $8-9=-1$.

Every pair in every base behaves the same way. Each interior matching piece is filled by exactly one partner, the end pieces stay empty, and the two bin sizes add to one more than the two counts do.

The endpoint arithmetic in any base

Put $q=b^2$ and choose an address $a$ coprime to $b$, with $1\leq a<q$. For a piece numbered $j$, write its floor increment as

$$D_j(a)=\left\lfloor\frac{(j+1)a}{q}\right\rfloor -\left\lfloor\frac{ja}{q}\right\rfloor.$$

For every interior boundary $1\leq j<q$, coprimality gives

$$\left\lfloor\frac{j(q-a)}q\right\rfloor =j-1-\left\lfloor\frac{ja}q\right\rfloor.$$

Subtracting successive instances shows that the two increments add to one on every interior piece, where $1\leq j\leq q-2$, and to zero and two on the first and last pieces

$$\begin{aligned} D_0(a)+D_0(q-a)&=0,\\ D_j(a)+D_j(q-a)&=1,\\ D_{q-1}(a)+D_{q-1}(q-a)&=2. \end{aligned}$$

The matching pieces have indices $d(b+1)$ for $d=0,\ldots,b-1$, which takes in both end pieces and $b-2$ interior ones. Each last-piece increment counts the excluded endpoint once, and removing it from each denominator leaves

$$\begin{aligned} &C_b(a)+C_b(q-a)\\ &\quad=0+(b-2)+2-2\\ &\quad=b-2. \end{aligned}$$

The two bin sizes add to $b-1$. Writing $a=bh+s$ with $1\leq s<b$, they are $h$ and $b-h-1$, and subtracting gives

$$\begin{aligned} &T_b(a)+T_b(b^2-a)\\ &\quad=(b-2)-(b-1)\\ &\quad=-1. \end{aligned}$$

The table can also be computed without choosing any larger denominator at all

$$T_b(a)=-1-\left\lfloor\frac ab\right\rfloor +\sum_{d=0}^{b-1}D_{d(b+1)}(a).$$

At address one the same formula uses the empty count $C_b(1)=0$. Each of these steps is proved for every base in The Collision Periodic Table, along with the two extremes.

The table balances as a result. Its forty entries form twenty pairs, every pair adds to $-1$, and so the average is exactly $-1/2$. The pairing settles the signs too. Two numbers that are zero or more cannot add to $-1$, while two negative integers add to $-2$ at most. So every pair holds one negative entry and one that isn’t. Exactly twenty of the forty are negative, and in any base exactly half the cells are.

These are statements about cells, not about primes. How often the primes land in each cell is a separate question, and a harder one.

Six cells in base three

In base three the whole table has six cells. The addresses below are written in base three, while the entries are ordinary signed integers.

First digit	Last digit 1	Last digit 2
0	0	+1
1	0	−1
2	−2	−1

Turn the rectangle halfway around and each cell lands on its partner. The pairs are $0$ and $-1$, then $+1$ and $-2$, then $0$ and $-1$, and each one adds to $-1$.

Base twelve has forty-eight cells. Twenty-four are negative, as the pairing requires, and the entries run from $+10$ down to $-11$. The pictures below carry the tables up through larger bases, with every cell computed from the floor formula. In the large ones the entries line up in fine diagonal bands, and even neighboring bases such as $360$ and $361$ look nothing alike.

From six cells to 123,462

Rows give the first digit of the address and columns the allowed final digits in increasing order, leaving out any digit that shares a factor with the base. So that different bases can share one color scale, the color shows $(T_b+1/2)/b$, spaced logarithmically on both sides of zero. Centering on $-1/2$ is what makes gold and teal trade places under a half-turn, and no family average has been subtracted.

Base $360$ has $96$ allowed final digits and $34{,}560$ cells, while base $361=19^2$ has $342$ allowed final digits and $123{,}462$ cells. Neither plate leaves out a cell.

The forty-eight base-twelve entries

Labels give digit values in ordinary decimal notation, so the last row is the digit eleven. Only the final digits $1$, $5$, $7$ and $11$ share no factor with twelve.

First digit	1	5	7	11
0	0	0	0	+10
1	−1	−1	−1	−1
2	−2	0	+2	0
3	−3	−1	+1	+1
4	0	0	+6	+2
5	−5	+1	−5	−1
6	0	+4	−2	+4
7	−3	−7	−1	−1
8	−2	−2	0	+2
9	−1	−3	−1	+1
10	0	0	0	0
11	−11	−1	−1	−1

The pairing fixes the center and the sign count in every base. The two ends of the range take one more observation. An address below $b^2$ has its fractions more than $1/b^2$ apart, so each matching piece holds at most one of them. The two end pieces are always empty. That caps the count at $b-2$. The bin size can’t be negative, so the same cap holds for the entry.

Nine and ninety-one

In decimal the cap is eight, and nine reaches it.

1/9 = 0.111…       5/9 = 0.555…
2/9 = 0.222…       6/9 = 0.666…
3/9 = 0.333…       7/9 = 0.777…
4/9 = 0.444…       8/9 = 0.888…

All eight fractions begin with a doubled digit, and the bin size, a tenth of eight rounded down, is zero. The entry at $09$ is $+8$, as large as the table allows. In any base $b\geq3$ the denominator $b-1$ does the same, since each of its $b-2$ fractions repeats a single digit forever.

Ninety-one is nine’s partner, and reflection hands it the other extreme. Its ninety fractions sit just over a hundredth apart, yet not one of them lands in a doubled-digit piece. Each interior piece is filled by exactly one member of the pair, and the ninths have already filled all eight. With a count of zero against a bin size of nine, $91$ sits at $-9$, the table’s lowest entry. In base $b$ the same argument puts $-(b-1)$ at the address $b^2-b+1$. Base two is too small for any of this and has just the entries $0$ and $-1$.

A prime with a thousand digits that ends in $91$ therefore has as many doubled beginnings as a tenth of itself, rounded down, less nine. Eight of the nine are the interior pieces the ninths fill, and the last is the one every reflected pair comes up short.

The forty entries, the twenty pairs and the sign counts, drawn