Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

An Interesting Pattern in the Prime Numbers: Parallax Compression

novaspivack.com

Post reply on HN
Print view View original

51–60 of 195 posts

Re: An Interesting Pattern in the Prime Numbers: Parallax Compression

#51

Post by Recursing »

Tossrock wrote: post #27

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

Re: An Interesting Pattern in the Prime Numbers: Parallax Compression

#52

Post by yorwba »

enedil wrote: post #45
WaxProlix wrote: post #20

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

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.

Re: An Interesting Pattern in the Prime Numbers: Parallax Compression

#53

Post by szemet »

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)

Re: An Interesting Pattern in the Prime Numbers: Parallax Compression

#54

Post by Senderman »

md224 wrote: post #31

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 tr…

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

Re: An Interesting Pattern in the Prime Numbers: Parallax Compression

#55

Post by chickenstrips »

enedil wrote: post #45
WaxProlix wrote: post #20

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

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

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.

Re: An Interesting Pattern in the Prime Numbers: Parallax Compression

#58

Post by hathawsh »

airesearcher wrote: post #15

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!

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.

Re: An Interesting Pattern in the Prime Numbers: Parallax Compression

#59

Post by tgb »

mathythrowaway wrote: post #57

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!

Re: An Interesting Pattern in the Prime Numbers: Parallax Compression

#60

Post by airesearcher »

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.
Post reply on HN