|
|
|
|
|
|
|---|---|---|---|---|---|
 |
 |
 |
ζ | XN + YN = ZN |
|---|---|---|---|---|
 |
 |
 |
 |
XXXX |
|---|---|---|---|---|
 |
 |
 |
|---|---|---|
Number theory analyzes integer solutions to equations. Computers are often used, opening opportunities for amateurs and crowd computing. Mathematics accounts for 1/4 of crowd computing.
Computers often seek counterexamples, and the "reach" is the extent to which counterexamples are ruled out. For example, Collatz conjecture counterexamples are ruled out up to 1020. Computers continuously expand reach. Another example is that all maximal prime gaps are known up to 1020.
There are archives with number theory data and programs, which is an opportunity to make fancy charts.
Polymath8 was a large team project, coordinated by Terence Tao, that sharpened Zhang’s breakthrough on prime gaps.
 |
|---|
The maximal gap function Gap(X) is the size of the biggest prime gap up to prime X.
A "record" gap at X is such that there are no known gaps of larger magnitude at smaller X. It doesn't necessarily mean that they don't exist. In the chart, all record gaps are shown.
Some primality tests are guaranteed to correctly distinguish between a prime and composite. Some tests are probabilistic. They have good accuracy but occassionally a composite passes the test. Such composites are called "pseudoprimes".
In the chart, "guaranteed gaps" are record gaps with guaranteed primes. "Probable gaps" are record gaps with probable primes.
The average gap size at X scales as ln(X). The scaling for the maximal gap is poorly constrained, as is the gap distribution.
If gap size is Gaussian distributed as e-(Gap/lnX)2, the maximal gap scales as Gap(X) ~ ln3/2X.
If gaps are exponentially distributed as e-Gap/lnX, the maximal gap scales as Gap(X) ~ ln2X. This is the Cramer conjecture.
Numerical evidence supports an exponential distribution but there is a computational limit for how far the tail can be explored. The limit hinges on sieve size and memory.
 |
