An Interesting Pattern in the Prime Numbers: Parallax Compression | Hacker News Reader

An Interesting Pattern in the Prime Numbers: Parallax Compression

novaspivack.com

626 pointsairesearcher179 comments

The drawing is incorrect.

More specifically, it’s a drawing of OEIS A054521 (black if gcd(row, col) == 1, red otherwise), not of the parallax compressed primes. The two drawings do not match as claimed. The first place where they differ is row 9, column 1, which is drawn as black even though none of 217, 226, 235, 244, 253, 262 are prime.

It’s clear that gcd(row, col) == 1 is a necessary condition for there to be any primes in that cell (which consists of the numbers col + 3row² − 3row, col + 3row² − 2row, col + 3row² − row, col + 3row², col + 3row² + row, col + 3row² + 2row), but it’s not sufficient. There’s no way it could be sufficient, because there are only constantly many (six) numbers tested in every cell, but the asymptotic density of the primes goes to 0 and the asymptotic density of A054521 goes to 6/π².

Their picture is correct, but only because they are doing something more ridiculous than this. Every one of the squares in their picture represents 75 numbers, not 5 numbers.

Click on the definition of T, and you see exactly the A054521 formula.

T = (n, k) => { return (GCD(n, k) == 1) ? 1 : 0; }

The given code doesn’t use primes, primesSet, or isPrime at all.

But that does produce a picture identical to theirs. Because they are using 75 numbers per square, they do end up hitting at least one prime in each box with (n,k)=1 for the first 75 rows. This pattern won't continue much longer, which is why they've conveniently stopped the picture at that point.

The claim is that using N numbers per square will result in the pattern holding for N rows, for arbitrarily large N.

Even if I’m misunderstanding how this is supposed to work for odd n, this claim fails for plenty of even n.

n = 14: fails on row 13, col 3

n = 20: fails on row 17, col 8

n = 30: fails on row 17, col 7

n = 38: fails on row 37, col 8

n = 44: fails on row 31, col 2

n = 50: fails on row 43, col 13

…

Those are some pretty basic checks to miss. Perhaps I've misread OP's claim.

I think OP is a bit confused, the post is very ambiguous and on telegram he added more info but still hasn't fully formalized what he's trying to say

OP here - really it’s just a matter of I found a cool thing and wanted others ideas/input. I never had a pretense of a proof or a formalization just a cool pattern that emerges from folding the Ulam Spiral up a certain way. I think we were over zealous in the gcd triangle being an exact correspondence now as it clearly is not for some cells.

The pattern does not exactly match GCD as it turns out - but that makes it more curious actually. Here is the Mathematica code that does work for other values.

Https://GitHub.com/shaunxcode/a-pattern-in-the-primes

From OP: > Interestingly, this same pattern holds for more numbers, and for different intervals.

He's not claiming it holds for _all_ n, just for _many_ n.

I think you may misunderstand what terms are in a cell. For instance in your first example what numbers live there? In that observable you can run cellToTerms(row,n,binomialCoEfficient2,col) to get the terms. You can then chain .map(isPrime) (for reasonable sizes it is slurping in data to make testing faster). Those fns are there for interactivity I have not gotten around to adding yet.

I used range(row * (row - 1) // 2 * n + col, row * (row + 1) // 2 * n + col, row) in Python. For n = 14, row = 13, col = 3, this is

[1095, 1108, 1121, 1134, 1147, 1160, 1173, 1186, 1199, 1212, 1225, 1238, 1251, 1264]

none of which are prime. cellToTerms(13, 14, binomialCoEfficient2, 3) in the observable gives the same list (though no such calls are made when generating the picture).

Ok going back to the mathematica version that does it the slower primality testing per terms in cell way I am seeing the deviations meaning the gcd triangle is not an exact match to what we have here.

Here is the code on GitHub - it renders it correctly and addresses the issues. Https://GitHub.com/shaunxcode/a-pattern-in-the-primes

Can you explain how that picture would be produced with 75 numbers per square? The generalization that seems obvious to me already fails in both cells of row 2, because 75 is odd:

row 1, col 1: [1, 2, 3, …, 75], has primes

row 2, col 1: [76, 78, 80, …, 224], no primes

row 2, col 2: [77, 79, 81, …, 225], has primes

You are completely right; their pattern holds iff (I believe, not proven!) the number they take 75 for is even. If you take any even number of rows (== amount of numbers per cell, in their construction), say 6, or 74, or 76, the pattern works.

No, it still fails for even n; see my other comment: https://news.ycombinator.com/item?id=17104624

Fair point, I missed that. Scratch my claim.

Then their claim that this pattern holds isn't even true; as pointed out elsewhere, and is obvious when you write out the sequence items explicitly in terms of their coordinates, any gcd!=1 cell will be red. But a gcd=1 cell need not be black, for many n.

From what we have seen in our tests, the pattern holds for the number of rows n, where n = the number of integers contained in a cell. After n rows the symmetry breaks. We haven't tested every possible n yet however. It would be great to do more tests and let's see if there are exceptions.

Actually someone did point out an exception and it generates something very interesting we didn't see before. The pattern is different for odd n. But also has an interesting self-similarity. See the discussion on Telegram about this. https://t.me/joinchat/G8AnchIna2q8yn1lGHirkA

UPDATE:

Thanks to comments from readers we have found that the pattern does not exactly match the GCD triangle for some values of the number of cells and rows.

This possibly makes it a more interesting finding. But it also means we can’t use GCD to render it quickly for all values.

In the code on Observable we were using GCD as a shortcut to render it because it saved time compared the earlier approach. However readers correctly pointed out that the rendering was not always correct using GCD.

Now that we know GCD doesn’t apply to all values of n, we are reverting to the original code, which generates the correct renderings for all values - but is slower - and there will be an update on Observable soon.

Meanwhile - to see the original code at work, and test it out for any value yourself, here is the Mathematica notebook code:

Https://GitHub.com/shaunxcode/a-pattern-in-the-primes

The Observable JavaScript code is being updated soon to account for this.

Join the discussion in the Telegram group as well - details below.

You mean 24/tau^2, right?

Your point about the deviations is taken - the gcd triangle is not an exact fit for the pattern. Working on an updated version this evening. Specifically for odd n it does not work and there are occasional asymmetries.

The rendering was for n=74 in fact, not for n=75. The pattern does seem to recur for even numbered n values and for those we think it matches GCD (where cells contain an even number of integers, and we render for the same even number of rows). But this has not been proved yet. However when n has odd values, the pattern does not always match GCD, it turns out. This is interesting and means that it may be a less “trivial” pattern in fact.

See the Mathematica notebook, which correctly renders it for any value.

Https://GitHub.com/shaunxcode/a-pattern-in-the-primes

See this animation by Ian Rust showing how the even values of n approach the GCD pattern as the values increase:

https://streamable.com/l7r96

However, for odd values of n, it does not match GCD. So it's not simply a drawing of the GCD pattern.

This is fascinating!

Well, for obvious reasons: when n is odd, and the row R is even (specifically, 2 mod 4, i.e. of the form 4k+2 for some k) and the column C is odd, then even if gcd(R, C) = 1, the set being considered contains only even numbers — note that it starts with R(R-1)N/2+C which will be even as R(R-1)/2 is odd and so is C - so you won't have any primes in it. (That is, you'll have a red cell, even where the gcd pattern has a black one.)

