Prime Number Grid

by todsacerdoti • 11 months ago

296 96 11 months ago

susam7• 11 months 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

I hope this is fun for you too!

camillomiller• 11 months ago

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

jona-f2• 11 months ago

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.

Tepix2• 11 months ago

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 ;-) )?

susam7• 11 months ago

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.

davedx• 11 months ago

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.

lblume• 11 months ago

Numbers are prime irrespective of base.

teytra• 11 months ago

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").

susam7• 11 months ago

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.

reb• 11 months ago

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.

rmrfchik• 11 months ago

Nice patterns are reveals when cols is prime.

ethan_smith• 11 months ago

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.

scotty79• 11 months ago

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.

spongebobism• 11 months ago

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?

amne• 11 months ago

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.

madcaptenor4• 11 months ago

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.

Sharlin• 11 months ago

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.

agnishom• 11 months ago

Since this is in a grid, how about visualizing Gaussian primes instead?

throw3108222• 11 months ago

Kind of surprising, my intuitive idea of primes is that they become rarer much faster, while there's really a ton of them.

susam7• 11 months ago

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.

eru2• 11 months ago

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.

kristopolous• 11 months ago

This is a very well researched topic

https://en.m.wikipedia.org/wiki/Prime_number_theorem

Someone2• 11 months ago

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.

eru2• 11 months ago

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).

throw3108222• 11 months ago

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.

knome• 11 months ago

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?

mickeyp• 11 months ago

I really love susam's blog posts and curiosity. I highly recommend that people check out his site for more of his insights.

nyc111• 11 months ago

I tried but his pages do not have links to a home page or other posts

genezeta• 11 months ago

There's this https://susam.net/pages.html for your convenience. (Also this https://susam.net/links.html maybe a bit more organised.)

susam7• 11 months ago

Thank you for the kind words, Mickey! Your website too is a treasure trove of excellent information, especially for Emacs users like me!

vim-guru• 11 months ago

This works surprisingly well for logo design. Cool concept

martinclayton• 11 months ago

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.

susam7• 11 months ago

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);

AnotherGoodName3• 11 months ago

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.

quijoteuniv• 11 months ago

Wow! I see the pattern now! ;) … nice work

kitd• 11 months ago

Really interesting, stepping up and down the "cols" number, seeing the dots align at certain key points, especially at multiples of 30.

krige• 11 months ago

There's also a cool effect where incrementing columns by one has the dots align diagonally, and then vertically multiple times.

dev0p• 11 months ago

Editable size pls? I wonder if this could be visualized in 3 dimensions...

vintermann• 11 months ago

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.

aldonius• 11 months ago

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.)

fendy3002• 11 months ago

it's interesting that for 6 cols only the 1st and 5th column has value, ignoring first row.

seanalltogether• 11 months ago

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.

madcaptenor4• 11 months ago

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%)

wrigby• 11 months ago

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!

anthk• 11 months ago

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.

wmanley• 11 months ago

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".

willvarfar• 11 months ago

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!?

vincnetas• 11 months ago

https://www.alpertron.com.ar/ULAM.HTM

okokwhatever• 11 months ago

The good old internet. I miss it.

madcaptenor4• 11 months ago

Seconding the Ulam spiral. My first thought was "why can't I see the diagonals?" because I expected it to be the Ulam spiral.

BrainBacon• 11 months ago

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.

cuber_messenger• 11 months ago

Decreasing the number of columns looks like rotating some noisy parallel lines counterclockwise. Very fun.

courtcircuits• 11 months ago

Gonna make API calls to that next time I need to generate an Elgamal key pair

dirkc• 11 months ago

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

AmazingTurtle• 11 months ago

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

mg2• 11 months ago

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;

To this:

    if (Math.random()>0.99) return 1;

Very different. I wonder where the symmetry and all the other properties of the pattern come from when using primes.

BobbyTables2• 11 months ago

Almost looks like Klingon!

pinoy420• 11 months ago

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

polivier• 11 months ago

Are you talking about the patterns found in the linked website of the parent comment? Because there clear patterns there.

rbongers• 11 months ago

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.

AnotherGoodName3• 11 months ago

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.

segfaultgolf• 11 months ago

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!

mg2• 11 months ago

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.

photonthug• 11 months ago

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...

davidnc• 11 months ago

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.

sejje• 11 months ago

That's a 7 year old comment; did you just remember it existed?

Thanks for the link!

Chinjut2• 11 months ago

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

Chinjut2• 11 months ago

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.)

xerox13ster• 11 months ago

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.

shaunxcode• 11 months ago

I have continued to research this - should be publishing a zine about it soon!

qmmmur• 11 months ago

Where?! Interested here.

haar• 11 months ago

Setting it to 1, 7, 100 looks like a ticker tape of constellations (like Stargate Chevrons) :D

ilmenit• 11 months ago

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.

y42• 11 months ago

shameless plug

https://primes.nickyreinert.de

(desktop recommended)

GistNoesis• 11 months ago

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.

dfee• 11 months ago

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

physix• 11 months ago

https://news.ycombinator.com/item?id=44888548

butlike• 11 months ago

Wonder what this would output if run through a FORTRAN system with a few punch cards.

ragmondo• 11 months ago

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.

themafia• 11 months ago

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.

stillthat• 11 months ago

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?

Prime Number Grid

Related Stories