Prime Number Grid
susam.net
susam.net
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
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
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.
Any primorial will give you the strongest patterns. (Primorials are the products of the first N primes, so 2, 6, 30, 210, etc.)
Would we see new patterns emerge if the number of columns increases per row by X (X being constant or perhaps prime numbers ;-) )?
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.
I tried odd number of rows and prime number of rows. All very interesting.
All primes are n*6 +/- 1 (after the primes 2 and 3 that are "special").
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.
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.
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;
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.
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.
Okay so if you iterate only even or odd packings the pattern actually converges, which is crazy!
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...
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.
Thanks for the link!
With this in mind, the seeming patterns of the figure you link to are explained by https://news.ycombinator.com/item?id=17106193
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!?
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.
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
> 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.
There are more prime numbers than there are squares of integers.
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).
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.
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?
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.
And if you go up or down by one (119 or 121) they appear to "rotate" left or right.
Very cool viz tool.
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
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.)
Apparently the average gap between primes is `log(n)`: https://en.wikipedia.org/wiki/Prime_number_theorem
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.
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.
cols.value = 1n; setInterval(() => {cols.value++; readInput()}, 250);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
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.
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!
https://primes.nickyreinert.de
(desktop recommended)
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.