And when n is even, there's also a heuristic argument that there are only finitely many counterexamples; i.e. you should expect to find the pattern from your process exactly match that from just the gcd, beyond a few counterexamples: https://news.ycombinator.com/item?id=17106648

> the even values of n approach the GCD pattern as the values increase

Meaning that the chance of finding a prime in these sequences of N numbers approaches one, after eliminating the cases that make primes impossible (n odd and r=2 mod 4, gcd(r,c) > 1).

Is there any deeper meaning to that, or is it simply that the probability of finding a prime in any sequence of n numbers approaches one as n increases, excluding sequences in which primes are impossible?

Check the observable doc now https://beta.observablehq.com/@montyxcantsin/unwinding-the-u... should be more in line with original intention.

Thanks for an interactive version. Using this, you can check the examples that Anders pointed out in his comment here: https://news.ycombinator.com/item?id=17104624 -- for example, with n=20, see that row 17, column 8 does indeed have a red dot instead of black, which does not match the claimed pattern. (Edit: I wrote more in this comment: https://news.ycombinator.com/item?id=17106193)

Yes, the thing is the claimed pattern IS the one with the dot etc. the mistake we made was seeing how close the GCD triangle version fit and thinking it was the same when in fact it was not. The only claim I am making is that this is an interesting way to transform the ulam spiral into something less chaotic.

Thanks for your comments; it helped me understand exactly what was being claimed, and what the observed pattern is.

For the benefit of others who may be similarly mystified, here's an elaboration. First, in vague terms, there are two things going on here:

1. If you colour a triangular grid according to the gcd of the coordinates, then you get a pretty picture (this is itself interesting IMO), and

2. If you colour a triangular grid according to a particular function involving prime numbers, then the picture will often (NOT ALWAYS!), and in many places (NOT EVERYWHERE!) resemble the pretty picture of (1) above.

Less vaguely, here are precise definitions:

--------------------

Draw a triangle (triangular grid) where row R (for R = 1, 2, 3, ...) has R cells or "columns" (C = 1, 2, 3, ..., R). Suppose we colour the cell at co-ordinates (R, C) to be

- black, if gcd(R, C) = 1 (that is, R and C have no common factors except of course 1), and

- red, if gcd(R, C) > 1 (that is, there is some number > 1 that divides both R and C).

