6 ms·
Peculiar pattern found in 'random' prime numbers
- JustSomeNobody 11y agoWhy is random in quotes? Random numbers can have patterns, too.
- jessaustin 11y agoPrime numbers may be generated in deterministic fashion, so in a real sense they can't be random. More discussion at https://news.ycombinator.com/item?id=11282480 https://news.ycombinator.com/item?id=11282480
- theoh 11y agoThis is a technicality, but isn't it the case that if the deterministic algorithm required takes up as much space at the mathematical object itself, the object can be considered random?(according to Gregory Chaitin etc.) https://en.m.wikipedia.org/wiki/Algorithmically_random_sequence https://en.m.wikipedia.org/wiki/Algorithmically_random_seque...
- jessaustin 11y agoThat is one sense of the concept "random", but the primes are trivially disqualified from that (please forgive my coffeescript): $ wc -c primes.coffee 110 primes.coffee $ cat primes.coffee ps=[n=2] until ps.join(',').length>110 n++ ps.push n unless ps.some (p)->not(n%p) console.log ps.join ',' $ coffee primes.coffee | wc -c 115 $ coffee primes.coffee 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151
- radarsat1 11y agoCan they? Genuine question.
- fahadkhan 11y agoYes, it's normally one of the first programs most people tackle when learning a new programming language.
- radarsat1 11y agoWhat is? My question was about whether random numbers can have patterns. I thought a sort of general definition of patterns was the existence of correlation from one state to another, while the definition of randomness was the lack of the same correlation. So I'm wondering how random numbers can have patterns? It's possible my view of "random numbers" and "patterns" is not sufficiently nuanced. I have no idea what your comment means in this context.
- fahadkhan 11y agoSorry I thought the context of your question was "Prime numbers may be generated in deterministic fashion" Of course you know that random numbers will have a distribution. I think this is an example of that. Most people would have expected a uniform distribution here but it isn't the case.
- sp332 11y agoYeah, it depends on the distribution you're sampling from. It's possible (often desirable) to introduce a bias when picking a random number. http://www.boost.org/doc/libs/1_42_0/libs/random/index.html http://www.boost.org/doc/libs/1_42_0/libs/random/index.html
- ipsin 11y agoI think it's in quotes because prime numbers have a probability distribution, but it's (obviously) not a uniform distribution. I think that the article is trying to say that there are more subtle rules around the distribution than just probability density. By "probability density", I mean that the probability of a number around n being prime are about 1/ln(n) -- see the Prime Number Theorem[1] for more -- but of course any given integer is either prime or not. [1] https://en.wikipedia.org/wiki/Prime_number_theorem https://en.wikipedia.org/wiki/Prime_number_theorem
- deleted 11y ago[deleted]
- DoubleMalt 11y agoIt's even worse if you represent the primary numbers in binary notation. Every prime number greater than 10 ends with the digit 1 ;) [edit typos]
- deleted 11y ago[deleted]
- fredley 11y agoWhich leads to the interesting question: if this happens in base 10, but not (trivially) in base 2, what other bases does it happen or not happen in?
- ghurtado 11y agoI think you may have missed the joke.
- allemagne 11y agoHe got the joke, but was also taking it seriously as a phenomenon that could have interesting implications. This finding obviously doesn't hold base 2 (more accurately, isn't an applicable concept), and apparently becomes more pronounced in base 3.
- Phemist 11y agoOnly in bases that are itself prime ;)
- kba 11y agoIt's a joke. The last digit of a binary number is parity (odd or even). Since all primes (except for the number 2 [or 10 in binary]) are odd, the last digit will of always be 1.
- fredley 11y agoYes, I am aware of that (hence 'trivially') thank you!
- CarolineW 11y agoPrimary discussion: https://news.ycombinator.com/item?id=11282480 https://news.ycombinator.com/item?id=11282480
- pc86 11y ago> Primary
- MoonZ 11y agojust tested it against the 10000 first prime numbers in Sublime Text : 2462 prime numbers have a direct neighbour with the same last digit. That's nearly a quarter of them... Edit: by taking into account sequences with 3 identical digits (110 occurrences), it's even more.
- kba 11y agoI was curious, so I wrote a small program to check it: The normal distribution is 1: 24.9940% 3: 25.0128% 7: 25.0100% 9: 24.9832% The distribution following a prime ending in 1: 1: 17.0448% 3: 31.0789% 7: 32.1018% 9: 19.7745% Source: https://gist.github.com/kbadk/71bbb57c9be0d66de156 https://gist.github.com/kbadk/71bbb57c9be0d66de156
- redblacktree 11y agoFTA: > “Every single person we’ve told this ends up writing their own computer program to check it for themselves,” says Kannan Soundararajan, a mathematician at Stanford University in California, who reported the discovery with his colleague Robert Lemke Oliver
- mchahn 11y agoFinding patterns in primes is old news. In the 60's Scientific American had an interesting article about a curious pattern in primes. If you start on a grid and fill in the integers in a spiral there are obvious patterns of connected primes. I had to try it of course, on grid paper by hand up to a couple of hundred.
- tripzilch 11y agoThis is true, they're called Ulam spirals. But the reasons for these patterns appearing are afaik pretty well understood (I forget exactly how but it wasn't hard to get a grasp of why they are there). Though these patterns are pretty noisy still. https://en.wikipedia.org/wiki/Ulam_spiral https://en.wikipedia.org/wiki/Ulam_spiral
- amai 11y agoCould this be related to https://en.wikipedia.org/wiki/Benford%27s_law https://en.wikipedia.org/wiki/Benford%27s_law ?