|---|
The chart shows the prime gap distribution for X = 218, 224, and 230.
Model the gap distribution as
D(Gap) = A e-C (Gap/lnX)α
ln ln [D(Gap)]-1 = ln C + α ln(Gap/lnX)
The data is fitted by α = 1 and C = 1.28.
A Diophantine equation has integer coefficients and integer exponents, and integer solutions are studied. The number of terms is finite.
A1 X1N1 + A2 X2N2 + A3 X3N3 + ... = 0
A transcendental Diophantine equation is any equation for which integer solutions are studied.
[T] denotes a theorem and [C] a conjecture. An arrow means logical implication. A dash means a relationship rather than an implication.
A capitalized variable denotes an integer. Lower-case variables need not be integers.
Equation Theorems, conjectures, and corollaries A * B = C 2½ is irrational: Hippasus ~500 BCE Prime numbers Bateman-Horn [C] -> Hardy-Littlewood #1 [C] -> Schinzel hypothesis H [C] -> Dickson [C] -> Dirichlet [T] -> Twin prime [C] -> Sophie Germain [C] Generalized Riemann Hypothesis [C] -> Riemann hypothesis [C] Generalized Elliott-Halberstam [C] -> Elliott-Halberstam [C] Brocard [C] -- Legendre [C] Oppermann [C] -> Legendre [C] Oppermann [C] -> Brocard [C] Oppermann [C] -- Andrica [C] Cramer [C] -> Brocard [C] Gilbreath [C] FGKMT large-gap lower bound [T] Firoozbakht [C] -> Cramer upper bound [C] A + B = C Strong Goldbach [C] -> Weak Goldbach [T, Helfgott] Baker [C] -> ABC [C] -> Faltings [T] -> Fermat [T] -> Fermat-Catalan [C] -> Pillai [C] -> Beal [C] <-> Modified Szpiro [C] X1 + X2 + ... + XN = 0 Strong n [C] -> n [C] -> ABC [C] AX + BY = C Hilbert 10th problem [T, undecidable: DPRM] A0 + A1X +...+ ANXN = 0 Algebraic numbers Liouville proved the existence of transcendental numbers in 1844 and constructed one in Lambert [C 1768] e is transcendental. Proved by Hermite in 1873 Lambert [C 1768] π is transcendental. Proved by Lindemann in 1882 Cantor [T 1874] Transcendentals and reals have the same cardinality XN + YN = ZN Fermat [T], proven by Wiles & Taylor in 1995 X1N + X2N + ... + XTN = 0 Lander-Parkin-Selfridge [C] -> Fermat [T] Sum of like powers Euler sum-of-powers [false] Geometric Langlands [C] Langlands reciprocity [C] M = X1N + X2N + ... + XGN Waring [C 1770] AX + BY = CZ ABC [C] -> Fermat-Catalan [C] Exponential equations -> Asymptotic Fermat [conditional consequence] -> Pillai [C] Beal [C] -- related generalized Fermat equation XY - YX = 1 Catalan [T], proved by Mihailescu in 2002 ABC [C] -> Weak Hall [C] Y2 = X3 + BX + C Modularity [T] -> Fermat [T] Elliptic curves Langlands program [C] Birch & Swinnerton-Dyer [C] A XM - B YN = C Pillai [C] -- Hall [C] 1N + 2N + ... + (M-1)N = MN Erdos-Moser [C] 2N + 1 = P + 2Q Lemoine [C] -- A more restrictive three-prime representation 2N + 1 = P + M(M+1) Sun [C] N! + 1 = M2 Brocard factorial problem [C] M/N = X-1 + Y-1 + Z-1 Generalized Erdos-Straus [C] -> Erdos-Straus (M=4) [C] X2 + Y2 <= r2 General Gauss circle problem [C] -> Gauss circle problem [C] Plane set, rational dist Bombieri-Lang [C] -> Erdos-Ulam false ABC [C] -> Erdos-Ulam false Giuga [C 1950]
Let X have B bits. The cost of integer multiplication is M(B) = B2. For numbers with more than 211 digits, methods with better scaling are possible. The reach scaling is multiplied by M(B) to produce the overall scaling.
Digits X Reach scaling
Reach, prime number sieve 20 e19 X ln ln(X) Memory is X½
Reach, prime gap, maximal 20 e19
Reach, prime gap, proven 7 1113106
Reach, prime gap, probable 8 16045848
Reach, twin prime gap, record 17 e16
Reach, Baille-PSW pseudoprimes 19 1.9e18
Reach, Riemann exhaustive zeros 12 4e11 X ln(X) / (2π)
Reach, Collatz conjecture 20 e20 X
Reach, Goldbach conjecture 19 4e18 X ln ln X
Reach, Euler cuboid 13 e12 X3
Reach, Erdos-Straus conjecture 18 e17 X
Reach, ABC conjecture 20 e19
Reach, Firoozbakht conjecture 19 4e18
Reach, Agrawal conjecture 18 e17
Reach, Andrica conjecture 20 2e19
Reach, Hall conjecture 29 6e28
Reach, Lamoine conjecture 11 1e10
Reach, Gilbreath conjecture 20 1.5e15
Reach, Brocard problem 16 1e16 Known solutions are (4,5), (5,11), (7,71)
Reach, archive, Charmichael 22 e21
Reach, archive, Base-2 Fermat 20 2e19 Pseudoprimes
Reach, Li coefficient
Reach, Catalan-Beal conj.
Reach, Aliquot sequence
Reach, Giuga conjectures
Reach, Giuga complete list 31 5e30
Reach, primary pseudoperfect 19 6e18 Complete list
Reach, Ekl(6,1,5) 5 730000 X5/2
Reach, Ekl(6,1,6) X5/2
Reach, Ekl(7,1,5) X3
Reach, Ekl(8,1,7) X7/2
Reach, Ekl(9,1,8)
Reach, Ekl(9,1,9)
Reach, Ekl(7,3,4)
Reach, Ekl(9,4,5)
Reach, Ekl(10,5,5)
Biggest Mersenne prime 41000000 Big
Biggest probable prime 8200000 Big ln ln(X) Miller-Rabin PRP test
Biggest twin prime 388342 Big
Biggest triplet prime 20008 Big
Biggest Riemann zero 35 8e34 X½
Biggest Catalan number 17 3.8e15
Biggest Giuga number 97 4e96
Biggest primary pseudoperfect 38 4e37
Biggest Riesel number 7 3580901
Skewes point, proven 317 1.49e316
Skewes point, min 175 1.5e174
Skewes point, prime pair 7 1369391 Wolf 2011
Skewes point, prime triple 6 337867 Toth 2019
Skewes point, prime 4-tuple 7 1172531 Toth 2019
Skewes point, prime 5-tuple 8 21432401 Toth 2019
Skewes point, prime 6-tuple 12 2.5e11 Toth 2019 251331775687
Skewes point, prime 7-tuple 13 7.6e12 Pfoertner 2020 7572964186421
Skewes point, prime 8-tuple 16 1.2e15 Pfoertner & Luhn 2020 1203255673037261
Skewes point, cousin prime 7 5206837
Skewes point, sexy prime Unknown
Waring N=2 4 Lagrange 1770
Waring N=3 9 Weiferich 1912
Waring N=4 19 Balasubramanian & Deshouillers & Dress 1986
Waring N=5 37 Chen, Conway 1964
Waring N=6 73 Pillai 1940
Waring N=7 143 Dickson, Pillai 1936
Giuga counterex. low bound 36067
Mertens lower bound 17 e16
Mertens upper bound 8.5e18 Big
Polya conj min counterexample 9 906150257 Tanaka 1980
Erdos-Moser conj lower bound e9 Big
Archimedes sand reckoner # 63 Big
Googol 100 Big
Googolplex 10100 Big
Integer, 4 byte 10 2e9
Integer, 8 byte 19 9e18
Integer, 16 byte 39 2e38
Integer, 32 byte 77 6e76
Float, 4 byte 39 3e38
Float, 8 byte 309 2e308
Float, 16 byte 4933 1e4932
The First Hardy-Littlewood conjecture (1923) is that the density of prime M-tuples at X is 1/lnM(X).
The prime number theorem is the case M=1 and was proven in 1896 by Hadamard & Poussin independently.
In 1915, Brun proved that the number of twin primes less than X is less than (2/3) X/lnM(X).
The Bateman-Horn conjecture (1962) generalizes the First Hardy-Littlewood conjecture.
Gap(X)
Upper bound, proven, 1852 X Assumes a prime between P and 2P. Bertrand postulate
Upper bound, proven, 1930 X32999/33000 Hoheisel
Upper bound, proven X249/250 Heilbronn
Upper bound, proven, 1936 X3/4 Cudakov
Upper bound, proven, 1937 X5/8 Ingram Implies a prime between successive cubes
Upper bound, proven, 1972 X7/12 Huxley
Upper bound, proven, 2001 X.525 Baker, Harman, & Pintz
Upper bound, conjecture, 1912 X1/2 Legendre conj. Assumes a prime between successive squares
Upper bound, conjecture, 1969 X1/2/ln(X) Grimm conjecture
Upper bound, conjecture, 1936 ln(X) ln(X) Cramer
Upper bound, conjecture, 1982 ln(x) ln(x) - ln(x) - 1 Firoozbakht Assumes PN1/N strictly decreasing, where PN is the Nth prime
Riemann hypothesis corollary 1936 X1/2 ln(X) Cramer
Lower bound, proven, 1931 ln(X) Westzynthius
Lower bound, proven, 1938 ln(X) lnln(X) lnlnlnln(X) / [lnlnln(X)]2 Rankin
Lower bound, proven, 2018 ln(X) lnln(X) lnlnlnln(X) / lnlnln(X) Ford-Green-Konyagin-Maynard-Tao
To find zeros of the Riemann Zeta function, use the Hardy Z function, which is real-valued function along the critical line.
Search for sign changes. Use root-finding (Newton, Brent, secant, etc.). Count how many zeros were found. Independently count how many zeros should exist using the Riemann-von Mangoldt formula. If the counts agree, every zero up to that height lies on the critical line. This is the method used in essentially every large-scale verification.
The Odlyzko-Schonhage formula evaluates all zeros in an interval collectively, at a cost of ln(X) per zero.
The density of zeros is ln(X)
For evaluating the Hardy function at a single point, the Riemann-Siegel formula scales as X½.
Calculations use interval arithmetic, ball arithmetic, and arbitrary precision libraries. Each computed value is an interval guaranteed to contain the true value. Packages like Arb (now integrated into FLINT) make this practical.
The Riemann hypothesis is equivalent to all Li coefficients being positive, although this test is more expensive than evaluating zeros.
The density of Riemann zeros is ln[γ/(2π)] / (2π)
The RMS magnitude of the Hardy Z function is ln½ γ
The scaling for moments of order m is conjectured to be lnm2/4 γ.
Non-trivial zeros have the form
W = β + i γ
The scaling for calculating all zeros up to height γ=H is
X ln X
It uses FFT methods. The current reach is 4⋅1011.
The scaling for calculating an isolated zero is X½ and current reach is 8⋅1034.
Normal zeros have β=½ and deviant zeros have β≠½.
The prime number theorem forces 0 < β < 1.
If devient Riemann zeros exist, let the smallest one have γ=γ0.
Let X0 be the smallest value of X for which the deviant zero causes consequences for prime number distributions.
If the first deviant zero is accompanied by a storm of nearby deviant zeros, let M be the number of deviant zeros.
X0 ~ (γ/M)1/(β-½)
Define a weighted prime counting function:
C = ∑p<X ln p
Asymptotically, C ~ X
Riemann zeros contribute fluctuations with value XW/W.
Define an Ekl polynomial Ekl(N,U,V).
X1N + X2N + ... + XUN = Y1N + Y2N + ... + YVN Q = U + V - N
The Lander-Parkin-Selfridge conjecture is that all integer solutions have Q>=0. The Fermat theorem is the case Ekl(N,1,2).
The conjecture is true for N<=4.
Denote a solution with brarckets. For example, a solution for Ekl(2,1,2) is:
52 = 32 + 42 <--> [5] = [3 4]
The value of Q=0 for the LPS conjecture is supported by probabilistic arguments. By probability, if there are no congruence constraints, then the number of solutions up to height H is
S(H) ~ HQ if Q>1
S(H) ~ ln(H) if Q=0
S(H) is expected to be finite for Q<0
Euler's sum of powers conjecture (1778) is that Q>=1 for integer solutions of Ekl(N,1,V). It was proven false with counterexamples for N=4 and N=5. No counterexamples exist for N>5. The smallest counterexample for N=4 and N=5 is
4224814 = 958004 + 2175194 + 4145604 1445 = 275 + 845 + 1105 + 1335
Solutions for Ekl(N,1,V) with Q=1 are known only for N = {2, 3, 4, 5, 7, 8}
The tables give the minimum value of Q known as a function of N, U, and V, along with the minimal numerical example. Solutions for Ekl(N,1,2) are ruled out by the Fermat theorem.
N U V Q 2 1 2 1 [5] = [3 4] Pythagorean triples Antiquity 3 1 3 1 [6] = [3 4 5] Antiquity 4 1 3 0 [422481]= [95800 217519 414560] Euler counterexample 1998 Elkies 5 1 4 0 [144] = [27 84 110 133] Euler counterexample 1967 Lander et al. 6 1 7 2 [1141] = [76 234 402 474 702 894 1077] 1967 Lander et al. 7 1 7 1 [568] = [525 439 430 413 266 258 127] 1999 Dodrill 8 1 8 1 [1409] = [1324 1190 1088 748 524 478 223 90] Chase; Meyrignac Only solution known 9 1 10 2 [917] = [851 822 668 625 574 542 475 179 99 42] 10 1 13 4 [228] = [210 204 187 179 128 122 85 73 59 57 49 13 6] Chase 2 2 2 2 [2 11] = [5 10] Antiquity 3 2 2 1 [1 12] = [9 10] Antiquity 4 2 2 0 [59 158] = [133 134] 1772 Euler 5 2 3 0 [141325 2205] = [140685 62375 50275] 1997 Scher & Seidl 6 2 5 1 [770 1117] = [84 212 602 861 1092] 1999 Brisse 7 2 6 1 [125 24] = [121 94 83 61 57 27] Meyrignac 8 2 7 1 [1303 1127]= [1334 976 648 623 516 401 272] Chase; Meyrignac Only solution known 9 2 9 2 [137 69] = [121 116 116 115 89 52 28 26 14 9] 2002 Wroblewski 10 2 12 4 [112 99] = [109 103 89 79 72 59 59 52 20 15 5 5] 2000 Pliousnine 2000, 2000 Kuosa 5 3 3 1 [3 54 62] = [24 28 67] 1967 Lander et al. 6 3 3 0 [3 19 22] = [10 15 23] 1934 Subba Rao 7 3 5 1 [96 41 17] = [87 77 77 68 56] 8 3 5 0 [966 539 81]=[954 725 481 310 158] 2003 Chase, Meyrignac, Resta & Meyrignac 9 3 9 3 [38 38 3] = [41 23 20 20 18 13 13 12 9] 1998 Ekl 10 3 11 4 Solutions known 2002 Wroblewski 6 4 4 2 [2 2 9 9] = [3 5 6 10] 1934 Rao 7 4 4 1 [149 123 14 10] = [146 129 90 15] 1996 Ekl 8 4 4 0 [3113 2012 1953 861] = [2823 2767 2557 1128] 2006 Kuosa 9 4 6 1 [90 64 35 35] = [86 80 62 43 27 16] 10 4 9 3 Solutions known 2002 Wroblewski 9 5 5 1 [192 101 91 30 26] = [180 175 116 17 12] 1997 Ekl 10 5 16 11 Solutions known 10 6 6 2 [95 71 32 28 25 16] = [92 85 34 34 23 5] 2002 Kuosa
In the table, the first column is N and the top row is U. The interior is the minimum known Q for integer solutions of Ekl(N,U,V) with U <= V.
U -> 1 2 3 4 5 6
N
2 1 2
3 1 1
4 0 0
5 0 0 1
6 2 1 0 2
7 1 1 1 1
8 1 1 0 0
9 2 2 3 1 1
10 4 4 4 3 7 2
Proofs for specific exponents:
Exponent
3 1770 Euler
4 1670 Fermat
5 1825 Legendre; Dirichlet
6 1802 Kausler
7 1869 Lame
10 1913 Kapferer
14 1832 Dirichlet
<270 1823 Germain
<2522 1954 Vandiver Computer proof
<125000 1978 Wagstaff Computer proof
<4000000 1993 Computer proof
Even 1977 Terjanian
Regular prime Kummer Conjecture: 61% of primes are regular
All 1995 Wiles
1955 Modularity conjecture. Taniyama & Shimura
1983 Faltings theorem
1984 Frey theorem
1986 Ribet theorem
2001 Modularity theorem
Every positive even number occurs infinitely often as the gap between consecutive primes.
Zhang proved in 2013 that some prime gap no larger than 70,000,000 occurs infinitely often. Polymath8 and Maynard–Tao reduced the bound to 246. Polignac conjectures this separately for every positive even gap.
Generalized Fermat equation:
AX + BY = CZ
Beal conjecture: All integer solutions with {X, Y, Z} > 2, {A, B, C} have a common prime factor.
The Fermat-Catalan conjecture is that there are only finitely many solutions with A, B, and C being positive integers with no common prime factor and X, Y, and Z being positive integers satisfying X-1 + Y-1 + Z-1 < 1
The Beal conjecture can be restated as "All Fermat-Catalan conjecture solutions use 2 as an exponent".
The ABC conjecture implies that there are at most finitely many counterexamples to the Beal conjecture.
The Catalan conjecture was posed in 1842: The only solution to AX - BY = 1 is 32 - 23 = 1. It was proved in 2002 by Mihailescu.
To search for solutions to Euler polynomials Elk(N,1,N) up to height H, the naive computational scaling is N HN / (N-1)!.
Meet-in-the-middle technique improves the scaling to N H(N-1)/2.
Modular sieving can reduce the search space and reduce the constant in front of the scaling.
The generalized Andrica conjecture is PN+1Z - PNZ < 1 if Z < .670873.... where PN+1 is the Nth prime.
The Andrica conjecture is for the case Z=1/2.
There are at least 1 primes between successive squares. This implies that there are at least 2 primes between successive prime squares.
There are at least 4 primes between successive prime squares. The Brocard conjecture implies the Legendre conjecture.
The conjecture is that zeros of the Riemann zeta function have a correlation function of
1 - [(sin(π X) / (π X)]2
The conjecture has big numerical support.
For N-bit integer multiplication:
Algorithm Scaling Crossover Crossover
digits bits
Standard N2 211 704 Ancient
Karatsuba Nlog23 ~ N1.585 2639 8768
Toom-3 Nlog35 ~ N1.465 81379 270336
FFT N ln(N) ln ln(N) 1010 2912 1971 Schonhage & Strassen
Galactic FFT N ln(N) Harvey & van der Hoeven Optimal scaling
"crossover" is where another algorithm becomes better.
The crossover from FFT to Galactic FFT is a lower bound.
Residues can be calculated faster than divides. Clock cycles:
Add Multiply Divide Residue
Integer 32-bit 3 3 12 ~3
Integer 64-bit 3 3 12 ~3
Float 32-bit 3 3 12
Float 64-bit 3 3 12
Operations can be pipelined to produce an output each clock.
The scaling for a prime sieve is X ln ln X
Algorithm Scaling Crossover
digits
Brute force X½
Pollard rho X¼
Quadratic sieve exp[X ln ln X]½ 100
GNFS exp[(64/9)1/3 ln1/3X (ln ln X)2/3]
Some tests are guaranteed to correctly distinguish between a prime and composite. Some tests are probabilistic. They have good accuracy, but occassionally a composite passes the test. Such composites are "pseudoprimes". B = log2 X.
Scaling
Brute force Guarantee X½
Fermat Probable B Defeated by Carmichael numbers
Miller-Rabin Probable K B Probability of 4-K
AKS Agrawal-Kayal-Saxena 2002 Guarantee B6
Agrawal-Kayal-Saxena + Agrawal 2005 Guarantee B3 Assumes that the Agrawal conjecture is true
Baillie-PSW Probable No known conterexample
Adleman-Pomerance-Rumely [ln X]ln ln ln X
ECPP
The test produces probable primes with controllable probability. The scaling is K ln(X), where K is the number of rounds. Each round constrains the probabililty of being composite by more than a factor of four. Producing a probable prime takes at least K=ln(X)/ln(4) rounds.
The Baillie-PSW primality test is a probabilistic or possibly deterministic primality testing algorithm that determines whether a number is composite or probable prime. "PSW" stands for Pomerance Selfridge, Wagstaff.
The Baillie-PSW test is a combination of a strong Fermat probable prime test to base 2 and a standard or strong Lucas probable prime test. The Fermat and Lucas test each have their own list of pseudoprimes, that is, composite numbers that pass the test. There is no known overlap between these lists, and there is even evidence that the numbers tend to be of different kind, in fact even with standard and not strong Lucas test there is no known overlap.
Computers show that there no Baille-PSW pseudoprimes below 1.9e18.
Searches for large prime gaps first identify a range of guaranteed composites and then test the endpoints for primality. Only two numbers need be tested for primality.
Such gaps are the product of biased searches and need correction to be related to the gap distribution.
"primesieve" is a prime-sieving program that is well-optimized and harnesses parallel threads. It uses cache wisely. On a 1 TFlops machine, it takes 40 seconds to sieve up to 1012. The sieve scaling is X ln ln(X).
A "segmented sieve" sieves an interval from X to X+XI, where XI << X, the scaling is XI X½ / ln(X).
There are 85 record gaps up to 1.01⋅1020, and the average factor in X between record gaps is 1.72. To find record gaps and probe the end of the gap distribution, you have to have XI = X, so a full sieve should be done.
The biggest number that primesieve can handle is Xmax = 264 - 1 = 1.84⋅1019.
Let X = 2N. The sieve size is 8 π(2N/2) bytes, where π is the prime counting function. For N=64, the sieve size is 1.63 GB, well within reach of computer memory.
Statistics for a set of primes:
Prime constellations: gaps, deserts, and clusters.
Residues
Pseudoprimes
Correlations
Extreme instances
For a segmented sieve, each sieve segment saves primes at the endpoints to link to adjacent segments.
A sieve in the range of X=1019 takes 1000 Operations per integer and 50000 operations per prime.
Identify a set of compact statistics that can be calculated with 50000 operations and do a run.
Identify all statistics of interest to mathematicians and do a run, which will be slower.
A typical sequence of memory sizes and clock latencies for a strong desktop are:
Clock cycles Size in MB Latency in microseconds
Register 0 .004
L1 4 .032 .001
L2 12 1 .003
L3 32 64 .008
RAM 400 64000 .1
RAM, Neocortex 1600 24000000000 .4 Neocortex HPE Superdome Flex. 32 Xeon Platinum 8280L processors; 896 cores
Solid state 40000 4000000000 10
SD card 200000 4000000000 50
Disk 48000000 20000000000 12000
We assume a clock speed of 4 GHertz.
A strategic set of bases maximizes overall information per memory. Compactness matters for cache efficiency. There's a balance between residue memory and speed.
The distribution of residues for a base gives you the distribution of residues for factors of that base. It's strategic to use big bases that are highly composite. Combined bases have information that the component bases don't.
The set of bases should include all primes < 28. It should also include all prime powers PQ with P<256 and Q the maximal integer such that PQ < 216.
Strategic product bases include:
*) 224⋅3⋅5⋅7⋅11⋅13⋅17⋅19⋅23
*) 23 32 52 72 112 132
*) 26 34 54 74
A base has the form: W = 2N2 3N3 5N5 7N7 ... 251N251
The importance of a prime P scales as 1/P.
For a base PQ,
*) Q ≥ 1 is essential.
*) Q ≥ 2 is valuable for testing if admissible classes split uniformly among their prime lifts.
*) Q ≥ 3 is exploratory.
*) Q ≥ 4 is used for specialized p-adic research and pseudoprime work.
All odd primes have residue 0 modulo 2, so this information doesn't need to be tallied. For 2Q, only 2Q-1 residues need be tallied. If a base W includes a factor 2Q with Q ≥ 2, only W/2 residues need be tallied. "4" can be considered an honorary prime.
A "balanced" base has decreasing Q as P increases. PQ has similar magnitude for each factor. For example, 27 34 53 72 112 13 15. We include 2 primes with Q=1 to balance the Q=2 factor to the left.
Residue distributions be stored in an array with 1 byte per element. Upon overflow, tally to a companion array with 64-bit integers and reset the counter. The overflow test is negligible compared to memory latency.
L2 cache is typically 12 clocks and L3 cache is typically 32 clocks. If a base is small enough to fit in L2, it's worth it to multiply it by more bases so that the product base is in L3.
The residue distribution of a combined base has information that the component bases don&spos;t. Maximize the size of combined bases strategically such that the set fits in L3.
RAM is typically 250 clocks. It can be strategic to multiply bases that fit in L3 to form a combined base that lives in RAM.
L3 cache is typically 64 Mbytes. Assume a budget of 8 Mbytes for bases and identify a strategic set that fits in this limit.
Construct another set of strategic bases that fit in RAM. We assume a budget of 8 Gbyte.
Make the L3 bases and RAM bases synergistic.
A survey of mathematicians will likely yield a distribution of opinions for the choice of bases.
For 8 GB of total memory, a strategic set of bases in decreasing order of importance is:
446185740 = 22 3 5 7 11 13 17 19 23 Maximize the number of primes
138738600 = 23 32 52 72 112 13 Squares
203742000 = 24 33 53 73 11 Cubes
340200000 = 26 35 55 7
241864704 = 212 310
2270268000 = 25 34 53 72 11 13 Balance
83521 = 174 Prime powers
130321 = 194
279841 = 234
707281 = 294
29791 = 313
50653 = 373
68921 = 413
1849 = 432
2209 = 472
2809 = 532
...
63001 =2512
123002880 = 213 3 5 7 11 13 Extreme powers
131351220 = 4 38 5 7 11 13
187687500 = 4 3 56 7 11 13
144204060 = 4 3 5 75 11 13
79939860 = 4 3 5 7 114 13
131951820 = 4 3 5 7 11 134
295074780 = 4 3 5 7 11 13 173
368588220 = 4 3 5 7 11 13 17 192
29609580 = 4 3 5 7 11 13 17 29 Big primes
31651620 = 4 3 5 7 11 13 17 31
...
31771740 = 4 3 5 7 11 13 232 Big squares
50510460 = 4 3 5 7 11 13 292
...
190930740 = 4 3 5 7 112 13 172 Mixed squares
225645420 = 4 3 5 7 11 132 172
...
462000000 = 4 3 7 11 105 Base 10
With 24 Tbytes of memory:
14841476269620 = 4 3 5 7 11 13 17 19 23 29 31 37
521240920200 = 23 32 52 72 112 132 172
24652782000 = 24 33 53 73 113
816820200000 = 26 35 55 75
1312200000000 = 29 38 58
940369969152 = 216 315
10488638160000 = 27 35 54 73 112 13
A constellation is a set of primes with specified distances between them.
For a prime, define a set of bits representing primes that are larger and nearby. A constellation of radius R needs R/2 bits, which is an index in an R/2 dimensional array. Add another dimension for the distribution for the constellation.
Named constellations:
Pattern 2 Twin 4 Cousin 6 Sexy 2 6 Triplet 4 6 Triplet 2 6 8 Quadruplet 4 8 Cousin triplet 6 12 Sexy triplet 4 8 12 Cousin quadruplet 6 12 18 Sexy quadruplet N 2N Arithmetic progression length 3 N 2N 3N Arithmetic progression length 4
Dense constellations:
# of Width Pattern First instance primes 2 2 2 3 5 Twin prime 3 6 2 6 5 7 11 Triplet prime 3 6 4 6 7 11 13 Triplet prime 4 8 2 6 8 5 7 11 13 Quadruplet prime 5 12 2 6 8 12 5 7 11 13 17 5 12 4 6 10 12 7 11 13 17 19 6 16 4 6 10 12 16 7 11 13 17 19 23 7 20 2 6 8 12 18 20 11 13 17 19 23 29 31 7 20 2 8 12 14 18 20 5639 5641 5647 5651 5653 5657 5659 8 26 2 6 8 12 18 20 26 11 13 17 19 23 29 31 37 8 26 2 6 12 14 20 24 26 17 19 23 29 31 37 41 43 8 26 6 8 14 18 20 24 26 88793 88799 88801 88807 88811 88813 88817 88819 9 30 2 6 8 12 18 20 26 30 11 13 17 19 23 29 31 37 41 9 30 4 6 10 16 18 24 28 30 13 17 19 23 29 31 37 41 43 9 30 2 6 12 14 20 24 26 30 17 19 23 29 31 37 41 43 47 9 30 4 10 12 18 22 24 28 30 88789 88793 88799 88801 88807 88811 88813 88817 88819
The scaling for constellation width W as a function of order K is
W ~ K (ln K + 1)
It's accurate to better than 1 part in 128.
A dense constellation of order C in the range of X occurs with probability ln-C(X). When storing a constellation, store a large number of surrounding primes, nominally 28.
With a disk memory of 1 Tbyte for a set of constellations, with 210 bytes per constellation, 1 Gbyte of constellations can be stored.
For a scan up to X = 264, the full set of constellations can be stored if they occur with probability < 1010, which corresponds to C=6.
Let G1 and G2 be consecutive gaps. It could be any kind of gap. Tally a distribution D(G1,G2). This can be extended to any number of gaps.
The largest number that primesieve can handle is 264 ~ 1.819. The maximal prime gap for this number is 1550 and this sets the size of arrays for distributions. One can get away with a smaller array size by recording extreme events that are beyond the arrays and adding them to the correlation later. Computer memory can handle a 4-stage distribution of prime gaps.
Saving only even prime gaps means 775 array elements per gap. A 3-point distribution with 4-byte integers is 1.86⋅109 bytes.
The array can be compacted by storing overflow instances separately. The average prime gap size is 44 at X=264. If the array tallies gaps up to 512, this is 256 elements per dimension. A 4-point distribution is 4.3 Gbyte.
Define probability functions D and correlation functions C.
D12 = D1 D2 + C12 D123 = D1 D2 D3 + D1 C23 + D2 C13 + D3 C12 + C123
Let G1 be a prime gap, G2 be a double prime gap, etc. Gk spans k+1 primes.
Tally the distribution for k=1, 2, 3, 4, 6, 8, 12, 16, etc. This exposes clusters and deserts. It's more tidy than scan statistics.
This may be applied to any constellation.
If gaps are Poisson distributed with a density of λ, then Gk follows an Erlang distribution.
Dk(Gk) = λk Gkk-1 eλ Gk / (k-1)!
A program performs a sieve on a segment and produces a stream of primes.
Next, a program receives the stream and calculates. No memory access is needed. It produces a set of output numbers, many of which are indices for arrays.
Next, a program receives the output and changes arrays. In many cases, an array element is incremented by one.
Calculation and array changes are separated if possible so that memory latency is less than calculation.
Hardware can be optimized for number theory. There is hardware for cryptogaphy. Things that can be hard-wired.
*) High-precision integer operations
*) Residues
*) Prime wheels
*) Logic for handling residues
Low-precision integer operations are often present on tensor processors.
Standard matrix multiplicaiton is N3 and Strassen multiplication is N2.807. Strassen multiplication is practical.
The best current practical algorith scales as N2.77, but it's more complex than Strassen multiplication.
The best current bound is N2.37, but this algorithm is galactic and impractical (Alman, Duan, Williams, Xu, Xu, and Zhou).
The first block is mathematics projects and the second block is the largest projects outside mathematics. Mathematics accounts for around 1/4 of crowd computing.
TeraFlops
Collatz conjecture 18500
Mersenne primes 5300
General prime search 3000
Amicable pairs 1500
Sierpinski/Riesel Bases 600
NumberFields@Home 130
Elliptic curves yoyo@home 66
Factorization NFS@Home 51
Ramanujan machine 4.4 Find new formulae
ABC conjecture ?
Agrawal conjecture ?
Protein structure 44300 Rosetta@home
Protein structure 29800 Folding@home
Gravitational waves 4100 Einstein@Home
MilkyWay@home 2000 3D model of the Milky Way
 |
 |
 |
 |