(This is the sequence http://oeis.org/A054521.) Then, the triangle has a pretty and regular pattern, as shown in the post. This is not too hard to prove, but is IMO itself interesting, and a nice discovery for someone playing with numbers and visualizations. So congratulations to the authors for coming up with this.

Call this Drawing 1.

--------------------

Next, fix an even integer N, and for each pair of coordinates (R, C) with 1 ≤ C ≤ R, let S(R, C) be a particular set of N integers, to be defined precisely shortly. (Roughly, in row R, we take RN numbers and assign them to the C cells in a round-robin fashion.)

For example, for N = 10, the first 3 rows have 6 cells so 60 numbers, so in row 4, the numbers 61 to 100 are distributed as follows:

    S(4, 1) = {61, 65, 69, 73, 77, 81, 85, 89, 93, 97}

    S(4, 2) = {62, 66, 70, 74, 78, 82, 86, 90, 94, 98}

    S(4, 3) = {63, 67, 71, 75, 79, 83, 87, 91, 95, 99}

    S(4, 4) = {64, 68, 72, 76, 80, 84, 88, 92, 96, 100}

In general, to define the elements of the set S(R, C), start with (R(R-1)N/2 + C), and increase by R each time, until there are N integers. In Python notation,

    S[(R, C)] = range(R*(R-1)*N/2 + C, R*(R+1)*N/2 + C, R)

Then, colour the cell with coordinates (R, C) with:

- black, if any of the numbers in the set S(R, C) are prime, and - red, if none of the numbers in the set S(R, C) is prime.

Call this Drawing 2 (for a particular value of N).

--------------------

Now, note the following:

- when cell (R, C) in Drawing 1 is red, i.e. when gcd(R, C) > 1, then in Drawing 2, whatever the value of N, all the numbers in the set S(R, C) are divisible by that gcd, so none of them can be prime.

- when cell (R, C) in Drawing 1 is black, i.e. when gcd(R, C) = 1, then in Drawing 2, especially for larger values of N, you have a set of N integers that have no particularly forced reason to be composite, so it's rather likely that at least one of them may be a prime. (This can be made somewhat more precise using standard number-theory heuristics like the Cramer random model, but nothing that reaches the level of proof.)

So Drawing 2, which depends on the primes, is likely to resemble Drawing 1 (red in all the places where Drawing 1 has red), but with occasional additional red dots (where Drawing 1 has black) that break the nice, regular pattern. Some of these counterexamples are listed in this comment: https://news.ycombinator.com/item?id=17104624

(I haven't worked out the details but I think we can prove things like that there will be infinitely many of these counterexamples if we extend the triangle far enough, but also that the ratio (asymptotic density) of these counterexamples will be small. So "the pattern will kind of hold" is about all we can say.)

--------------------

What does all this tell us about primes? Unfortunately, not much it appears. To the extent that there is a nice pattern in the picture, it comes from the regular properties of the gcd function. And if one considers the deviations from the regular pattern as what's interesting, then it tells us things only in a diffuse way: whereas with Ulam's spiral one sees individual primes, here what one sees visually is cases where in a particular set of N numbers none of them happened to be prime.

Still, the pictures are pretty to look at, and that counts for something. :-)

UPDATE - Saturday May 19

The drawing has been updated on the blog post cited above; there was an error in the description of it, this has been clarified and the code has been updated as well

Join the Telegram group to discuss: https://t.me/joinchat/G8AnchIna2q8yn1lGHirkA

Note that Even and Odd Values of N have a very different pattern.

For example try using the values 99 and 99, and then 100 and 100, in this HTML PREVIEW VERSION:

https://htmlpreview.github.io/?https://github.com/acmegeek/p...

CODE TO TRY:

Javascript https://beta.observablehq.com/@montyxcantsin/unwinding-the-u...

Mathematica https://github.com/shaunxcode/a-pattern-in-the-primes

Perl https://www.dropbox.com/s/z5tfub5geyuctex/prime-draw.pl?dl=0

EXPLANATION:

In short, actually there are some curious patterns in this, and they are not simply equivalent to OEIS A054521 (as we, and others, initially thought they were).

For even values of n, they seem to approach the OEIS A054521 sequence as n increases. But for odd values the pattern is different and OEIS A054521 doesn't describe it at all. More discussion of this on the Telegram group...

I wonder why the authors took the time to generate an image of their pattern but refrained from giving the actual DEFINITION. This does not foster constructive discussion of any possible ideas present. As can be seen in dozens of well-meaning comments here, people waste time reversing and guestimating parameters etc.

Looking at the layman letters that my institute gets on a regular basis, I can say, that this is unfortunately a recurring theme with amateur mathematicians: They fail to state their basic definitions and assumptions and seem all to eager to dive right into applications, be it computer graphics, cryptography or finance.

More to the point: This picture seems from a cursory inspection to plot T(k,n) with n=row, k=column from the top left. But why is this interesting?

As far as I could gather from one of the links in the article, the definition seems to be "cell n is black if there is a prime in the interval [Rn , R(n+1)[, for R a natural number". The "pattern" supposedly holds for R rows when displayed in a triangular arrangement, equivalently R^2/2 cells

That's what they say, but the generated image is different (e.g. the first cell of the second row should be red)

That's because amateur mathematicians are artists :)

I think I figured out what the authors were claiming/drawing, and an actual definition: https://news.ycombinator.com/item?id=17106193

I fail to see how this reply is helpful to anyone other than your ego. Perhaps you could state your view in a way that constructively improves their observations.

Awesome! It's the math enthusiast's dream to come up with something new and exciting outside of academia. Recently I discovered what I thought was an interesting chaotic map, but after posting a question about it to Math StackExchange[1] and emailing one or two professors (no response, which is understandable), my obsession waned and I gave up on trying to figure out if it had any significance. Maybe I should keep trying!

[1] https://math.stackexchange.com/questions/2654984/identifying...

Keep going!

Don't forget: There's nothing bad about no-response - People are much more likely to respond on the web and email when you're wrong. ;)

> There's nothing bad about no-response - People are much more likely to respond on the web and email when you're wrong. ;)

There certainly could be something bad about no-response. As someone in academia who gets uninformed musings or crackpot theories from laypeople in his mailbox from time to time, no-response basically means “I know you are wrong, seriously wrong (and, in many crackpot cases, probably mentally ill), but I am not going to just waste my time trying to tell you that.”

As someone else in academia who gets his share of crackpot emails, no response can also mean "oh god, I don't have time to think about this when I have 1000 other emails from my students and colleagues".

