Prime number patterns | Hacker News Reader

Prime number patterns

chrisdavies.github.io

60 pointschristophilus45 comments

Ulam's spiral is fascinating, too. I've recently discovered this excellent prime number distribution visualization page, which combines the general idea of Ulam's spiral with other things: http://www.dcs.gla.ac.uk/~jhw/spirals/

Woah! That is cool. Thanks for sharing.

This is pretty cool, but seems like an illusion in that it appears to show a pattern where there isn't one. At least not exactly.

Firstly, the formula traces a spiral. If you plot every point, that is. You only plot a point if it's a prime, but it's still always going to trace a spiral!

Still, this only-plotting-primes business leads to new, unexpected patterns emerging. Yet, if you think about it, that's not altogether surprising really. Patterns emerge not so much in where the primes are, as where the primes aren't. Once you go beyond two, anything divisible by two can't be a prime anymore. Same with three. Same for all numbers, because that's what prime means. As a result, you get a pattern. It just so happens that this is what that pattern looks like when you plot it on a spiral rather than a straight line, or in a grid like the OP.

The grid has a similar effect, but the pattern forms vertical lines depending on how many of the prime factors within the set divide evenly by the modulo divisor chosen. Or the divisor +/- 1, which gives rise to diagonals (try adjusting the number up/down by 1 to see this effect).

Thank you, your explanation was a deep insight into those patterns for me.

I always thought these attempts were interesting, because the patterns depend completely upon the visualization implementation and not directly on the pattern of the prime numbers. Is there some way to find prime number patterns without depending on a specific visualization?

i've had the same thought, but I dont think theres anything wrong with the fact that patterns are only noticeable in a certain visualization. A pattern in a decimal number wouldn't be discernible in another base for instance. Its may just be that finding the right visualization might be the way to discover new insights.

See Sociology.

The model / metric forms the inference.

Yes. It's called math.

Edit: I should read more throughly next time, we don't really seem to disagree at all. I thought I read that you said that these patterns were not interesting because they are not 'perfect'.

Original comment:

I've always thought what seems to be the direct opposite of what you do.

In the end every thing we know are incomplete internal models of external systems. E.g. We see a plant, and the image of the plant is stored in our minds, however the image of the plant is not _the_ plant, and may or may not perfectly resemble the plant.

What I'm trying to say is that I think it's pretty pointless to try and find 'perfect' patterns because our own storage system/recognition engine is less than perfect and that it's more fruitful to focus on those domains in which it's easy for us to see patterns, incomplete they may be. Like this very intriguing map of prime patterns.

I don't have a very strong math background, but it seems to me self-evident that the strong vertical striping, for instance, would be a trivial artefact of the modulus rather than anything interesting about the prime numbers themselves.

This leads me to suspect that the rest of the linear striping has a similar explanation which is simply less obvious to me.

This in turn leads me to wonder what it is, exactly, that we're looking at. There will always be patterns visible because there is a deep connection between the ability to form a pattern and not-being-a-prime-number; the latter always implies the former, if not the other way around. So how does one perceive a "subtle" pattern of primes when not-being-a-prime is a property possessed by an overlay of an infinite number of patterns?

Try 4513 for two divergent lines in the first million and almost complete randomness in the 50th million.

That's a prime number and those diagonals were present for all primes I tried. There's probably a name for that.

