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.
An Interesting Pattern in the Prime Numbers: Parallax Compression
171–180 of 195 posts
Re: An Interesting Pattern in the Prime Numbers: Parallax Compression
#172The 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…
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 “trivi…
See this animation by Ian Rust showing how the even values of n approach the GCD pattern as the values increase:
However, for odd values of n, it does not match GCD. So it's not simply a drawing of the GCD pattern.
Re: An Interesting Pattern in the Prime Numbers: Parallax Compression
#173The 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 t…
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)
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 Re: An Interesting Pattern in the Prime Numbers: Parallax Compression
#174Earlier quoted context omitted.
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 “trivi…
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!
Re: An Interesting Pattern in the Prime Numbers: Parallax Compression
#175The 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 t…
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)…
Here is animation by Ian Rust that shows how the pattern approaches GCD as the even values of n increase.
Note that for odd values of n the pattern does not resemble GCD.
Re: An Interesting Pattern in the Prime Numbers: Parallax Compression
#176Earlier quoted context omitted.
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 il…
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.
Re: An Interesting Pattern in the Prime Numbers: Parallax Compression
#177Earlier quoted context omitted.
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 “trivi…
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.
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
Re: An Interesting Pattern in the Prime Numbers: Parallax Compression
#178> 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...
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
Re: An Interesting Pattern in the Prime Numbers: Parallax Compression
#179Earlier quoted context omitted.
> 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 il…
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”.
Re: An Interesting Pattern in the Prime Numbers: Parallax Compression
#180Earlier quoted context omitted.
”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.