(I'm particularly horrid at email.). So I wouldn't take it personally.

It sounds to me like you should have a prewritten response for people who were interested enough to contact you, but who don't know where to start.

I am sceptical of the ability of laymen to even meaningfully understand the field that I am in enough to contribute their own ideas. The amount of literature that would have to be read and assimilated is vast, really achievable only for academics. My prewritten response would only be “Do at least an MA in this field, then we’ll talk”.

What is the field?

I genuinely think that's a good response.

Maybe the majority of recipients won't act, or they'll even take offense, but if somebody in there chose to contact you because they look up to your position, you could easily find in a few years that you challenged somebody to get on the right track with one of those responses. Some people are on the fence and looking for a push.

Obviously it's up to you, but I think it's worth a shot.

Yep - we are not claiming to be mathematicians, we're pattern hunters... this is an open invitation to others with more expertise to chime in and help figure this out... it's possible it is a minor discovery or even not a discovery... or it could be useful or even very useful. We don't know. Please help us explore it!

Either way, hearing a mathematician explain why this is a non-discovery would still be interesting to pretty much anyone who doesn't study primes. Kudos on a cool visualization.

If nothing else, this depiction of prime numbers looks very satisfying for recreational mathematics, much more so than the Ulam spiral. I think students who learn how to generate this pattern will be inspired to learn more about math.

It will be interesting to see if this pattern falls apart when the numbers are reasonably large (like roughly 300 digits+).

”we are not claiming to be mathematicians, we're pattern hunters.”

“Searching for interesting tautologies” or “Hunting for patterns” are good descriptions of what mathematicians do.

Mathematicians do mathematics because they want to be sure that a) they caught a pattern and b) that it is interesting. That’s what’s being discussed here.

Actually there is a pattern. Take a look at the Mathematica code on GitHub.

I think the parent's trying to tell you guys not to sell yourselves short - that what you're doing is exactly what mathematics is.

These visualization techniques have something going for them. I mean, it's amazing work and with new visualizations, people will make new conclusions based thereon much more easily. Analytic continuation ad nauseum. :)

This made me curious, so I wrote a javascript version that renders a larger image of it:

http://www.gibney.de/parallax_primes

Using your frames here's the sequence as N goes from 2 to 90 with a stride of 2: https://streamable.com/l7r96

This is what I wanted to see! Like others have said this looks like it approaches that image as N grows large.

So does the pattern work or not? People are saying it's not plotting primes, but there is clearly a prime check in this code

The original pattern uses prime check (as per this code). OP claimed an exact match with http://oeis.org/A054521 - but this isn't true for many N (see vietjtnguyen's streamable). Perhaps it approaches it as N grows large?

I really liked your approach. I made a few modifications.

http://htmlpreview.github.io/?https://github.com/acmegeek/pr...

I changed it to render with circles vs squares, and have them stack nicely. Also, have the variables more isolated to test. Also, it counts how many primes are within a pack, and assigns the color proportionately. This is still a work in progress.

I made a version of your program in SmallBASIC: https://raw.githubusercontent.com/smallbasic/smallbasic.gith... I found with packSize less than about 20 the shapes vary, then increasing values of packSize results in two alternating sets of shapes.

The way the numbers are picked into the 75-number groups is responsible for pretty symmetry.

If you replace condition isPrime() with simpler checks: "is not divisible by 2" "is not divisible by 2 and 3" .. "... by 2, 3 and 5" .... "... by 2,3,5,7,13,17 and 23" ... you'll get more and more complex images but still symmetrical.

For me the whole thing is subtle hiding of messiness of primes into the strong, pretty, symmetrical shape which obscures the mess and just gets richer and more artistic due to that.

Experiment with the code provided by user no_gravity here: http://www.gibney.de/parallax_primes

By changing the contents of isPrime() function you can see how you get fooled into thinking there's order in primes by mixing messiness of primes into the order of number picking scheme.

I was thinking in the same direction but could not come up with a simple test. Your idea to start with "is not divisible by 2 .. 3 .. 4 .." is great.

It's interesting, that up to 4, it's a perfect pattern:

    function isPrime(n) { return n%2 && n%3 && n%4; }

As soon as you get to 'Not divisible by 5' noise starts to appear:

    function isPrime(n) { return n%2 && n%3 && n%4 && n%5; }

This 'noise' closes some gaps between the pattern and makes it look like runes.

Would any type of noise do this?

Here is how it looks like with some random noise added:

    function isPrime(n) { return n%2 && n%3 && n%4 && (Math.random()>0.95); }

It is not as structured as the version based on primes.

As of now, I'm not sure what to make of it. Maybe there is some other type of simple 'noise' that creates something as complex and logical as the primes. Maybe not.

My take, but correct me if I'm wrong.

Take the relation to the GCD triangle http://oeis.org/A054521

At GCD(n,k)!=1 all numbers are divisible by GCD(n,k) therefore contains no prime

At GCD(n,k)==1 we have https://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arith... - so those series contain infinitely many primes - and seems like they actually contain at least one prime in all the pixels of the first N rows (but this should be explained/proved, if it is always true for any chosen N, or just happen to be true for the N-s tried by the OP)

You're onto it: what you say would still need to be proven is actually not even true, see anderskaseorg's comments, e.g. https://news.ycombinator.com/item?id=17104624.

So their picture is nice, and the gcd!=1 cells are all red, but the gcd=1 cells need not be black. For odd N this fails loads of times (always?), and for even N you quickly find failing cells when you start looking for it (see linked comment).

It wasn't exactly clear to me when I read the article, so here's my explanation:

- take a line of integers, color them black if prime, red otherwise