There are two non-parallel lines in 4513( and I'm not talking about the two sets of parallel lines crossing each other ). Look carefully, and ignore other parallels. I haven't seen any such clear example in other primes( or any other number for that matter ).

I though it was interesting so here is a picture: http://i.imgur.com/KpbfuSz.jpg

Between the purple and blue lines, there are a couple of segments desperately trying to form a line, but failing.

the UI is very nice... where did you find 50 million primes? https://github.com/chrisdavies/primepattern/tree/master/sets

I found them: https://primes.utm.edu/lists/small/millions/ He says: Usually it is faster to run a program on your own computer than to download them.

Here in numpy:

  import numpy as np

  N = 1000000

  n = np.arange(N)+2
  p = []

  while(len(n) > np.sqrt(N)):
      p += [n[0]]
      n = n[np.where(n% p[-1] != 0)]

  print len(p), N/np.log(N)

Hm. I should credit the source... Will put that on my todo list tonight. I transformed these into JSON: https://primes.utm.edu/lists/small/millions/

Yeah. I thought about shrinking the dataset down to 10k primes instead of 1m primes, as the patterns would still hold up, but the load/rendering times would greatly improve.

I appreciate having such a ridiculous number or primes. For certain cryptography problems I need primes around 10^15 or even bigger.

I like this way of using numpy. This resembles the sieve of eratosthenes, so you'd think it was fast.

However `n%p[-1]` isn't fast to do, your inner loop ends up taking nearly linear time. At least linear in the final number of primes, which is larger than `N/logN`. Hence your algorithm runs in `N^(3/2)` whereas eratosthenes is `NloglogN`.

Funny how many versions of this algorithm there are out there.

I noticed it ran a bit slow... it is supposed to be Eratosthenes Sieve

I noticed that comparing sequential mod N (1260, 1261, 1262) you can see the composite lines rotating (which makes sense because the lines follow the 2s, so a mod of a number makes the 2s on each line be 1 or 2 pixels apart the lines appear diagonal.)

This isn't a huge insight, but it does feel like a jumping off point for looking at the patterns -- a sort of lattice or baseline by which to compare the rest of the static.

This app makes me happy. :-]

This is great, although it's obviously hard to draw conclusions. I'd love to see the same sort of visualizations done for 50 million (or however many) random numbers drawn from a distribution that vaguely mimics the primes.

Github source: https://github.com/chrisdavies/primepattern

Assuming the black striped continue forever for "prime mod 1260", does this mean we can quickly weed out non prime numbers?

I was wondering that, myself. The magic number seems to be 210. (1260 is 210 * 6)

You'll also notice that between the black stripes, there is a somewhat denser white stripe. A while back, I calculated the number of primes in those white stripes, and the number was a good bit higher than the over all average.

This just seems to be a variation of the Sieve of Eratosthenes?

Maybe? Haven't heard of it.

2310

Yeah, I just did the same thing. 235711 Unfortunately, it didn't yield anything much more interesting than 1260...

If a pattern were found that allowed primes of arbitrary size to be computed trivially, how would this impact cryptography?

There is such a formula, it is very simple

  n^2+n+41

It doesn't generate sequential primes.

That doesn't really matter, checking if a number is prime can be done in sublinear time complexity. The real problem is factoring large numbers.

It also stops generating primes for n=40. See

https://en.wikipedia.org/wiki/Formula_for_primes#Prime_formu...

It never stops generating primes, but it doesn't give a prime for every n.

Then why is it better than just

which also doesn't give a prime for any n, but does generate them all.

Because it grows exponentially. ( And it is interesting )

In reality you will use a O( (log n)^6 ) algorithm.

I think n² grows quadratically rather than exponentially.

::blush::

Nobody in their right mind uses AKS for primality testing. You use Miller-Rabin with an appropriate constant number of iterations, with complexity (log n)^(2 + o(1)). Or if you want provability, you use some fast variant of ECPP with (log n)^(4 + o(1)) complexity.

This degrades pretty quickly, however. Only 581 of the first 1000 numbers generated by that formula are prime.

11 also works initially as a constant, but it degrades even more quickly than 41.

What we usually do for cryptographic key generation is finding probable primes, which can be found very efficiently.

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

The "openssl prime" command implements a probabilistic primality test that is used inside OpenSSL itself when generating cryptographic keys. You can use that same test to generate probable primes.

https://www.madboa.com/geek/openssl/#prime