|---|---|---|---|
 |
 |
 |
 |
|---|---|---|---|
 |
|---|
Float/second Int/second Clock Hertz
1938 Z1 .05 1 1 Mechanical
1940 Z2 .08 1.5 1.5 Mechanical
1941 Z3 .3 5.3 5.3 Mechanical
1944 Colossus 0 500000 5000 Vacuum tube Codebreaking. Integer operations
1945 Eniac 50 5000 100000 Vacuum tube Manhattan Project. Floating point
1959 IBM 7090 100000 100000 458000 Transistor Mass-produced
 |
|---|
 |
|---|
Computation speed is measured in GFlops (Giga Floating point operations per second). A floating point operation (Flop) is an add or a multiply.
A "core" is an independent floating point unit. Different cores can do different computations.
A core produces an add and a multiply once every clock cycle, hence it produces 2 floating point operations per cycle.
A core can be "vectorized", which means that it does many adds and multiples simultaneously. For vectorization, each element in the vector has to do the same computation. Gaming hardware is heavily vectorized.
The speed of a supercomputer is
Supercomputer speed = S = 2FCV Clock frequency = F Cores = C Vectorization = V Number of vectors per core
Speed per dollar, CPU = 2 GFlop/$ Speed per dollar, GPU = 40 GFlop/$ Memory, RAM = .2 GByte/$ Memory, solid state = 7 GByte/$ Memory, disk = 33 GByte/$ Speed per power = 200 GFlop/Watt (GPU) Battery energy per mass = .6 MJoule/kg Battery power per mass = 500 Watt/kg
 |