- hexagonally arrange them in a spiral (similar to Ulam's spiral)

- cut the hexagon into six equilateral triangles

- overlap the triangles (rotate where necessary)

- if any pixels are black, color the whole thing black, if none are black, color it red

- interesting pattern arises

- interesting pattern already exists as per http://oeis.org/A054521

Edit: They may be packing more than 6 numbers into a pixel, looks like 75. Unsure how that would look visually, but you extend the above to use 75 or any other number. Unsure why 75 was chosen, maybe it's the only interesting one?

Just check the numbers listed in one of the referenced articles, it is easy to expand it by induction to numbers greater than 6: https://beta.observablehq.com/@montyxcantsin/unwinding-the-u...

It also helps to understand my other comment about the explanation of the pattern and GCD equivalence...

I wrote some code to replicate this in the console, overlaying A054521 (in colors) onto their triangle (using _ and #) for any N. The output from running

  ./prime-triangle.py 74

is included as x_output_74.png. It's not fancy, but it could save you some time trying to figure out what the actual formulae are.

https://gist.github.com/mortehu/ccca0bafc7a9caa26d6008379057...

Edit: Other than 2, 14, 20, 30, 38, 44, 50, and 74, the two patterns match perfectly for every even N up to at least 600.

Edit 2: Looks like this is related to Linnik's theorem: https://en.wikipedia.org/wiki/Linnik%27s_theorem

From a cryptography standpoint, could this hint at attack vectors for things like discrete log problems? I've only learned of the math behind that myself recently, not sure what implications having a "topographical map of the primes" could have, especially if the pattern is relf-repeating regardless of the size of the primes.

Yes, but only up to a certain point. Larger semiprimes are still a pita to get the primes out of.

My gut sense is that this has something to do with visualizing the sieve of Eratosthenes, and nothing more than that. But I'd be happy to hear otherwise.

Other than the sieve of Eratosthenes being a way to compute a finite list of primes I don't see the relationship here. Could you elaborate?

I think the relationship is that the sieve has a natural shape since it's based on ruling out multiples.

Isn’t the sieve’s eventual shape just the list of prime numbers?

I don't intent to be rude, but what does that even mean? Can you explain?

Mostly the "pattern holding up until n^2". I don't know exactly how the groups-of-N factors into all this. Maybe it's nothing and there's no clear relationship.

How about this, but folded? https://en.m.wikipedia.org/wiki/Eisenstein_prime

A few quick observations:

- The right edge of the triangle is always red (ie, no primes present), because it represents (row number) * (3* (row number)+[1..6])

- Prime numbered rows are always black (except the far right column). I can sort of feel why this is true but can't express it mathematically yet.

It's equivalent to http://oeis.org/A054521

Cell i of row j contains n elements of an arithmetic progression, with common difference of j. If i and j have a GCD != 1, they are not coprime, so they share a factor p, as do all numbers in the sequence, so they cannot be prime

Otherwise it's very likely there's at least one prime

If j is prime every column i is coprime with it, so it's going to be black

> on January 18, 2018, I found a numerical sequence that generated the exact same pattern as Shaun’s pattern

Does this mean that we have a sort of bloom filter-esque test for primality? (ie, it will give you a guaranteed no in O(1) but you'll have to crunch numbers to get the yes?)

If so, are there implications for things that want to know "is it prime?" quickly? Crpytography comes to mind, for instance...

>Does this mean that we have a sort of bloom filter-esque test for primality?

This catches most non-primes ;)

bool maybe_prime(x) { return x % 2 && x % 3 && x % 5 && x % 7; }

This is both, correct, and useless.

Corpos would love it.

And it's infinitely expandable to improve accuracy, at a linear cost of computation!

way ahead of you:

https://en.wikipedia.org/wiki/Primality_test#Probabilistic_t...

We already have quick algorithms that say "is it prime" with certainty. Reducing the required time from O(log^6(n)) to O(1) isn't particularly important from cryptographic point of view.

https://en.wikipedia.org/wiki/Primality_test#Fast_determinis...

Note that log(n) is the length of the prime, so if you are using 2048 bit primes, log⁶(n) is quite large. I don't think anyone actually uses one of the general deterministic primality testing algorithms in cryptographic applications.

It also doesn't reduce the time to O(1). Each of the ranges is of size O(2^(N/2)) for an N bit prime, so it's really not useful at all.

we do not have a fast, certain, algorithm for large numbers. The only thing we have for large numbers is “it’s probably a prime. if it’s of a special form, such as messenne, use this other algorithm that takes like 10 days to confirm whether it is actually a prime. If it’s not a number of a special form for which we have specialized algorithms for, which are still pretty slow for large numbers, well you’re SOL, and if you really want to know for certain if it’s a prime or not you better use one of the clever brute force algorithms that do things like only check odds and only check up until the square root of a probable prime, and are still slow as all get out”

So speed improvements are welcome for academic use. Although this doesn’t look like it’s a game changer.

If by "bloom filter-esque", you mean a probabilistic way of testing whether a number is prime or not, then the answer would yes for a majority of numbers.

How? Just run Fermat's little theorem on multiple values of "a" until you feel comfortable. [1]

Why a majority? There are certain exceptions such as the Carmichael numbers to which we need to use slower algorithms to verify the primality of.

Note that I'm assuming the number of calls to an algorithm is constant since it would be naive to discount the size of the number you're testing.

What are the implications of this result? Off the top of my head I can only think of one: the problem of deciding whether a number is prime or not is in the complexity class P (decidable in polynomial time). [2]

How does this affect cryptography? I would say not by that much.

Why? The "hardness" of some forms of cryptography (asymmetric) isn't from the ability to determine primality of a number. It's from the ability of determining the factors of a number. [3] That problem itself has greater implications for the field.

The question of whether it is possible to do so in polynomial time on a classical computer is actually an open question in CS right now.

Note the emphasis on classical! Amazingly, there exist a polynomial time algorithm to do so on a quantum computer called Shor's algorithm. [4]

[1] https://en.wikipedia.org/wiki/Fermat_primality_test

[2] https://en.wikipedia.org/wiki/AKS_primality_test

[3] https://en.wikipedia.org/wiki/Integer_factorization

[4] https://en.wikipedia.org/wiki/Shor%27s_algorithm

Fast primality testing is of course important from asymmetric crypto. Without it, we couldn't generate big semiprimes.

Shaun is going to update the code with some additions that will hopefully help clear up some of the questions / confusion below. We will also post Mathematica code that is more rigorous. And a new finding. Stay tuned.

What would it look like if instead of a binary coloring, you used a gradient coloring representing the number of primes in each range?

I played around with the cool demo posted by no_gravity: https://news.ycombinator.com/item?id=17104652

replace the source with the one I dropped here and hit Go: https://pastebin.com/aw9nRmeZ

It's actually fun to run the original first and then watch the colors overlay on top of it.

Thank you! I tried doing this with the observablehq version and got really "lost in the Ulam Spiral" of opening and closing functions.

I fiddled with your version and changed the colours to a heatmap-like colour scheme adapted from https://stackoverflow.com/questions/12875486/what-is-the-alg...

This shows the pattern again:https://imgur.com/qR4iGJb

Further fiddling ~shows~ highlights more patterns: https://imgur.com/a/Yjln2RX

This just shows the reduced residues mod n. There are n squares in the nth row from the top. Color the kth square of the nth row black if gcd(k,n)=1, color it red otherwise.

That's what the OEIS sequence they link to says. I hadn't realized that it makes such a beautiful pattern!

How is that?

Isn't it plotting a prime spiral, not GCD?

Obviously prime implies gcd=1, but the "kth" square isn't "k", because it's a spiral counting up from the center.

No, it isn't plotting a prime spiral. Each square in their triangle is a block of 75 numbers. Within the nth row the numbers are sorted by residue mod n.

You're correct. The correspondence just seems to be due to some bound on the prime gap for arithmetic progressions (or perhaps something even more trivial that I'm missing). A cursory search suggests it might be a consequence of Ingham's bound. In any case, it doesn't yield much of interest.

Just run a search on: prime numbers fractal, and many interesting articles (both academic and other) will surface. Search for: zeta function fractal, and you'll find more. I'm no mathematician but it wouldn't surprise me if two very deep fields turn out to be different "manifestations" of some deeper underlying truth, and I then wonder about the possibility of a larger grand unified theory that includes both maths and physics that would have far reaching insights which would go beyond both mathematics and physics, but then I realise that perhaps I've seen too many movies :-)

