Prime Number Grid
susam.net291 points by todsacerdoti 2 days ago
291 points by todsacerdoti 2 days ago
Hello! I wrote this simple prime number grid visualiser last night, just for fun. It is inspired by the "Show HN" post https://news.ycombinator.com/item?id=44888548 that I stumbled upon a few days ago.
My tool uses the Miller-Rabin primality test with prime bases drawn from https://oeis.org/A014233 to determine whether a number is prime. This allows it to handle numbers up to 3317044064679887385961980.
For example, https://susam.net/primegrid.html#3317044064679887385961781-2... shows the upper limit of the numbers this tool can check. The three circles displayed there represent the following prime numbers:
3317044064679887385961783
3317044064679887385961801
3317044064679887385961813
Great visualization! Can you please add a on-mouse-over so when i hover my mouse over a dot i can see the prime number it represents?
Would we see new patterns emerge if the number of columns increases per row by X (X being constant or perhaps prime numbers ;-) )?
Adding mouseover text to every prime number slows down rendering on large grids (say, with a million or more numbers). So mouseover text is available as an optional feature. You can toggle it using the 't' button at the top: click once to enable the text, and click again to disable it.
Thanks, that was fast!
Here's an idea on how to implement it without the slowdown: https://jsfiddle.net/qpswztj8/
Given that it's a preformatted text with a known number of columns, the number below the mouse pointer can be computed using the mouse position, character width and line height.
It's so cool actually!
You actually sent me on a rabbit hole trying to visually look for patterns :D But I guess the discretionality with which you can organize in rows and columns makes mine quite a pointless excercise :D
If you select 30, 60 or 90 columns you get the clearest patterns. It kinda seems that the more divisors the number of columns has, the clearer the vertical clusters are. And somehow 30, 60 and 90 stand out. Number theory is so weird. I expected more randomness.
The reason vertical clusters appear in these examples is that all your chosen numbers are multiples of 6. A prime number greater than 3 leaves a remainder of either 1 or 5 when divided by 6. In other words:
For all primes p greater than 3, p ≡ ±1 (mod 6).
Therefore, when the total number of columns is a multiple of 6, all primes except 2 fall into the same columns, namely 1, 5, 7, 11, 13, 17 and so on.
I just set the column width to 6 to verify this for myself. What a neat tool!
If you can do 210 you'll see even more.
Any primorial will give you the strongest patterns. (Primorials are the products of the first N primes, so 2, 6, 30, 210, etc.)
Thank you for making and sharing this! It's fun to quickly increment the column counter and spot repeating patterns over time — little spiral movements, big swinging lines.
Growing up I loved math's logic puzzle elements, but it got tough when presentation of the subject became more abstract in late high school and college. Visualization tools like this would have gone a long way toward making the concepts concrete and keeping me curious about the relationships behind the symbols.
I think another interesting feature would be if you could change the number base to 16 or some other base, I'm really curious if the pattern would change.
> I think another interesting feature would be if you could change the number base to 16 or some other base, I'm really curious if the pattern would change.
Whether a number is prime has nothing to do with the base we use to write it. Changing the base wouldn't affect the visualisation at all. A number is either prime or not regardless of base. Since this grid only marks prime positions with circles, the pattern would look exactly the same. In fact, you can already imagine the numbers in any base you like while looking at the visualisation.
Numbers are prime irrespective of base.
Since I seriously doubt that these numbers were checked in decimal, I would be led to believe base-2 is working and working well, as well as all other even bases. Ood bases would be fun,but much slower.
I tried odd number of rows and prime number of rows. All very interesting.
Set columns to 6, and the pattern is changed in an "interesting" way.
All primes are n*6 +/- 1 (after the primes 2 and 3 that are "special").
Set cols to anything divisible by 6, to get the same kind of "stacks" with more cols (i.e. 90)
Here is a strange one:
You look at integers in "packs" of 100. If a pack contains a prime number, you color it black, otherwise you color it red.
The first pack contains 100 consecutive integers. The second every second integer. The third every third integer and so on.
Every pack starts where the last one stopped.
On the first row, you draw 1 pack, on the second 2, on the third 3 and so on:
https://www.gibney.org/parallax_primes
It looks like hieroglyphs from another universe.
I'm still not sure why it looks the way it looks.
If you want to compare it to a random distribution, you can change this line:
if (isPrime(myNum)) return 1;
if (Math.random()>0.99) return 1;
This comment does a great job of clarifying the picture: https://news.ycombinator.com/item?id=17106193.
It's effectively a visualization of gcd(x,y), and has almost nothing to do with primes. Once you realize that, it's a lot easier to reason about a lot of the patterns, although it is still a pretty interesting visualization.
That's a 7 year old comment; did you just remember it existed?
Thanks for the link!
Your description here does not quite match your linked code, in that it is not that the N-th pack contains integers spaced out by N. Rather, packs on the N-th row contain integers spaced out by N. For example, the third pack does not contain "every third integer", but rather draws alternating integers just like the second pack, because it is on the second row. The second pack contains (first cell of the second row) contains {101, 103, 105, ..., 299} and the third pack (second cell of the second row) contains {102, 104, 106, ..., 300}.
With this in mind, the seeming patterns of the figure you link to are explained by https://news.ycombinator.com/item?id=17106193
My one quibble with the comment I linked is about asymptotics. By the Prime Number Theorem, asymptotically, the density of black squares should approach zero and the density of red squares should approach 100% (including among the left diagonal which is entirely black in the displayed window, and including losing the regular appearance of rows that are entirely black except for their last cell. These black line patterns in the displayed window are both small number phenomena caused by (1 - 1/ln(R))^100 being nearly zero for small R, which stops and then goes the other way for large R.)
Ok this nerd-sniped me pretty good, never seen this before and assumed it would be quickly connected to the Ulam spiral mentioned elsewhere in the the thread. That particular rabbit hole kinda bottoms out in polynomial residues and the very mysterious-sounding "Conjecture F" [0].
This parallax primes thing though led to the linked page [1] which has lots of background and other connections, including the most satisfying part, which turned out more geometric [2]
[0] https://en.wikipedia.org/wiki/Ulam_spiral#Explanation [1] https://www.novaspivack.com/science/we-have-discovered-a-new... [2] https://www.cut-the-knot.org/Curriculum/Arithmetic/PrimesFro...
Playing with this: https://g.co/gemini/share/b1979827dbe8
Okay so if you iterate only even or odd packings the pattern actually converges, which is crazy!
Yes, I noticed that too. The smaller the pack size, the more random the image. The larger, the more it converges to the final pattern.
I've been messing with this and you can get a very detailed view of another highly self-similar structure by changing the packsize to 1, the cellsize to 2, and then adding packSize++; to the end of the drawRow function.
I have continued to research this - should be publishing a zine about it soon!
It looks the way it does because we like to see patterns even where there are none. E.g. you see a number 696969 and this seems more significant than 482649 for whatever reason
Prime numbers are a pattern; take the natural numbers - starting after 2, exclude every number that isn't 2, starting after 3, exclude every number that isn't 3, etc.
It repeats like this predictably. Even though it changes, the way in which it changes is also predictable. Their repetition and predictability make prime numbers a pattern.
Out of the fundamental pattern of prime numbers, higher-level patterns also appear, and studying these patterns is a whole branch of math. You can find all kinds of visualizations of these patterns, including ones linked in this thread.
It's not that you're seeing a pattern that's not there, it's that you're seeing a pattern that gradually becomes infinitely complex.
Prime numbers have extremely well understood patterns and this is what he's seeing. There's a weird and persistent myth that there's 'no patterns in prime numbers' but of course factors repeat at known intervals and prime numbers are the inverse of numbers with factors. So if you can accept that numbers with factors have a pattern to them (which should be obvious, they repeat at known intervals by definition) you should be able to accept prime numbers, the inverse of numbers with factors, have patterns too since they are just the gaps in the pattern of numbers with factors.
These patterns were documented and well understood starting in BC times by Erasthosenes and learning them as part of prime number theory is a 101 course in tertiary maths education. So it's really really weird for anyone to say "there's no patterns". There are and they are extremely well understood and known.
Here's a simple pattern; All prime numbers above 2 are odd. Well duh right? Otherwise they'd be a multiple of 2, not prime.
Well let's extend this. All prime numbers above 6 are of the form 6n + 1 or 6n +5. Otherwise they'd be a multiple of 2 or 3.
Once more; All prime numbers above 30 are of the form 30n + one of [1,7,11,13,17,19,23,29]. Anything else would be a multiple of 2,3 or 5. You can extend this forever. Note each time we do this we're reducing how many numbers could possibly be prime. From 1/2 to 2/6 to 8/30 numbers possibly being prime. Keep going with this and you'll converge to the prime counting function.
Basically whenever you have a composite number there's well understood periodic gaps in primality. People understand this more intuitively for base 10 where anything ending in 0,2,4,6,8 is a multiple of 2 and anything ending in 0,5 is a multiple of 5 hence you only get primes ending in 1,3,7,9 when writing in base 10 but this idea works for any composite number. This leads to the extremely well known and well understood patterns you get when you graph primes in various ways.
Are you talking about the patterns found in the linked website of the parent comment? Because there clear patterns there.
Perhaps explore plotting the Ulam spiral too? https://en.wikipedia.org/wiki/Ulam_spiral
Of course the pressing question is, if this is the start field for a Conway game-of-life, do any interesting patterns evolve?
It would be fun to brute-force a few starting grid sizes and seeing how long the game continues. Games that last more than a few steps can be set aside for human evaluation.
Because if it turns out that some particular smallish grid or spiral of primes causes something interesting to happen in game-of-life, then you can imagine HN melting down!?
Not exactly the same, but I made this Ulam spiral generator more than a decade ago.
https://embed.plnkr.co/mdZX6C/
It isn't just doing primes though, instead the size of the dot generated is dependent on the number of even divisors for the number at that position.
Seconding the Ulam spiral. My first thought was "why can't I see the diagonals?" because I expected it to be the Ulam spiral.
Kind of surprising, my intuitive idea of primes is that they become rarer much faster, while there's really a ton of them.
They indeed do become rarer. Plotting all the primes in a single row makes this apparent, like so: https://susam.net/primegrid.html#1-1-1000000
In fact, according to the celebrated prime number theorem, the number of primes less than or equal to n is asymptotic to n/log n, which means the density of primes near n is asymptotic to 1/log n.
I have a small section about this at https://susam.net/journey-to-prime-number-theorem.html#prime... if you want to read more about this.
See also: https://en.wikipedia.org/wiki/Prime_number_theorem
Yes.
> In fact, according to the celebrated prime number theorem, the number of primes less than or equal to n is asymptotic to n/log n, which means the density of primes near n is asymptotic to 1/log n.
When written down as a string of digits, log n is another way to say 'proportional to the number of digits'.
The number of digits grows fairly slowly, thus also the 'probability' of a number being prime drops very slowly.
That’s what ‘everybody’ thinks. I think that’s from reading so much about them being hard to find. They aren’t hard to find, though, it’s (as far as we know) hard to recognize integers as being primes.
There are more prime numbers than there are squares of integers.
> I think that’s from reading so much about them being hard to find
More from the fact that each prime number makes all its multiples non-prime, so you'd expect this would accumulate quickly in making primes an increasingly rare find. Which is the case, but slower than intuition suggests.
>There are more prime numbers than there are squares of integers.
all integers have a square, while not all integers are prime.
in any given span, you'll see more primes than squares, however.
more dense?
> all integers have a square, while not all integers are prime.
That’s true, but I don’t see how that’s an argument. “All integers have a prime ‘the nth prime’, while not all integers are squares” similarly is true, but not an argument as to which set is denser.
They must both have the same cardinality, ℵ0, because they are both infinite subsets of the natural numbers, and so can each be laid out in order and paired with every natural number.
For example, the number of primes less than n is around n/log(n) while the number of squares less than n is around sqrt(n), which is much smaller.
> They aren’t hard to find, though, it’s (as far as we know) hard to recognize integers as being primes.
Depends on what you mean by 'hard'. It's easy in the sense that we have algorithms to decide whether a number is prime or composite that take time polynomial in the space it takes to write down your number (ie polynomial in log n).
Nice patterns are reveals when cols is prime.
This happens because when columns = p (prime), numbers in each column share the same remainder mod p, creating visible diagonal patterns as multiples of p are eliminated from primality.
Not so much that cols is prime as that cols+1 or cols-1 has lots of factors - see for example 25 or 91 or 119. But it does seem like numbers adjacent to primes have a lot of factors.
The more factors an (even) number n has, the more likely it is that n+-1 is prime because those numbers cannot have any of the factors of n as factors. At the same time it is impossible that n+-2 or 4 are prime and unlikely that n+-3 is prime because 3 is likely to be a factor of n. And if additionally 5 is a factor, the primeless gap is even wider. So the primes stand out.
When the col is seven, there are a lot of diagonals going from top right to bottom left. When col is five, from top left to bottom right. Are runs of consecutive sexy primes also this frequent for larger numbers, or does that pattern break down at some point?
I find the patterns from cols % 30 == 0 very interesting (30,60,90,120, etc.) .. just straight vertical lines.
And if you go up or down by one (119 or 121) they appear to "rotate" left or right.
Very cool viz tool.
Almost all of these patterns that you see don't really come from primes. If you display numbers not divisible by first 100 natural numbers you get pretty much the same picture.
I did recently also a tool for prime numbers visualization: https://ilmenit.github.io/prime-fold/ It's not only for visualization but also discovering of mathematical functions that generate or embed prime numbers using evolutionary algorithms and fitness functions. It has two modes: PrimeFold Mode (2D Embedding): Enter or evolve two functions, f_x(n) and f_y(n), to map numbers to 2D points. Primes and composites are visualized differently. This mode helps you discover spatial patterns and structures unique to primes. Example: f_x(n) = n, f_y(n) = n^2 or simply n, n^2. PrimeGen Mode (1D Generation): Enter or evolve a single function, f(n), to generate numbers. The app visualizes which outputs are prime and how many unique primes are produced. Example: f(n) = 2*n + 1.
Setting it to 1, 7, 100 looks like a ticker tape of constellations (like Stargate Chevrons) :D
https://susam.net/primegrid.html#1-200-330
zoom out, then play around with cols +/-1 and observe the pattern change. I observe the pattern from -7 to +5; same on #1-200-420
Here's a weird relationship between consecutive primes that I discovered while bored trying some python...
Take the last digit (in base 10) of consecutive primes. Now ignore 2 and 5 as .. well they only occur once, and look at the mapping between 1->3, 1->5, 1->7, 1->9 ... 3->1 etc etc..
You would think that they would pretty much all be equal, I mean primes are "random" right?
WRONG!
There are statistically significant differences in those edges, and no-one knows why.
My intuition was that there were even fewer primes and there was a greater rate of decrease as the numbers got bigger – but it looks like there are so many! Even at [1, 10,000, 10,000] it seems pretty dense near the bottom, though perhaps less dense.
Apparently the average gap between primes is `log(n)`: https://en.wikipedia.org/wiki/Prime_number_theorem
Fun to see that prime numbers of columns causes stripy patterns, and some stripe to the left and some stripe to the right. Probably some deep number theoretic reason for that.
You'll find that when the number of columns is a multiple of 6 you'll get obvious columns in the dots, and if it's +1 or -1 modulo 6 the columns become diagonal stripes (the process sort of continues for ±2 and at ±3 it's pretty broken down).
It's a fairly straightforward number theory result that every prime > 3 is congruent to ±1 modulo 6 so that's probably what you're seeing. (Can't be +2 or +4 because that's divisible by 2, can't be +3 because that's divisible by 3, leaving +1 and +5 aka -1.)
I'd like it if I could set "columns" to be an expression. That expression could be something like "1.1415 * row". That'd be neat.
Hours of fun (stimulation?) to be had...
Try these shapes: 100x113, then 100x114, then 100x115, the "patterns" swing from slant down, to vertical, to slant up.
I'd love this (even more) with some animation and colo(u)r options.
This was just a quick experiment I put together last night in my free time, so the tool is quite bare bones. If you're on a desktop browser and don't mind opening the developer tools console, you can run this little snippet to animate the grid:
cols.value = 1n; setInterval(() => {cols.value++; readInput()}, 250);This is also basically the most trivial proof that primes are infinite. If you think you've discovered all the primes, just multiply all those primes together and add or subtract 1. You now have a new number that shares no factors with those primes.
Nice visualization! 2 suggestions if I can nitpick :)
1. Make the grid render as a square when rows == columns
2. Default to the largest number of rows and columns that would still avoid page scrolling
Really interesting, stepping up and down the "cols" number, seeing the dots align at certain key points, especially at multiples of 30.
There's also a cool effect where incrementing columns by one has the dots align diagonally, and then vertically multiple times.
I really love susam's blog posts and curiosity. I highly recommend that people check out his site for more of his insights.
I tried but his pages do not have links to a home page or other posts
There's this https://susam.net/pages.html for your convenience. (Also this https://susam.net/links.html maybe a bit more organised.)
Decreasing the number of columns looks like rotating some noisy parallel lines counterclockwise. Very fun.
Wonder what this would output if run through a FORTRAN system with a few punch cards.
no idea why or how, but are there attempts at implementing all that crazy math stuff like golden ratio, prime grids, fractals and what not into the game of life, Lenia?
it's interesting that for 6 cols only the 1st and 5th column has value, ignoring first row.
Yeah I was gonna say the same thing. So in a base-6 counting system primes must be very intuitive to spot. Although also expanding it out to base-12 shows the primes always fall into 4 specific rows.
It's similar to how in base 10 all primes must have last digit 1, 3, 7, or 9. But it woks slightly better in base 6 because fewer numbers are candidates (2/6 ~ 33% instead of 4/10 = 40%)
Yep and you can also just keep going with this to get to the Prime Number Theorem.
If you just consider odd numbers you know that at best only half of numbers can be prime. We've ruled out 1/2 of numbers.
If you then multiply 2 x 3 to get 6 you can state all prime numbers above 6 are of the form 6n + [1 or 5], everything else is a multiple of 2 or 3. We've now ruled out 1/3 more numbers in that remaining half we already ruled out above. Leaving 1/2 x 2/3 = 1/3 numbers possibly being prime (you could write this in a non-simplified form as 2/6 to match the count above).
If you then multiply 2 x 3 x 5 to get 30 you can state that all numbers above 30 are of the form 30n + [1,7,11,13,17,19,23,29]. The rest are multiples of 2,3 or 5. You've now ruled out another 1/5 of numbers from that remaining 1/3 above. Leaving 1/3 x 4/5 = 4/15 numbers possibly being prime (or 8/30 if you don't simplify the fraction to more clearly match what we counted above).
If you continue this you have a series that's multiplicative_sum( 1 - 1/p) of all primes so far. This function is called Euler's product formula and is the inverse of the famous Riemann Zeta Function (1/ζ(s)). This series converges to the Prime counting function https://en.wikipedia.org/wiki/Prime_number_theorem#Non-vanis... which you can intuitively understand from what i've written above.
Fwiw these patterns in prime numbers, or more specifically the gaps where numbers can't possibly be prime, are extremely well understood. They were first documented by Erasthosenes in BC times who used the above to quickly find new large prime numbers. While it's fun to look at patterns in primes and any enthusiasm should be encouraged i will take a moment to point out that mathematicians occasionally deal with lay people who think they've stumbled on some revelatory new thing by observing these well known patterns in primes. There's a myth that 'there's no patterns in primes'. But... that isn't true at all. We know there's patterns. It's the basis for prime number theory. It's been known for a few thousand years now.
I enjoyed looking at this one too - playing around for a minute on paper with it was fun.
The numbers in each row (when cols is set to 6) are of the form:
6n+1, 6n+2, 6n+3, 6n+4, 6n+5, and 6n+6
Only 6n+1 and 6n+5 can't be trivially factored:
6n+1, 2(3n+1), 3(2n+1), 2(3n+2), 6n+5, 6(n+1)
So it follows that for any n >= 1, numbers in columns 2, 3, 4, and 6 can never be prime. Fun!
Gonna make API calls to that next time I need to generate an Elgamal key pair
Since this is in a grid, how about visualizing Gaussian primes instead?
This works surprisingly well for logo design. Cool concept
Wow! I see the pattern now! ;) … nice work
I'd love this but in SDL+GL allowing to scale up and down an image. Or better, a command to write an XBM/XPM image and then I'd convert it to any format I like.
Scaling is already supported - try Ctrl+Mouse Wheel or pinch to zoom on mobile. It also supports writing an image with the keyboard shortcut "Print Screen".
Editable size pls? I wonder if this could be visualized in 3 dimensions...
The problem with this visualization is that the pattern we see are meaningless.
It's making me thing of sieving, like in Sieve of Eratosthenes. But we have progressed a lot since.
What's nice about primes are the abstract ideas they generate, and the properties they have.
Primes connect numbers together. It allows you to form "groups" ( https://en.wikipedia.org/wiki/Group_(mathematics) ) of elements which don't have "subgroups". They are the sizes of the groups which don't have subgroups. (https://en.wikipedia.org/wiki/Cauchy%27s_theorem_(group_theo... )
If you want to know more about primes, you can look at the factorization of numbers problem.
You need to wrap your head around Euclid's algorithm (300 BC but it still matters a lot), this guy stumbled onto something very deep.
Prime numbers color other numbers. Once you pick a prime, number smaller that it can be colored as either "square" or "not square" (in the cyclic group defined by the prime). That's something figured Euler with https://en.wikipedia.org/wiki/Euler%27s_criterion .
It's one angle of attack to the factorization problem. This breaking of symmetry has been exploited in https://en.wikipedia.org/wiki/Quadratic_sieve .
But that's not the algorithm, I want to speak of today. I'd rather speak of https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factori... . The principle is simple, build a mathematical construct (elliptic curve) using the number which is not a prime and you want to factorize, and treat it as if it was a prime. Then you watch the construct crumble, trace the bug, and you have your factors.
If you are more mathematically proficient, you can also have a look at the General Number Field Sieve, but it's much harder.
To conclude I'd like to give a final nugget for the road : https://en.wikipedia.org/wiki/Montgomery_modular_multiplicat... a nice trick around division.
[dead]