← Range ArcadeWORLD Nº 054 · PRIMES WITH A PROOF
▲ rollball towerWEIGH · PROVE · CLIMB · CARRY THE CERTIFICATE HOME

TWELVE RUNGS. ONE SEED PRIME. NO PROBABLE-PRIME TEST ANYWHERE.

Build primes.
Don't hunt them.

Start from M31 = 2³¹−1. Each rung offers five candidates N = 2kq+1 off the prime q below.
Weigh them on the wheel for a coin, prove one with a witness for five, and climb.

THE TOWERRUNG 1 / 12
150 COINS
▲

A tower
of proven primes.

Five candidates wait on every rung and at least one is prime. Weighing finds small factors cheaply; proving spends more but settles it.
Coins run out; digits do not. Leap while the numbers are small to double your height.

31 BITS · 10 DIGITS1–5 WEIGH · SHIFT 1–5 PROVE · L LEAPROLL IT UP

THE RACK · FIVE CANDIDATES, AT LEAST ONE PRIME

A rung is proved when q | N−1, q > √N, a^(N−1) ≡ 1 and gcd(a^((N−1)/q) − 1, N) = 1: Pocklington, 1914, with Euclid's +1 doing the work.

A DIFFERENT TOWER

Words choose every candidate on every rung; the same words build the same tower for anyone.

HOW THE PROOF WORKS

Euclid's +1, Pocklington's witness.

Take a prime q you already trust and any multiplier k. Then N = 2kq + 1 cannot share a factor with q. If q > √N and some a satisfies a^(N−1) ≡ 1 (mod N) and gcd(a^((N−1)/q) − 1, N) = 1, then N is prime. Not probably: outright. The tower keeps k small enough that q stays above √N, so each proved rung is the q for the next.

Weigh divides N by every prime up to 2000; a factor found is a coin well spent, and about five in six composites are caught. Prove runs the witness test with a = 2, 3, 5… A failed Fermat test means composite for certain. Leap offers multipliers almost as big as q, doubling the bit count in one rung; it is available while q has at most 512 bits.

Coins are the only limit. Three stars is reaching the twelfth rung with at least 200 digits. The certificate lists every rung; replay it in Python with pt.pocklington.verify_certificate_json or pt.nt.verify_certificate, or here with Verify.

THE CLIMB ENDS

▲

A prime with
a paper trail.

A TOWER FOR A FRIEND

Climb this tower with me.