Re:Prime number patterns
by wfn on Tuesday November 11, 2014 @01:24PM
(#8591304)
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/
Re:Prime number patterns
by robert_tweed on Tuesday November 11, 2014 @01:45PM
(#8591437)
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).
Re:Prime number patterns
by Zolomon on Tuesday November 11, 2014 @01:00PM
(#8591189)
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?
Re:Prime number patterns
by SCHiM on Tuesday November 11, 2014 @02:06PM
(#8591550)
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.
Re:Prime number patterns
by netcraft on Tuesday November 11, 2014 @01:30PM
(#8591338)
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.
Re:Prime number patterns
by escape_goat on Tuesday November 11, 2014 @02:40PM
(#8591722)
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?
Re:Prime number patterns
by readerrrr on Tuesday November 11, 2014 @02:34PM
(#8591688)
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 ).
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)
Re:Prime number patterns
by thomasahle on Tuesday November 11, 2014 @01:52PM
(#8591475)
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.
Re:Prime number patterns
by christophilus on Tuesday November 11, 2014 @01:37PM
(#8591387)
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.
Re:Prime number patterns
by ccvannorman on Tuesday November 11, 2014 @01:23PM
(#8591301)
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.
Re:Prime number patterns
by tikhonj on Tuesday November 11, 2014 @02:21PM
(#8591622)
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.
Re:Prime number patterns
by christophilus on Tuesday November 11, 2014 @03:33PM
(#8591983)
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.
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.
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
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.
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
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
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".
Re:Prime number patterns
by pbsd on Tuesday November 11, 2014 @01:22PM
(#8591286)
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.
Re:Prime number patterns
by CJefferson on Tuesday November 11, 2014 @12:54PM
(#8591153)
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.
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).
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.
The model / metric forms the inference.
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?
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.
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:
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.
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. :-]
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".
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.
https://en.wikipedia.org/wiki/Formula_for_primes#Prime_formu...
n
which also doesn't give a prime for any n, but does generate them all.
In reality you will use a O( (log n)^6 ) algorithm.
11 also works initially as a constant, but it degrades even more quickly than 41.