These runes would serve excellently as a written alphabet for an alien species in fiction (or maybe for modrons or other Lawful creatures in D&D).

I'd like to see the triangle fractal as a starting state for Conways "Game of Life".

As displayed in the image, every other row is offset by half a square from being on a grid.

Maybe if you shifted everything to the left to line it up, but

Who said you couldn't have a hexagonal lattice? Instead of 8, every field has 6 neighbors. The only problem with that really is that you have to expect the 23/3 rule to look differently on that grid. So, no standard glider.

The Javascript code at Observable has been updated to render it correctly for both even and odd values of n now.

This addresses the issues that were pointed out below for the most part.

In short, actually there are some curious patterns in this, and they are not simply equivalent to OEIS A054521 (as we, and others, initially thought they were).

For even values of n, they can be rendered by the GCD sequence, without the primality testing. But for odd values the pattern is different and GCD doesn't describe it.

The Mathematica code on Github lets you experiment with this.

There are some nice versions, and experiments in different ways of coloring or arranging the graph in the Telegram group as well.

Telegram group https://t.me/joinchat/G8AnchIna2q8yn1lGHirkA

Javascript code https://beta.observablehq.com/@montyxcantsin/unwinding-the-u...

Mathematica code: https://github.com/shaunxcode/a-pattern-in-the-primes

Also there are versions in Perl and other languages in the Telegram group.

One correction (already accepted by your co-author @shaunxcode) is that even for even n, your triangle and the one formed by OEIS A054521 are not equivalent. Specifically, here are some values of N, and (row, column) coordinates where the gcd sequence and your sequence differ:

    Counterexample: N=14, (R,C) = (13, 3)
    Counterexample: N=20, (R,C) = (17, 8)
    Counterexample: N=20, (R,C) = (19, 1)
    Counterexample: N=30, (R,C) = (17, 7)
    Counterexample: N=30, (R,C) = (19, 1)
    Counterexample: N=38, (R,C) = (37, 8)
    Counterexample: N=44, (R,C) = (31, 2)
    Counterexample: N=44, (R,C) = (37, 2)
    Counterexample: N=50, (R,C) = (43, 13)
    Counterexample: N=74, (R,C) = (73, 43)

(For n=74, look at the last shown row in the post right now, for N=73, where there's a “stray” red dot: this dot wouldn't be present in the computed-from-gcd sequence.)

There are very few counter-examples though (larger ones seem hard to find); you can see some reasons in my long comment here: https://news.ycombinator.com/item?id=17106193

Here's a rough heuristic calculation for how many counterexamples we should expect. Let's say gcd(R,C)=1, so that there should be no “special reason” to expect everything in the set to be composite. Then, as the set contains N numbers each of size roughly (NR^2/2), each is prime with “probability” 1/log(NR^2/2) — this is the Cramer heuristic — so the probability that all of them are composite is

    (1 - 1/log(NR^2/2))^N < (1 - 1/log(N))^N ≈ e^(-N/log N).

Even with about N^2/2 chances for a counterexample, the expected number of counterexamples (union-bound) is only N^2e^(-N/log N), so for sufficiently large (even) N, the probability of the two drawings differing at any point should be vanishingly small. In fact, by this heuristic, we should expect only finitely many counterexamples, so quite likely the 10 above are the only ones.

Here is animation by Ian Rust that shows how the pattern approaches GCD as the even values of n increase.

https://streamable.com/l7r96

Note that for odd values of n the pattern does not resemble GCD.

Is there are particular reasoning or meaning to each dot being 6 numbers? Is there any significant changes if you pick other numbers per dot, following the same pattern?

