Primes ยท Prime numbers
The Ulam spiral
Write the numbers in a spiral and mark the primes, and they fall on diagonals. Zoom, pan, start anywhere, and highlight Euler's polynomial.
Drag to move, scroll or use the buttons to zoom. Runs in your browser.
The Ulam spiral is what you get when you write the whole numbers in a square spiral, starting with 1 in the middle, and mark the primes (found with a sieve). They don't scatter evenly. They pile up along diagonal streaks, and the pattern is still there in a spiral of a million numbers. Drag the picture to move, scroll to zoom, and move the pointer over a cell to see its number.
Ulam's doodle
Stanisław Ulam, the Polish–American mathematician who worked on the hydrogen bomb and Monte Carlo methods, found the pattern in 1963. In Martin Gardner's retelling, Ulam was at a scientific meeting listening to a long and very boring paper, and began doodling numbers in a spiral on a piece of paper and circling the primes. The diagonals appeared. Back at Los Alamos he and his colleagues Myron Stein and Mark Wells used the MANIAC II computer to extend it to about 100,000 points, and Gardner described it in his March 1964 Mathematical Games column in Scientific American. Gardner's account is the source for the meeting story, and the tool here lets you check the maths part for yourself.
Why the diagonals
Each diagonal of the square spiral holds the values of a quadratic polynomial. One diagonal of the spiral that starts at 1 holds 3, 13, 31, 57, 91, 133, 183, 241, which is 4n² − 2n + 1, and in a spiral that starts at s, the main diagonal holds s + n(n + 1). So a streak of primes on a diagonal is a polynomial that produces an unusual share of primes, and that has a reason. A typical number near 1012 is divisible by 2 half the time, by 3 a third of the time and so on, and that's what keeps primes rare. Some polynomials are never divisible by some small primes: n² + n is always even, so n² + n + 41 is always odd. Every small prime a polynomial can never be divisible by raises its share of primes. In 1923 Hardy and Littlewood gave a conjecture that predicts how dense the primes should be along any given polynomial, and it matches what the spiral shows. Nobody has proved it for any polynomial of degree 2 or more. It isn't even known whether n² + 1 gives infinitely many primes.
Euler's 40 primes
The most famous polynomial is n² + n + 41, which Euler noted in 1772. It gives a prime for every n from 0 to 39: 41, 43, 47, 53, 61, 71… up to 1,601. At n = 40 it gives 1,681, which is 41². The tool's Start at 41 button puts 41 in the middle of the spiral so Euler's primes run along a single diagonal, and highlights them. The related n² − 79n + 1601 isn't a new polynomial. It's Euler's with n shifted by 40, so it takes 80 consecutive prime values, but only 40 different ones, since each appears twice. The code checks both (scripts/examples/sieve-ulam-examples.mjs). Euler's polynomial is never divisible by any prime below 41 (the code checks every residue), which is the source of its luck. Over the first million values of n, 26.1% of its values are prime, against about 3.9% for random numbers of the same sizes, nearly seven times as many. The reason runs through the number 163, one of the nine Heegner numbers, which is 4 × 41 − 1: a theorem of Rabinowitsch from 1913 says that n² + n + A gives primes for every n from 0 to A − 2 only when the number field built from √(1 − 4A) has unique factorization, and 41 is the largest A for which it does.
The Sacks spiral
Switch the tool to Sacks to see a variant by Robert Sacks, from 1994. Each number n goes at distance √n from the center and is turned by one full turn for every perfect square, so all the squares line up along the ray to the right of the center. Quadratic polynomials now show as curved arms instead of straight diagonals, and Euler's polynomial makes a clear one.
What the spiral doesn't mean
The streaks are real, but they don't give you a way to predict primes. They tell you some polynomials are lucky, not where the next prime is. Primes still look random in every test mathematicians have applied, in the way that matters for public-key cryptography. Pick a random number of 1,024 bits and about one in 710 is prime, wherever you start (the key-size page works that out). How closely the primes follow their average density is the subject of the Riemann hypothesis page.
Common questions
Do the lines go on forever?
Look further out and they thin out but don't vanish. A quadratic polynomial's share of primes falls slowly, along with the primes themselves. Try starting at a large number, such as 1,000,000,000,000, to see the streaks in a part of the number line far from 1.
Why does the picture change when I change the starting number?
Moving the start shifts every cell's number, which changes which diagonals hold polynomials that avoid small primes. Starting at 41 makes the main diagonal Euler's polynomial. Starting at 17 puts n² + n + 17 there instead, which gives primes only for n from 0 to 15 (at 16 it gives 17²), so the diagonal is much less striking.
Is there a prime pattern we can use to break RSA?
No pattern of this kind is known. RSA breaks if factoring is easy, and the spiral doesn't help with factoring.