|---|
Supercomputers today have a speed of 1018 Flop/second. A computer powered by a blue giant star has a speed of order 1048 Flop/second. A computer powered by a galaxy cluster has a speed of order 1056 Flop/second.
Speed, computer in 2026 = e18 Flop/second
Speed, blue giant computer = e48 Flop/second
Speed, galaxy cluster computer= e56 Flop/second
Power, blue giant star = e32 Watt
Power, large galaxy = e36 Watt
Power, galaxy cluster = e40 Watt
Energy per Flop, 2026 = 1e-12 Joule/Flop
Energy per flop, far future = 1e-16 Joule/Flop
Lifetime, calculation of today= 3e7 second = 1 year
Lifetime, blue giant star = 3e13 second = 10 million years
Lifetime, galaxy cluster = 3e17 second = 10 billion years
Computer Flop total, 2026 = 3e25 Flop
Computer Flop total, blue giant = 3e61 Flop
Computer Flop total, galaxy cluster= 3e73 Flop
Tetration can represent numbers from 0 to 101010101010 on the same scale. It's beyond a logarithmic scale. Define:
Tet(0) = 0
Tet(1) = 1
Tet(2) = 10
Tet(3) = 1010
Tet(4) = 101010
Tet(X+1) = 10Tet(X)
Define a continuous function Y = Tet(X).
It has an analytic form that's complicated to express. It wasn't invented until 1961.
We define a piecewise interpolation with unit intervals.
"10" may be replaced by any number larger than ee-1.
Tetration converges if the base is less than ee-1 and larger than e-e.
Astronomy archives set an example for thoroughness, ease of access, and centralization.
Encyclopedia of Integer Sequences. OEIS Foundation
Prime counting function
PARI/GP: sieves primes with no upper limit. It is thread-optimized.
primesieve: sieves primes up to 2^64. It is thread-optimized.
FLINT/Arb: Zeta and (L)-function evaluation; consecutive zero isolation. Platt zeta function.
Zhang published a result that identified fresh powder.
Tao led a team to to tackle it, the Polymath8 project.
Clusters:
Smale solved the generalized Poincare conjecture for dimension > 4 in 1961, for which he won a Fields medal.
Freedman solved the generalized Poincare conjecture for dimension 4 in 1982, for which he won a Fields medal.
Hamiltion invented Ricci flow in 1982, a crucial tool.
The Poincare conjecture is the generalized Poincare conjecture for dimension 3.
Perelman solved it in 2002 using Ricci flow.
A "demon" is an unexpected phenomenon.
Ronald Graham backs the Erdos prize with cash payouts.
Prime gaps
Ekl, R. L. "Equal Sums of Four Seventh Powers." Math. Comput. 65, 1755-1756, 1996.
Acknowledgments: The author
thanks ChatGPT (OpenAI) for discussions that helped organize ideas, clarify
terminology, and explore possible frameworks for presenting computational reach
in mathematics.
0 < X < 1 0 < Y < 1 Y = X X = Y Linear
1 < X < 2 1 < Y < 10 Y = 10X-1 X = 1 + log10 Y Logarithmic
2 < X < 3 10 < Y < 1010 Y = 1010(X-2) X = 2 + log10log10 Y Double-logarithmic
3 < X < 4 1010< Y < 101010 Y = 101010(X-3) X = 3 + log10log10log10 Y Triple-logarithmic
etc.
Big primes. t5k.org
Prime gaps
Jan Feitsma: Base-2 Fermat pseudoprimes ≤ 264
Carmichael numbers ≤ 1021
Polynomials. EulerNet
Polynomials. Mathworld
Euler polynomials. Steven Dutch
Goldbach conjecture. Tomas Oliveira e Silva
Prime constellations. Norman Luhn
Prime counting function. Jan Buethe
Thomas Nicely
Sums of equal powers. Rizos Sakellariou
ZetaGrid. Riemann zeros
Prime counting function
Prime counting function. Jan Buethe
Dense prime cluster widths. Dense prime cluster numerosity
Catalan
Sierpinski
Riesel
Miller-Rabin.
Smallest strong pseudoprime to the first n prime bases.
Directly converts Miller–Rabin rounds into a guaranteed numerical reach.
* Smallest number that is sum of 2 positive distinct n-th powers in 2 different ways
1 = 32 - 23
24 = 210- 103
13 = 28 - 35
3 = 27 - 53
2 = 33 - 52
104 = 36 - 54
1 = 23 - 7
4 = 53 - 112
7 = 27 - 112
7153 = 312- 219
1 = 2*5 - 32
5 = 53 - 3*23
1 = 24 - 3*5
2 = 25 - 2*3*5
5 = 7*15 - 102
1.75 ~ (3/2)12 - 27 Pythagorean comma. Relates musical octaves to fifths.
1.024= 27/53 = 210/103
7/5 ~ 2½
Pi ~ 22/7
e^P ~ 20
e^e ~ 15.15
7, 8, 9, 10
25, 27, 30, 32
Hippasus ~-500 2½ is irrational
Pythagoras previously conjectured that all numbers are rational
Euler transcendental Definition of a transcendental number as not algebraic
Galois 1832 Proved that roots of polynomials of degree at least 5 cannot in general be
expressed with radicals
Gauss construction Polygons exist that cannot be constructed with a straightedge and compass
Wantzel 1837 Angles exist that cannot be constructed with a straightedge and compass
Liouville proof 1844 Proof that transcendentals exist
Liouville number 1851 Constructed the first transcendental number
Hermite 1873 Proof that e is transcendental
Lindemann 1882 Proof that π is transcendental
Grassman ~1868 Showed that arithmetic needs deeper axioms
Peano arith. axioms 1889 Suitable axioms for arithmetic
Cantor countability The set of real numbers has higher cardinality than the set of rational numbers
Transcendental numbers have the same cardinality as reals
Clue that set theory needs advance
Cantor theorem The cardinality of a power set is strictly greater than the cardinality of the original set
Clue that set theory needs advance
Axiom of Choice Independent of the Zermelo-Fraenkel axioms of set theory and independent of the continuum hypothesis
Banach-Tarski paradox Consequence of the Axiom of Choice
Godel theorems
Weierstrass function A function that is continuous everywhere and differentiable nowhere.
Introduced the concept of uniform continuity.
Cantor set 1875 The Cantor set is nowhere dense, but has the same cardinality as the reals,
whereas the rationals are everywhere dense, but countable
Clue that set theory needs advance
Koch snowflake Continuous perimeter with no tangent
Peano curve Space-filling
Russell paradox Clue that set theory needs advance
Hausdorf dimension 1918 Characterizes chaos
Poincare Chaos in gravitational dynamics
Ulam & von Neumann ~1945 Cellular automaton
Conway Game of Life 1970 Popularized cellular automata
Feigenbaum numbers Recurring numbers from chaos
Mandelbrot set Exhibit of fractals. Popularized fractals
Wolfram book Popularized cellular automata
Littlewood Existence of Skewes crossings
Mertens conj false 1985 Odlyzko & te Riele
Euler sum of powers 1967 Conjecture formed in 1778. Lander found a counterexample in 1967
Polya conjecture false
Mercury orbit anomaly Breaks the Newtonian gravity. Clue for general relativity
Hawking-Penrose General relativity predicts singularities
Einstein The equations of general relativity show that dark energy can exist
Schwarzschild Proved the existence of black holes
Quantum gravity The Standard Model and general relativity have clashes
Black hole information Do black holes conserve information?
Penzias & Wilson Cosmic background radiation
Guth cosmic inflation The hot big bang model needs extension
Dark energy discovery Fine-tuning problem
Oersted 1820 A magnetic field exerts a force on an electric current
Clue for the Maxwell equations
Maxwell equations The magnetic force is not Galilean invariant. Clue for special relativity
Poincare Unifies the Maxwell equations and the Lorentz equation
Maxwell demon
Szilard demon Information can be converted to work
Landauer demon Erasing information costs energy
Adiabatic index of oxygen Clue for quantum mechanics
Hydrogen Lyman lines Clue for quantum mechanics
Einstein photoelectric Clue for quantum mechanics
Heisenberg uncertainty
Quantum spin
Lamb shift Phenomenon beyond Dirac theory. Clue for quantum field theory
Aharonov-Bohm phase shift Quantum-mechanical phase effect. 1959
CP violation in weak force
CP non-violation in strong force The strong force need not conserve CP symmetry, but it does
Neutrino oscillations Neutrinos have mass
Fine tuning The standard model requires fine tuning
Matter-dominant universe Clue for baryon number non-conservation and lepton number non-conservation
Clue for a unification of the strong and electroweak forces
Mendelev Atom mass ratios are not necessarily integer ratios. Clue for the neutron
Beta decay mass non-conserve There must be a new particle
Dark matter There must be a new particle
$
Hilbert Riemann hypothesis 0 Unsolved Smale problem
Hilbert Solvability AX + BY = C 0 Unsolved The twin prime conjecture and the Goldbach conjecture are cases
Hilbert Recipricity laws in number fields 0 Unsolved
Hilbert Extend the Kronecker-Weber theorem 0 Unsolved
Hilbert Ovals 0 Unsolved Smale problem
Hilbert Variational problems 0 Unsolved
Hilbert Automorphic functions 0 Unsolved
Millenium Poincare conjecture 1000000 Solved in 2002 by Perelman
Millenium Navier-Stokes smoothness 1000000 Unsolved Smale problem
Millenium Birch & Swinnerton-Dyer 1000000 Unsolved
Millenium P-NP 1000000 Unsolved Smale problem
Millenium Riemann hypothesis 1000000 Unsolved Smale problem
Millenium Yang-Mills existence & mass gap 1000000 Unsolved
Millenium Hodge conjecture 1000000 Unsolved
Smale Diophantine solutions in exp time 0 Unsolved
Smale Gravitational equilibrium 0 Unsolved
Smale points on a sphere 0 Unsolved
Smale Shub-Smale tau-conjecture 0 Unsolved
Smale Pugh closing lemma 0 Unsolved
Smale Linear programming 0 Unsolved
Smale Is 1D dynamics generally hyperbolic? 0 Unsolved
Smale Diffeomorphisms 0 Unsolved
Erdos Prime gap conjecture 10000 Solved in 2002 by Maynard, Green, Ford, Konyagin, & Tao
Erdos Arithmetic progression conjecture 3000 Unsolved
Erdos Szemeredi theorem 1000 Solved in 1974 by Szemeredi
Erdos Unavoidable set of congruences 1000 Unsolved
Erdos Erdos discrepancy problem 500 Solved in 2015 by Tao
Erdos Erdos-Graham Egyption frac variant 500 Unsolved
Erdos No 4 points in a circle probem 100 Unsolves
Erdos Sidon set bound 100 Solved
Erdos Erdos-Selfridge question 25 Solved in by Hough Covering Systems
Erdos Graphic Sequence Tournament Problem 25 Solved
Erdos Collatz density 25 Unsolved
Erdos Monotone Subsequences in Matrices 25 Unsolved
Thurston Quotient spaces of PSL(2,C) 0 Unsolved
Thurston Hyperbolic volumes of 3-manifold 0 Unsolved
"Extreme Value Theory Analysis of Prime Gap Distributions: Statistical Analysis
of Cram'er's Conjecture and Light-Tailed Behavior". G. Afriyie 2025
Ekl, R. L. "New Results in Equal Sums of Like Powers." Math. Comput. 67, 1309-1315, 1998.
Elkies, N. "On A^4+B^4+C^4=D^4." Math. Comput. 51, 828-838, 1988.
Hoffman, P. The Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical Truth. New York: Hyperion, p. 195, 1998.
Lander, L. J. and Parkin, T. R. "A Counterexample to Euler's Sum of Powers Conjecture." Math. Comput. 21, 101-103, 1967.
Lander, L. J.; Parkin, T. R.; and Selfridge, J. L. "A Survey of Equal Sums of Like Powers." Math. Comput. 21, 446-459, 1967
Letac, A. Gazetta Mathematica 48, 68-69, 1942.
Meyrignac, J.-C. "Computing Minimal Equal Sums of Like Powers." http://euler.free.fr.
Moessner, A. "Einige Numerische Identitaten." Proc. Indian Acad. Sci. Sect. A 10, 296-306, 1939.
Subba Rao, K. "On Sums of Sixth Powers." J. London Math. Soc. 9, 172-173, 1934.
Wiles 1994
E. Brisse 1999
Resta 1999
Resta and Meyrignac 2003
1934 Subba Rao
M. Dodrill 1999, PowerSum
Erik Westzynthius
Largest known zero of the Riemann zeta function https://mathoverflow.net/questions/264052/largest-known-zero-of-the-riemann-zeta-function
© Jason Maron, all rights reserved.
Data from Wikipedia unless otherwise specified.