Based on the linked explanation here: https://beta.observablehq.com/@montyxcantsin/unwinding-the-u...

I was wondering this myself. I skimmed to the code but can't find any variable for this.

The claim is that it is the same pattern independent of the number of integers per dot.

If the numbers of integers-per-dot was set to 1, the sequence would simply highlight prime numbers as they progress through the pyramid shape since “Parallax Compression” would no longer apply.

The triangle is a hexagon folded onto itself. That's what the "parallax" part is.

Yet they say that this only seems valid for the number of rows equal to the number of integers-per-dot that was used. So, it would indeed highlight with reasonable certainty all the primes in the first row. (I am not a mathematician but I think that is "1" ?)

Because primes exist on a base 6 numeric scale. Where all prime numbers are multiples of 1 and 5.

... I think that statement is only true for the prime number 5. ;)

Base 6:

1,2,3,4,5,6

7,8,9,10,11,12

13,14,15,16,17,18

19,20,21,22,23,24

25,26,27,28,29,30

See a pattern? 2 & 3 are the only prime numbers that are an exception. All others are multiples of 1 and 5.

> All others are multiples of 1 and 5.

Assuming you used “and” when you meant “or”, that's trivially true (and redundant) in that all numbers (irrespective of base, which has no effect on this) are integer multiples of 1.

But no primes other than 5 are integer multiples of 5, in any base.

> Senary may be considered interesting in the study of prime numbers, since all primes other than 2 and 3, when expressed in senary, have 1 or 5 as the final digit.

https://en.wikipedia.org/wiki/Senary

I expressed it poorly, but not as you state, incorrectly.

> I expressed it poorly, but not as you state, incorrectly.

No, really, it is completely incorrect to use “multiple of X in base Y” to mean “have X as the final digit in base Y” (which is equivalent to “is congruent to X modulo Y.”)

13 is not, in base 10 (or anywhere else), a multiple of 3.[0]

That's just not what “multiple” means.

[0] Well, the number denoted by the digits “13” in any base that is itself a multiple of 3—other than base 3 itself where “13” is not a valid number—is a multiple of 3, obviously, but we're talking about the number represented by “13” in base 10.

Having x as a final digit does not make a number a multiple of x. For example, 13 is not a multiple of 3 in base 10.

> Because primes exist on a base 6 numeric scale. Where all prime numbers are multiples of 1 and 5.

What you seem to mean to claim is that primes > 3 are all congruent to either 1 or 5 modulo 6.

UPDATE - Saturday May 19

Join the Telegram group to discuss: https://t.me/joinchat/G8AnchIna2q8yn1lGHirkA

Note that Even and Odd Values of N have a very different pattern. For example try using the values 99 and 99, and then 100 and 100, in this HTML preview version:

https://htmlpreview.github.io/?https://github.com/acmegeek/p...

Here is animation of increasing even values of N approaching GCD: https://streamable.com/l7r96

CODE TO TRY:

Javascript https://beta.observablehq.com/@montyxcantsin/unwinding-the-u....

Mathematica https://github.com/shaunxcode/a-pattern-in-the-primes

Perl https://www.dropbox.com/s/z5tfub5geyuctex/prime-draw.pl?dl=0

EXPLANATION:

In short, actually there are some curious patterns in this, and they are not simply equivalent to OEIS A054521 (as we, and others, initially thought they were).

For even values of n, they can be rendered by the GCD sequence, without the primality testing. But for odd values the pattern is different and GCD doesn't describe it.

Just a heads up, but I would pay money for mugs/t-shirts with the pattern. Of course I can just use to code to make it myself, but it's nice to support people sometimes

We will be happy with "it's a really pretty visualization of the primes" or "it's an improvement on the Ulam Spiral." But if it has more value than that (not sure.. but possibly there is some link in this that might be useful) then that's great too.

I am a little confused. When it says that each square corresponds to n sequential numbers, does it mean that the first square is the first n, and the second square (which is on the second row) is the first n after those, and the third square (also in the second row) has the first n after those, and so on,

Or, do the regions overlap?

I tried to look at the first 4 rows for n=5, but did not see the pattern depicted (each interval had a prime in it).

Am I interpreting what is meant by the blocks incorrectly, or does the pattern not work for small enough n?

For fixed n, a block (x,y) contains the numbers n/2y^2-n/2y + yz + x for all 0 <= z < n.

(n/2)y^2-(n/2)y + yz + x

Making sure I am parsing that correctly:

Is that

((n/2) * y^2) - ((n/2) * y) + (y * z) + x ? (For z ranging from 0 to n)

If so, alright, that makes more sense to me, thanks.

So, n * (y * (y-1)/2) + x + y * z ?

Edit: does HN have an escape character to deal with the asterisks?

Having whitespace after the asterisk or indenting the line by two or more spaces seem to be the only possibilities according to the "Formatting Options"[1]

[1]https://news.ycombinator.com/formatdoc

The Ulam Spiral: https://en.m.wikipedia.org/wiki/Ulam_spiral

Desktop link: https://en.wikipedia.org/wiki/Ulam_spiral

Here is a Dropbox link to the Mathematica code. Thanks to some of the input today we have found that this pattern does not exactly match the gcd triangle - which actually makes this more interesting in a way.

https://www.dropbox.com/s/d2dfwhxdmzkp4y4/a-pattern-in-the-p...

The Telegram link leads to a distribution channel, not a group, so one cannot actually discuss it there. I let the author know through the contact feature on the website, as it might be unintentional.

Edit: The link was changed to a group (at the bottom of the post).

fixed