Cryptographic keys that you use every day were generated in this way. For instance, the RSA modulus used for the Hacker News web site's HTTPS connection, over which you're reading this post right now, is

222509016795827497794083812831165961379247188961631875655725 097731134045330167937771236763198018821568432886298645744801 658852523304856266339353987508075113064105224649582744138410 510146575813098669176961919590643797014537786653110907775848 477867599116878297173259789693988510658470208808013230939561 018388391347262551003631143383727180887481292553673932217061 748044722300591830836145085835960246785127848933591684137542 631145040567308149003134261726643696478658524574120987942443 039450801995433458255131154946204465423021984216778361565845 434891950126041285345326571981150902538433621893316105896120 78998701064492853

This was generated by someone (probably using "openssl genrsa" or something that indirectly invoked it) using probabilistic primality tests to generate two numbers p and q which were multiplied together to create that modulus.

You might worry that some of the p and q values used for some crypto keys are actually composite (perhaps semiprimes, which actually have two prime factors of their own). That's theoretically possible, but it's incredibly unlikely if you believe that the probability estimates provided by the probabilistic tests are correct, since you could set the probability to be below 1/2⁵⁰⁰ or whatever. The idea is that it's reasonable to use things that are merely probably correct if you can set the probability that they're wrong to be well below the probability that something else in the system has already failed in a worse way (such as a cosmic ray causing a bit flip in the private key parameters that caused them to be composite).

So to summarize, we can already find large primes very quickly (and quickly enough to generate the crpyto keys we want), we're just not sure that those primes are prime, but we're sure enough to use them!

Now there is also the EFF Cooperative Computing Awards (which I run), where if you can find and prove really large primes, like world-record size, you can win cash prizes.

https://www.eff.org/awards/coop

There is a reference in The Curious Incident of the Dog in the Night-Time that may be intended to allude to this and seems to be based on the idea that these large primes would be useful for cryptography. (The protagonist says that you're supposed to send your huge primes to the CIA for a cash reward. Whereas our prize does require that you publish your primes first...)

A lot of people who contact us are a bit confused about the relative sizes of the primes involved. To generate a 2048-bit RSA modulus (the main component of a 2048-bit RSA public key), you need two 1024-bit primes. I just generated such a prime, which was

153177856694500434587513500139248340308937876686459991440575 509272451197058639489829675301493324370461576756305322222646 365872282776312608964726803114536076295854994471249141723824 310821111109394983308072557413772787885400112845231154620813 572050991182667139586732160443583213692240495599715288955030 782261199

This prime is 309 digits long (it is a probable prime, not a proven prime). It's perfectly serviceable for industry-standard cryptographic applications (though not really for use in a private key anymore now that I've published it on Hacker News -- you shouldn't publish your private key parameters on discussion forums).

The primes needed to win our awards are 1000000 digits (already awarded), 10000000 digits (already awarded), 100000000 digits (still available), and 1000000000 digits (still available). It's incredibly hard to do calculations with numbers of these sizes -- for example the last one would occupy 3.32 billion bits of RAM, or over 415 megabytes -- and there's no known cryptographic algorithm that could usefully use them for anything. Of course, primes this big are found with special techniques that are only applicable to numbers of special forms. Those techniques couldn't be used to test the primality of arbitrary numbers, only certain specially-chosen numbers. The current special-form primality testing champion is

https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality...

Edit: Added spaces to break up the large integers above to avoid messing up the formatting of the page. Edit 2: corrected "pseudoprime" to "semiprime".

for 1618 (golden ratio x 1000) there is a straight line right in the middle of the screen. Best visible when scrolling

Same with 1234

This kind of really obvious single line will occur for anything which is 2prime number. 1618 = 2809, so all numbers of the form: n1618 and n1618+809 are composite. There is no other 0<c<1617 where n*1618+c is always prime, so the line is really obvious.

Your division signs got parsed as italic typesetting.

31415

Reply on news.ycombinator.com