Maybe it is good to know that within the sequence of all prime numbers there infinitely wide gaps : take (n+1)! +2, (n+1)! +3, ..., (n+1)! + (n+1)

That is a sequence of n consecutive numbers none of which are prime.

Not sure how that would map in this triangle shape yet.

For those that like to mess around with the J programming language, here is what I believe is correct code to generate this parallax compression pattern.

  pack =: 3 : '+./ (r,y+1) $ (npc*y+1) {. (npc*y) }. p' "0
  pc =: 3 : 0
    r =: npc =: y
    c =: +/ 1+i.y
    p =: 1 p: (1+i.c*npc)
    pack i.r
  )

Image of output for numbers-per-cell = 75 here: https://twitter.com/seanstickle/status/997675789264015361

This is awesome. How can we access the code to play around with?

It is in an observable doc so you can fork it etc. https://beta.observablehq.com/@montyxcantsin/unwinding-the-u...

I'm noticing a few neat things about there is left-right reflected symmetry.

Really neat! (I still know I haven't the math chops though. Good place to further my study)

Here is an animation (thanks to Ian Rust) showing how the even values of n approach the GCD pattern (OEIS A054521) as the values increase https://streamable.com/l7r96 however the odd values of n are not equivalent to the GCD pattern.

Is each row the same as if the remainder on division of the cell number by the row number is 0 then red, otherwise black?

I would also like a clearer explanation of how this was generated, maybe with pseudocode, and would also like to see the larger images mentioned in the post.

As it is, the explanation doesn't really make sense to me.

EDIT: Found this lower down: https://beta.observablehq.com/@montyxcantsin/unwinding-the-u...

Is this really capturing a pattern in primes, or a pattern in non-primes (which is totally not surprising).

Whats the diff?

Well, every third number is a non-prime. There's no pattern like that for primes.

“Fooled by randomness.”

The prime numbers are interesting no matter how you slice and dice them!

I wonder if there's a pattern to how many primes per cells-with-primes.

It may turn out to be a pretty small part, but history was made today :) keep it up, stuff like this is awesome! You may not be mathematicians and it may turn out this is nothing hugely new, but even so, the proof of such itself is interesting. keep up the cool work!

This is... Amazing...!

in an Hexagon is a pattern following rules of the fibonacci spiral... but never told anybody about it cause of the effect....

Does this get us closer to being able to generate the Nth prime without factorization / primality test of every number?

No, very far from it

If you throw out the last cell of every row, the pattern is symmetrical.

"It looks like something they found on the ship at Roswell."

The pattern looks nice, but I would have asked some mathematicians before announcing this as something novel.

I think the invitation is extended by sharing the blog post.

Come on, does every cool thing need a stamp of approval by "experts" before publication?

"SQLite looks nice, but I would have double checked with Oracle engineers before announcing this as something novel"

Well, to some extent, yes.

Otherwise you’d end up like the MD who’ve “rediscovered” numerical integration (the trapezoid method) and got it published in the journal of diabetes or whatever.

What's the harm in that ?

So mathematicians should be reviewing papers in the Journal of Diabetes? I think that the Journal of Diabetes should just stay in its lane.

> Otherwise you’d end up like the MD who’ve “rediscovered” numerical integration (the trapezoid method) and got it published in the journal of diabetes or whatever.

This was shocking because calculus is a required subject in American high schools, and this American doctor presumably went to American high school, not because the doctor didn't check in with mathematicians. Frankly, it would be equally shocking if the doctor had asked a mathematician if integration were a thing, because presumably a doctor is an educated member of society.

Nonetheless, even though it's highly embarrassing to the parties involved, with a little bit of self-deprecating humor if I was the doctor, I could tell people at parties that I, along with Newton and Leibnitz have been published on a foundational numerical integration method. ^_^

ha!

Calculus is not a requirement to graduate high school in America. Algebra, sure.

It’s surely a general education requirement in most colleges.

It's a blog post, not a peer-reviewed paper. And the tone certainly sounds to me like an invitation to mathematicians "Hey, we're amateurs who found this cool thing, can you tell us more about it?"

I understand what you mean, but how many great breakthroughs in history were where someone shared the foundation of an idea and then another formalized it?

I think it happens fairly often.

In the more mathematical realm in information theory, turbo codes came out of nowhere by people who were not experts in the field of FEC. Their efficiency far surpassed other methods of the time, to the point that their results in the conference paper were doubted. They didn't have any understanding at the time of why they worked well, they just published results.

Lots of physical phenomena start as simple observations that are later worked into theoretical frameworks. The photoelectric effect comes to mind.

>The pattern looks nice, but I would have asked some mathematicians before announcing this as something novel.

The blog post serves that function.

"The initial goal of John Conway was to define an interesting and unpredictable cell automaton....

"While the definitions before Conway's LIFE were proof-oriented, Conway's construction simply aimed at simplicity without a priori aiming at the proof of automaton being alive." https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life

If this can really map prime numbers to a least a general region, would we be able to break Diffie-hellman key exchange more quickly?

If so this could be a huge blow to security.

But I must say this is amazing that they were able to visualize prime numbers in this way. These guys are geniuses.

I was initially thinking the same, but I don't think that's the case. This will help you find a small range of six potential primes (pick any element on the left edge of the triangle). But you're still required to calculate the factorizations on those six numbers to determine which of them are indeed prime.

No, this won't help with finding primes. As they noted, the pattern for ranges of size k only holds for k lines. So to find a prime of length N (on the order of 2^N), we need to have k=O(2^(N/2)). However, this yields a guarantee that a prime lies in a range of size O(2^(N/2)), which is not particularly useful. We get exponentially better probabilistic results from the prime number theorem.

Reply on news.ycombinator.com