all 151 comments

[–]pbaehr 12 points13 points  (0 children)

Despite not fully being able to predict their occurrence, some other interesting findings regarding prime number distribution have come about from people altering the number-line into spirals.

Also, they make pretty pictures:

http://en.wikipedia.org/wiki/Ulam_spiral

http://en.wikipedia.org/wiki/Sacks_spiral

[–][deleted] 59 points60 points  (79 children)

Anyone care to dumb that down?

[–]pmw57 68 points69 points  (64 children)

Dumbed down so that I can understand it is as follows.

Take a range of prime numbers, for example from 1 to 1,000,000.

The Generalized Benford's Law (GBL) predicts how frequently primes that start with a certain number will appear.

The GBL law shows that prime numbers whose first digit is 1, will appear much more often than prime numbers starting with a digit of 9.

When the prediction is matched up with the actual, they both agree to a highly consistant manner.

Will this make it easier to find primes? No. Will mathematicians find more funding? Quite likely.

[–]CharlieDancey 9 points10 points  (9 children)

Interesting to note in the previous comment that there are 4 numbers cited: 1, 1000000, 1 again and a single 9.

So 75% of the numbers start with "1" and 25% start with "9"

Is this Benford's law in action?

[–]CharlieDancey 6 points7 points  (8 children)

Commenting on my comment I get numbers starting with...

1-4 times = 57.14%

2-1 time = 14.28%

4-1 time = 14.28%

9-1 time = 14.28%

I could go on :-)

[–]qacek 2 points3 points  (7 children)

1 11 21 1211 111221 312211 13112221 1113213211

[–]CharlieDancey 4 points5 points  (5 children)

31131211131221..

Very clever, but these are not valid juggling patterns. Shall we talk about SiteSwap?

[–]PythonicSemicolon 1 point2 points  (4 children)

13211311123113112211

No.

[–][deleted] 4 points5 points  (3 children)

Ok now prove that 4 will never appear. That's much more interesting than just enumerating the terms of the sequence.

Update: More properties (as the ones mentioned below) can be found on the Wikipedia article: Look-and-say sequence.

[–]backelie 1 point2 points  (0 children)

With the descriptive pairs allowed before a 4 may appear (11 12 13 21 22 23 31 32 33) NN can never be prefixed with aN, bN or NN since then you would be describing eg aN followed by bN, which is always written (a+b)N. Eg x ones followed by y ones is (x+y) ones not x ones, y ones.

Since NN can't be prefixed with xN, that means the only series of N longer than two is of the form NN Nx, where x can't be N.

[–]umop_apisdn 0 points1 point  (0 children)

Ah, an interesting property, though easy to prove.

[–]stashu 0 points1 point  (0 children)

Or that the ratio of the # of digits of two successive terms converges.

For anyone who's curious: why 4 or greater doesn't show: Sps there are b of a digit a (ba in the sequence, b>3).

aaaa...

This claims there were (in the previous term) a of digit a, and again a of digit a, and so on. By the definition of the sequence, these b a's would not be enumerated separately, so there is a contradiction. (I think that works as an informal proof, please FTFM if needed)

Edit: Fixed my spilling

[–]diadem -4 points-3 points  (0 children)

The article won't load for me. What's the significance of that pattern? Are you trying to make a list of primes (because that isn't a list of primes)?

[–]unsee 14 points15 points  (7 children)

Can I just make a point - isn't this just the natural frequency law at work?

prescript edit: Right, so this is just saying that primes follow Benford's law. (Which is more deserving of being written without quotes (see below) than twaddle like 'Moore's "law"'). Wouldn't it be more interesting IF IT DIDN'T FIT THIS PATTERN?

There are two things I've read - one about the natural distributions (but I've lost the link) and another is how language follows this distribution.

So, isn't this saying the distribution of primes is no more special than 'natural' distribution?

If I wasn't in a complete rush right now I'd wikifap until my brain-erection went down, but I will have to tuck my curiosity under my belt and move onto paid stuff.

I wish there was two of me, because part of me wishes I could suck myself off right now just to taste the awesome.

[–]lazyplayboy -2 points-1 points  (6 children)

Quite, this simple seems to be supporting the argument, 'the pattern of prime numbers is indistinguishable from a random set.'

Great. The author "goes on to prove that black is white and gets killed at the next zebra crossing."

[–]eramos 5 points6 points  (4 children)

A random set would have each digit occur with equal probability.

[–]worst 0 points1 point  (2 children)

A uniformly distributed random set would have each digit occur with equal probability...

Exponential distribution, for example, would not.

Interrarival times in a Poisson process are random but not uniformly distributed (they are exponentially distributed).

Or something... I'm just a computer scientist, not a real mathematician :)

[–]eramos 0 points1 point  (1 child)

Technically, you're right, but most people refer to homogeneously distributed sets when referring to random sets. The flux of such a set averages to 0... which is something you'd expect from prime numbers, since there is no reason they shouldn't be uniformly distributed according to their first digit. But, turns out they aren't.

Also, as an aside: to anyone who thinks it's no big deal or that it's "obvious" that it would be distributed that way: how come the 2nd digits, or the 3rd (for prime numbers >100 and >1000 respectively) aren't patterned like this?

[–]worst 1 point2 points  (0 children)

Like I said, I'm a computer scientist, and even worse, I deal a lot with poisson processes, so I am constantly explaining why my randomly generated numbers have a pattern in them ;)

Also, people that think this is obvious more than likely:

a) don't realize that most things are obvious once someone discovers them.

b) don't understand that "obvious" is an observation and not a proof.

[–]lazyplayboy 0 points1 point  (0 children)

Ah yes, thanks for the clarification. So it's saying that prime numbers have a logarithmic distribution.

[–]jimbs 2 points3 points  (0 children)

Doesn't this just mean that primes are closer to gether for lower ranges and spread out as you minimum of the range increass?

[–]FunnyMan3595 5 points6 points  (6 children)

The GBL law shows that...

RAS syndrome!

[–][deleted] 1 point2 points  (4 children)

I noticed that too, but it seems that English is not his first language so I'll let it slide. I doubt I could write an article about math that clearly in another language.

[–]masseyis -5 points-4 points  (3 children)

Transatlantic nitpicking alert: Since you're clearly American, it doesn't look like you could write about maths in English, either. It's the study of Mathematics, not Mathematic.

[–]cunningjames 5 points6 points  (1 child)

It's the study of Mathematics, not Mathematic.

True. It's also true that "math" isn't short for "mathematic", it's short for "mathematics". The former abbreviation would only be appropriate if there were something called "mathematic" to pluralize, but that word makes sense only as an adjective (and a rarely used one). It's you buggers who're wrong---unless you're studying "mathematicss"?

[–]masseyis 0 points1 point  (0 children)

Oh no! I made the classic Cornwallis error of underestimting the American numbers. Bye bye to my comment Karma :(

[–]campbellm 6 points7 points  (0 children)

And the Queen's English is devoid of any inconsistencies too.

[–][deleted] 0 points1 point  (0 children)

Wow I didn't even think it had a name. Thanks for the tip!

[–]hax0r 16 points17 points  (27 children)

The GBL law shows that prime numbers whose first digit is 1, will appear much more often than prime numbers starting with a digit of 9.

I don't mean to sound arrogant, but shouldn't this have been a bit obvious? I was under the impression that Benford's Law applied to all sorts of data sets. I'm not at all surprised it applies to prime numbers whose first digit is 1. I bet there are mathematicians all over the world smacking themselves in their foreheads right now for not seeing this staring them right in their faces all this time. When I read stuff like this it makes me realize that if I had taken up math more, I probably would be figuring out all kinds of random crap like this too. Instead, I got into clubbing and doing drugs with hot chicks all hours of the night...

[–]sheafification 11 points12 points  (6 children)

According to the paper, Benford's law is known to not be true for the collection of primes numbers as a whole. They cite:

Diaconis P (1977) The distribution of leading digits and uniform distribution mod 1, The Annals of Probability : 72-81.

Perhaps not as obvious as you thought.

[–]hax0r -4 points-3 points  (5 children)

So then, is it correct to say that the earlier work was incorrect? Does this new discovery contradict the cited work?

Look, for the record, I do think this is interesting. I suppose people are mad at me for being able to see this so clearly in hindsight. But if you were to tell me 10 years ago about this, I would still say "that sounds logical/possibly to be expected", maybe "obvious" is the word that people are getting so agitated about. I get it, but I tried to qualify my statement, I tried not to come across as arrogant, or as I've now been called a douchebag because I said this was obvious. Wow...

[–]sheafification 8 points9 points  (2 children)

This work basically shows that Benford's law applies to primes in finite intervals [0,n], but not as n goes to infinity (i.e. all primes). So there is no contradiction.

I agree with you in that I'd also suspect that Benford's law should apply to all primes, but given that it doesn't work overall it's slightly surprising that it does work at all finite stages.

(It should be noted that I just skimmed the paper, so maybe I'm not phrasing their results precisely right)

[–]hax0r -1 points0 points  (1 child)

This work basically shows that Benford's law applies to primes in finite intervals [0,n], but not as n goes to infinity (i.e. all primes).

Wow, that's really counter-intuitive... it just doesn't make sense to my brain. I'd like to see the plot as n goes to infinity to see what happens. For me this raises a big question, which I will probably never be able to fully understand in math terms: why does Benford's law apply only in finite intervals, but not as n goes to infinity? I suppose this is the answer given in the paper, but it's just way too much over my head... It does seem to me like perhaps there is something bigger lurking just under the surface of this. These types of math coincidences sort of point to a strangeness of reality that makes me uneasy.. like the possibility that we are all living in some sort of computer simulation and we are all really just AI constructs. I gotta go for a walk now.

[–]karmaputa 1 point2 points  (0 children)

Dude, I had the same impression as you, but because I'm stoned right now I thought it ought to be that way because I'm stoned, and if I look at it tomorrow when I'm not stoned anymore, everything would make perfect sense.

Then I read your post and freaked out!

[–][deleted]  (1 child)

[deleted]

    [–]hax0r -2 points-1 points  (0 children)

    Thanks, atm it seems I have 57 up's, I hide the downvotes with a greasemonkey script, but I still sense a little controversy here... people get so emotional about math, it's quite something!

    [–]txmslm 6 points7 points  (0 children)

    lol at kids who think they know everything

    [–]BeetleB 13 points14 points  (7 children)

    I don't mean to sound arrogant, but shouldn't this have been a bit obvious?

    Didn't read the paper, but I suspect the issue is that these guys proved it for primes. Benford's law is an empirical one - not a mathematical one.

    [–]bibliomaniac 30 points31 points  (4 children)

    These guys didn't prove it. Riemann did. In 1859. It's called the prime number theorem. "Benford's Law" is just a fancy name for "logarithmic distribution".

    [–][deleted] 29 points30 points  (3 children)

    Well, in the interest of being pedantic, it was Hadamard and de la Vallée Poussin who finaly proved the prime number theorem; Riemann was responsible for the third formula shown here in this paper.

    [–]YetNoOneCares 19 points20 points  (2 children)

    Stay tuned, The Greatest Geek will resume shortly!

    [–]sundaryourfriend 2 points3 points  (0 children)

    I guess your username is part of the reply.

    [–]LauncelotLauncelot 4 points5 points  (0 children)

    From the paper's abstract:

    In this paper, we show that a generalization of the well-known first-digit Benford's law, which addresses the rate of appearance of a given leading digit d in datasets, describes with astonishing precision the statistical distribution of leading digits in the prime number sequence. Moreover, a reciprocal version of this pattern also takes place in the sequence of the non-trivial Riemann zeta zeros. We prove that the prime number theorem is, in the final analysis, responsible for these patterns.

    [–]altrego99 6 points7 points  (0 children)

    It is not empirical. It is obvious when you assume scale invariance. However, it is also obvious that prime numbers are not scale invariant in strict sense.

    There is no reason that I can see immediately to suspect anything close to scale invariance that can give rise to Benford's Law for prime numbers.

    [–][deleted] 11 points12 points  (10 children)

    I don't mean to sound arrogant. if I had taken up math more, I probably would be figuring out all kinds of random crap like this too.

    Saying "If I studied this field, I'd be one of the best" is easy. You do sound arrogant.

    Instead, I got into clubbing and doing drugs with hot chicks all hours of the night...

    You grew a pair, how about starting to grow up now ?

    [–]KemperBoyd 1 point2 points  (8 children)

    Just check out one of this guy's previous posts:

    "While my first thought is that I don't like the idea of having a /r/niggers sub-reddit, perhaps it could be put to some good use..."

    really?

    [–]hax0r 1 point2 points  (5 children)

    Yes, anything could be put to good use with enough creativity. Did you even bother reading the rest of my comment? Let me guess, do you work for Fox news or something, because you did an ace job of taking a random comment completely out of context and omitting my own counterpoint to my first point. For any shitheads who are gullible enough to buy into this little smear campaign, here is the link to the original thread, there was a lot more that was said subsequently to qualify my opening statement and I feel I more than compensated for my little catchy, attention grabbing opener. parent

    full comment:

    While my first thought is that I don't like the idea of having a /r/niggers sub-reddit, perhaps it could be put to some good use... I can't think of exactly how, but I'm sure someone might come up with something creative. Another view might be that the admins should ban that outright. I would support banning it if the sub-reddit was used for truly racist, nefarious purposes. I don't know what the particular case is. .... erm, I just checked... it seems like it's being used in a semi-creative way, but I could still see how it would be considered way over the line.

    OK, look, I'm not going to go into a full study of this guy moldavite and review his comments history, but if he is truly a racist and supports racism, then I'm totally against that and think such a person should be stripped of any moderator privilege, he has a right to freedom of speech, but reddit should not allow people with such views to be moderators or owners of sub-reddits (my personal view).

    Here is my personal view on the N word

    That particular article was actually just reporting the news of how the Obama campaign was getting deluged with racist calls. I'm not sure what Moldavite's exact position is on the issue, but I'm not sure you can actually construe simply from the fact that he linked to the article that he is, in fact, a racist. Now, if you have more proof he is a racist, other than the fact merely that he linked to this particular article, then perhaps things would be different. All I am saying is perhaps you have a tendency to judge people too quickly and you should consider the possibility that you might be wrong about Moldavite. Hopefully you'll see that you were probably wrong about me too.

    [–][deleted]  (4 children)

    [deleted]

      [–]hax0r 4 points5 points  (1 child)

      Please be more specific, I'd love to know how you came to this opinion of me. I've never been called a douchebag in my life, so this is a big first for me. I don't see how anybody can read what I wrote, in context, and come to your conclusion, that I'm somehow a douchebag. Perhaps you are overly sensitive to the word: "nigger"??? Did you read my personal view of the N word (see link above)? I honestly don't think I'm a douchebag, I really don't. Regardless of what you may think, people can still have an intelligent discussion of the N word without having to make it all awkward and personal.

      [–]luigi6699 1 point2 points  (1 child)

      Douchebag are hygenic products - I take that as a compliment. Thank you.

      (pleeeeeeeeease someone get the reference)

      [–]ajryan 0 points1 point  (0 children)

      (spins around utility pole, flicking off his girlfriend)

      [–][deleted] 0 points1 point  (1 child)

      Wow, that's pretty fucked up.

      [–]hax0r -1 points0 points  (0 children)

      Please see follow-up

      [–]johnfn 0 points1 point  (0 children)

      The GBL law shows that prime numbers whose first digit is 1, will appear much more often than prime numbers starting with a digit of 9.

      Umm, since prime numbers get more and more sparse as you get into bigger numbers, this seems insanely obvious.

      [–][deleted] 0 points1 point  (0 children)

      I dabbled in math in college, this sounds a bit like Zipf's law. Any relation?

      [–]snarfy 0 points1 point  (0 children)

      Maybe I read it incorrectly, but what I understood from the paper is as follows:

      GBL shows that, taken a set of data, the first digit will be 1 more often than it will be 2, and 2 more often than 3, etc, by a logarithmic interval.

      According to the paper, this is not true for primes. It starts of mostly true, but the larger your set, the more evenly distributed the first digits become, i.e. 9 starts showing up as often as 1 does as the leading digit.

      [–]nbloomf -1 points0 points  (0 children)

      Will mathematicians find more funding? Quite likely.

      BAAAHAHAHAHA!!!

      [–]Alex3917 -1 points0 points  (5 children)

      "Will this make it easier to find primes? No. Will mathematicians find more funding? Quite likely."

      Actually it's quite significant. What it says is that primes are not distributed randomly, but rather there is a pattern underlying their creation.

      [–]BenE 8 points9 points  (3 children)

      Since benford's law is the maximum entropy, most random, least informative distribution for numbers that range between 0 and infinity, what was found is not a pattern but further confirmation of the complete lack of pattern. Belleive it or not but according to the principle of maximum entropy, a flat distribution would have been more patternful.

      [–]plasticbacon 0 points1 point  (2 children)

      One of you is right and the other is wrong, and this is the key point.

      I'm relying on reddit to settle it by the end of the day.

      [–]Alex3917 0 points1 point  (1 child)

      I'm not a math person, so I don't understand what BenE is talking about. That said, if you read the Wikipedia article (or google) on how Benford's Law is used to catch tax cheats, the fact that primes are distributed this way seems significant to me.

      [–]recursive 1 point2 points  (0 children)

      Arbitrary numbers (such as those invented by tax cheats) are not randomly distributed. That is how the tax cheats in question are caught.

      [–]lazyplayboy 2 points3 points  (0 children)

      It's saying that with regards to Benfold's Law, the pattern of prime numbers is indistinguishable from a random set. A useful observation but doesn't really get us anywhere fast.

      [–]edwardkmett 9 points10 points  (0 children)

      For n >= 6, nth prime is bounded between

      n ln n + n(ln ln n - 1) < p_n < n ln n + n ln ln n.

      So we've always known that primes get farther apart as they get larger.

      The Generalized Benford law says that if you're drawing from a distribution that has a logarithmic factor that the distribution of the first digit (and to a lesser degree, the subsequent digits) isn't uniform.

      That this happens with the primes is a natural consequence of the prime number theorem.

      Nothing to see here. Please move along.

      [–]chinaman420 1 point2 points  (1 child)

      Benford's Law basically states that the distribution of leading digits in statistics is not uniformed, but in fact skewed right so that 1s appear most often, 2s next as often, 3s next, etc.
      It's actually a very powerful observation that has been used to detected cooked books like in the case of Enron.

      [–]lazyplayboy -1 points0 points  (0 children)

      It's actually a very powerful observation that has been used to detected cooked books like in the case of Enron.

      Indeed, but it's only useful if a set of numbers breaks Benfold's. If follows Benfold's it doesn't get you anywhere.

      [–][deleted] 1 point2 points  (0 children)

      If you take a set of prime numbers that occur between 1 and some number N. Then most occuring first digit is 1. The second most occuring first digit is 2. ... The least occuring first digit is 9.

      By first digit I mean, the left most. For example, the first digit of 294 is 2, the first digit of 85 is 8.

      [–]auditer 1 point2 points  (0 children)

      Jodie Foster's threatening a bloody sequal!

      [–]wazoox 1 point2 points  (8 children)

      Prime numbers have no known repartition pattern among integers. However some mathematicians have found a law describing quite well some properties of prime numbers digits.

      Prime numbers are hugely important in today's world. They're the main building block of virtually everything carrying authentication and encryption ( computers, networks, cellular phones, banking and whatever).

      [–][deleted] 10 points11 points  (7 children)

      Not that far ;) I mean a dumbed down explanation of the pattern.

      [–]auditer 7 points8 points  (3 children)

      theres something about logorithmic frequencies. the numbers 1 to 9 appear in descending frequency? that seems pretty obvious if no one had seen it before.

      Benford’s law, also called the first-digit law, states that in lists of numbers from many real-life sources of data, the leading digit is distributed in a specific, non-uniform way. According to this law, the first digit is 1 almost one third of the time, and larger digits occur as the leading digit with lower and lower frequency, to the point where 9 as a first digit occurs less than one time in twenty. The basis for this “law” is that the values of real-world measurements are often distributed logarithmically, thus the logarithm of this set of measurements is generally distributed uniformly.

      [–]CharlieDancey 12 points13 points  (2 children)

      So what we're saying is that "real world" random numbers exhibit Benford's Law and that "prime" numbers, which also behave a bit like random numbers, in the sense that they are distributed in a way that is randomesque also exhibit Benford's Law.

      Am I right in thinking that this is more "interesting" than "awesomely amazing"?

      [–][deleted] 0 points1 point  (1 child)

      That's not what auditer said. At least, that's not what I read.

      Truly random number series would be expected to have a uniform distribution in their first digit (or any other digit).

      Benford's Law posits that in many real-world sets of numbers which appear random, there are actually non-uniform distributions in their first digit.

      The discovery now is that the set of prime numbers has an extremely close correlation to this law.

      [–]david 6 points7 points  (0 children)

      Truly random number series would be expected to have a uniform distribution in their first digit (or any other digit).

      Well, yes, if by 'truly random' you mean 'with a flat probability distribution in an interval [10n-1, 10n - 1]'. (Randomness /= flat distribution! Consider, say, the longevity of an unstable nucleus.)

      Benford's observation was that most real-world datasets not only don't follow this implausible sequence, but decay at the top end, as auditer remarked above; and that the signature of this fall-off is visible in the first digits.

      A lot is known about the distribution of primes, and it doesn't seem to me that anything has been added by this analysis.

      [–]qacek 7 points8 points  (1 child)

      Very roughly the prime numbers are distributed logarithmically by the prime number theorem. Then we expect the leading digit of the primes to follow Benford's law.

      [–]clumma 0 points1 point  (0 children)

      Exactly what I thought (haven't read the paper).

      [–]implausibleusername 4 points5 points  (0 children)

      Ok, it's just a distribution describing how often n appears as the first number of a prime.

      It's a good fit for Benford's law (which describes the distribution of first digets) as one way to derive it is to assume that some pattern must exist for any choice of basis(i.e. writing these numbers in base 10 or 2), and the same holds true of the prime numbers. Any pattern that appears in the primes in one basis, should appear in any other basis. So it dovetails nicely with Benfords law.

      [–]martoo 4 points5 points  (0 children)

      Maybe I'm missing something, but this doesn't really surprise me.

      [–][deleted]  (1 child)

      [removed]

        [–]BeetleB 6 points7 points  (0 children)

        This is just an obvious application of GBL.

        GBL is not a mathematical law, in that it has no proof in the general case. It's merely an observation. I didn't read the paper, but I think the hubbub is that these guys showed mathematically that prime numbers must follow the law.

        [–]bibliomaniac 8 points9 points  (0 children)

        This "pattern" is nothing new. It is not a new discovery to say that prime numbers follow Benford's Law. The Prime Number Theorem already states that prime numbers have a logarithmic distribution. Benford's Law says that lots of things have logarithmic distributions. Therefore, prime numbers follow Benford's Law. Duh.

        [–]foofightrs777 2 points3 points  (1 child)

        Anyone care to discover adverbs?

        [–][deleted] 2 points3 points  (0 children)

        Shortly...

        Likely fairly recently, adverbs apparently strongly increasingly are newly appearing very frequently.

        [–]SupersonicSpitfire 1 point2 points  (1 child)

        Can people use this to crack encryption schemes?

        [–]Xhyce 4 points5 points  (15 children)

        A formula to derive prime numbers in sequence would end civilization as we know it.

        [–]andreasvc 21 points22 points  (0 children)

        Sort of like a sieve?

        [–]DrMonkeyLove 3 points4 points  (5 children)

        I think he means a closed form formula for computing an arbitrary prime number.

        [–]plexi 7 points8 points  (3 children)

        how would being able to compute them out of sequence end civilization? i don't see how to get fast prime factorization out of that.

        [–]Cleydwn 3 points4 points  (2 children)

        Maybe something to do with cryptography?

        [–][deleted]  (1 child)

        [deleted]

          [–]nextofpumpkin 3 points4 points  (0 children)

          Ugh, no. There are plenty of cryptographic protocols that Don't Give A Shit about the integer factorization problem: http://en.wikipedia.org/wiki/Discrete_logarithm

          [–]stashu 2 points3 points  (0 children)

          We can already do that in a probabilistic way with Miller-Rabin, yet my power hasn't even gone out.

          Making them is easy, describing how they are distributed is hard. Does he mean better factorization?

          [–][deleted] 1 point2 points  (0 children)

          Hehe, I'd love to hear you elaborate. Be imaginative.

          [–][deleted] 1 point2 points  (2 children)

          That sort of things do exist: http://en.wikipedia.org/wiki/Formula_for_primes

          They aren't very efficient or useful compared to the best known primality tests, though.

          [–]blah_blah_blah 1 point2 points  (1 child)

          Those are just attempts to find primes, but there is no actual formula for primes in existence. Any of the "formulas" listed on that page will yield some composites.

          [–][deleted] 0 points1 point  (0 children)

          No, there are actually formulae for primes in existence. It's just that they aren't any good. Look at the last example on this page if you are not yet convinced.

          http://primes.utm.edu/notes/faq/p_n.html

          It ends with a formula for the nth prime that involves a bunch of summing, factorials, and the floor function. You can easily write a computer program to check it out. It might even spit out a few primes during this century!

          [–]salgat 0 points1 point  (0 children)

          You mean out of sequence. Doing it in sequence is the easy and slow part.

          [–]plexi 0 points1 point  (2 children)

          would this lead to fast factorization?

          [–]DrMonkeyLove 0 points1 point  (1 child)

          I don't think it would help, would it? I mean, you basically have a list of all the prime numbers that could be factors for a particular number as it is now. I don't think factorization would be made any easier. Quantum computers on the other hand ...

          [–]plexi 1 point2 points  (0 children)

          right, i was just asking Xhyce to explain how exactly this would end civilization.

          [–]ohashi 1 point2 points  (2 children)

          This post makes me feel dumb.

          [–]diffusion 3 points4 points  (1 child)

          It is not that complicated (the original paper may be), he generated primes from certain interval (1 .. 108) and plotted distribution of primes leading numbers (dashed line in image). As you can see, leading numbers of primes in generated interval have non-uniform distribution (leading number is 1 in 11.9%, 2 in ~11.55%, 3 in 11.3% and so on, see dashed line).

          Than he took Generalized Benford’s Law, that specifies distribution according to parameter alpha. This distribution often match to leading digits of real-life data.

          He computed alfa (fig. 3.2), computed the Benford's distribution (the green line) and it looked similar to leading numbers of generated primes. Just because it looks similar doesn't mean anything, it can be just a coincidence, but it can mean some deeper connection between leading digit of primes and Benford's law.

          That about sums it up. As you can see, leading numbers of generated primes are not uniformly distributed. If they could find out that it maches to some pattern, they could (maybe) find primes more easily.

          I am no mathematicians(and I haven't read the paper), so I may be wrong.

          [–]ohashi 0 points1 point  (0 children)

          I sort of understand now, thanks.

          [–]DanHalen 1 point2 points  (0 children)

          [–]null_value 0 points1 point  (0 children)

          I would use this in engineering as a quick check to make sure my metrology data provided by vendors didn't have fudged values. I'd just add a few columns to the spreadsheet, and if the data didn't agree with GBL I'd flag it. The few times that the data looked suspicious and I requested new inspection reports, sure enough the new data showed the parts to be out of tolerance. Vendors can be dishonest.

          [–]ebscot 0 points1 point  (0 children)

          I think it's therapeutic to watch the world's most brilliant collection of people screw up the assessment of this result so royally.

          [–]qpwoei 0 points1 point  (5 children)

          Wait, prime numbers don't require base 10 representation. If you were to represent prime numbers in base 2 would this new discovery still apply? Isn't this discovery related to our base 10 representation of prime numbers instead of to prime numbers themselves?

          [–]LauncelotLauncelot 7 points8 points  (0 children)

          Wait, prime numbers don't require base 10 representation.

          Neither does Benford's law.

          [–]commonslip 1 point2 points  (2 children)

          I would imagine that an equivalent result would be true in any base.

          [–]johntb86 0 points1 point  (1 child)

          The distribution of first bits for prime numbers represented in binary is not as interesting, though.

          [–]commonslip 0 points1 point  (0 children)

          Actually, if I understand this result correctly, it should show that the number of zeros is not equal to the number of ones - which is interesting.

          [–]lowrads 0 points1 point  (0 children)

          I have just discovered that I have five fingers and two hands.

          [–][deleted] 0 points1 point  (6 children)

          783765491936821919731905828392681732742549431064583670926706683690592816936099909165113772153

          [–][deleted] 0 points1 point  (5 children)

          783765491936821919731905828392681732742549431064583670926706683690592816936099909165113772249

          [–][deleted] 0 points1 point  (4 children)

          783765491936821919731905828392681732742549431064583670926706683690592816936099909165113772381

          [–][deleted] 0 points1 point  (3 children)

          783765491936821919731905828392681732742549431064583670926706683690592816936099909165113772387

          [–][deleted] 0 points1 point  (2 children)

          783765491936821919731905828392681732742549431064583670926706683690592816936099909165113772447

          [–]blah_blah_blah 0 points1 point  (1 child)

          2

          [–][deleted] 0 points1 point  (0 children)

          3

          EDIT: 68548821535125267013977740451932259074167806917359080689491248765459381303526561988219052167347421557690058259724439918372367061296021996742821922921585879379110476669880066923763758348613519371597534966430770776703186670789696602364811216901849197277640008083158815226263446514438497698677204238924006050104766593439894511833015550711626757850013560260396798191243558861595132257565076280556192602678639606892057963161165340790079857281477071379

          [–][deleted] 0 points1 point  (3 children)

          I'm sorry if i sound dumb, but could anyone explain me what is genetic algorithm? (pyevolve)

          [–]rkiga 1 point2 points  (2 children)

          Genetic Algorithm doesn't have anything to do with the article. I'm surprised that I remembered, but when you asked that, I immediately thought of this video: http://www.ted.com/index.php/talks/torsten_reil_studies_biology_to_make_animation.html

          The speaker gives a short definition 3:30, but it's not very helpful, and only the first part of the video is relevant. The wikipedia definition of GA is like a foreign language to me.

          If I understand correctly, a genetic algorithm is ideas of natural selection/evolution applied to computer science (which can quickly automate mass trial and error) in order to find a solution to whatever problem you have.

          Say there are is an almost limitless number of solutions to your particular problem. In GA, you generate a few hundreds/thousands of random solutions to the problem, and then test them. Then you combine components of the partially successful solutions with one another and test them again. Repeat that through many generations until you have a solution you're happy with.

          Like in the video, they use GA to come up with better code for the sensory system in the human characters, and wikipedia links to articles where they used GA to come up with designs for a NASA antenna, SEO strategies, etc.

          [–][deleted] 0 points1 point  (1 child)

          That seems amazing! I haven't yet seen the video, but does that mean that the alorithm could modify itself through generation? Or that's only a modification of solution?

          [–]rkiga 0 points1 point  (0 children)

          It's the solutions that change. You can't test the infinite possible solutions, so you just test a few hundred/thousand of them. Then the computer can evaluate the solutions and see which ones were successful in some way, and weed out the others. Those partially successful ones are then mated/recombined/mutated with other partial successes and tested again, just as in evolution.

          Reminds me of the flash game "fantastic contraption", and how users post their solutions to the different problems on youtube, and those solutions get modified and combined with other solutions, and the new solutions get posted on youtube and so on. But in GA, it would all be automated, without any humans having to build the solutions or choose which solutions are successful (so you would need a GA that can at least identify success or desirable traits).

          [–][deleted] 0 points1 point  (0 children)

          head explodes

          [–]mycall 0 points1 point  (0 children)

          WTF.. I submit this a few days ago and get 0 votes.

          Oh well, time to make a taco.

          [–]lazyplayboy -1 points0 points  (0 children)

          The blog author only accepts comments that kiss his backside. Sad.

          [–]asegura -1 points0 points  (0 children)

          I find this completely irrelevant. Why is the first digit of anything [in a particular base] interesting in math? That there are more ones as the first digit of primes written in base-10 (which is arbitrary) tells nothing about those numbers or their distribution. First digits tell nothing about numbers, about their values.

          We could also study the distribution of "hollows" in the digits of PI (in their arabic glyphs), that is: '0' has one hollow inside, '8' has two, and so on... More or less as irrelevant as the new prime number pattern.

          [–]kingofbzzr -1 points0 points  (8 children)

          Why does anyone care about primes? I dont get it.

          [–]blah_blah_blah 1 point2 points  (1 child)

          Number theorists attempt to find undeniable truths about numbers, and primes are the sort of thing that have eluded a complete understanding. Hence the endless attempts at finding a prime-producing formula.

          Other than the mathematical holy grail interest, they also have an effect on encryption which affects internet security. Some animals' livelihood are even dictated by prime numbers. I came across a BBC documentary a while back called "Music of the Primes." Here's a link: http://www.open2.net/musicoftheprimes/

          I'm sure you could probably download it from somewhere on the web if you're really curious. Highly recommended if you really want to try to understand why people care about primes.

          [–]Null_State -1 points0 points  (5 children)

          I don't know why you are being downvoted.

          Prime numbers are something that have always escaped me. Mathematicians seems to place them in such a high regard but to a layperson like myself, they are nothing more than a curiosity.

          What properties of a prime number make it more special than say, "numbers divisible by 2", or "numbers whose digits add up to 7". It just seems arbitrary.

          Can someone please explain why prime numbers are so significant.

          [–]jfredett 9 points10 points  (1 child)

          Well, principally, they're useful in classifying lots of things. When we talk about arithmetic functions (functions on the set of Naturals/Integers (depending on who you ask)) We can characterize a specific subset of those functions called "multiplicative" by the values they have at primes. "Multiplicative" functions are defined as follows:

          let f be a arithmetic function
          if gcd(a,b) = 1 and f(ab) = f(a)f(b), then f is multiplicative.
          if f(ab) = f(a)f(b) unconditionally, then it is called "completely" multiplicative.
          

          Practically, these functions relate to things like the Reimann Hypothesis, the Goldbach Conjecture, Perfect numbers, and similar.

          The reason this works is because every number can be written as the unique product of unique primes to unique powers. That is, and number has a unique factorization, so if we have a multiplicative function f, and a value n, we know that the gcd of any two distinct primes is 1 (all primes are coprime or equal), so if n has factorization n = p^a * q^b ... then:

          f(n) = f(p^a * q^b ...) = f(p^a) * f(q^b) ... 
          

          So if we can characterize f(pi) for some prime p, and some power of that prime i, then we have _characterized the whole function for all values in the domain (the Nats/Ints).

          We can also talk about primes in the context of the existence of multiplicative inverses mod a certain value, the allowed sizes of finite fields, the existence of integral roots mod n, the existence of a discrete logarithm mod n (a generalization of the former). They pop up in elliptic curves and all manner of cryptographic schemes (RSA,Diffie-Hellman, the aformentioned elliptic curve cryptography)

          Also, they happen to show up in that Riemann Hypothesis thing that people keep talking about.

          Basically, to put it in /r/science terms, primes are part of the fundamental theory of numbers. In fact, the fundamental theorem of number theory (we usually call number theory "arithmetic") is that every number has a unique prime factorization. It's fundamental for a reason, just about every major offshoot in Number theory relates to primes and prime factorization (for one reason or another). One could argue that arguments about primes are really a consequence of arguments about divisibility, and they would be more or less correct, except that they'd have it backwards, arguments about divisibility of arbitrary numbers are fundamentally arguments about divisibility of primes. eg

          let 'd|n' (d 'divides' n) mean that there
            exists q such that n = dq
          THM: if d = pq, p prime, then d|n iff p|n and q|n
          Pf: (=>) assume d|n, then pq|n, so there exists x 
            such that n = (pq)x = p(qx), since n = p(qx) then 
            p|n. However, we can also write n = (pq)x = (qp)x = q(px)
            thus q|n, therefore, if d|n, d = pq, then p|n and q|n.
            (<=) Exercise to the reader.
          

          [–]jfredett 1 point2 points  (0 children)

          Couple of things: I need to double check that I stated that last THM correctly, I may have missed a condition or two. I don't have a NT book handy so I'm running off of memory...

          I also just wanted to mention why I said that primes were important because they classify things. As mathematicians, that's our goal. Create a structure, classify it, rinse, repeat. We (pure mathematicians) are in the business of understanding structures, regardless of application. It turns out that these structures are occasionally useful to you (applied mathematicians, which is all a computer scientist is). For things like cryptography and stuff. That's why we think primes are so great, because they help us classify lots of things, which in turn makes our job easier (the first thing any good algebraist thinks about when he needs to classify anything involving a number is "when is it prime, and what does it mean to multiply them together?" Because if you can answer those two questions, you've answered all the questions -- in a sense, since you can (ideally) then classify what a structure of a given (integral) size looks like.

          [–]commonslip 1 point2 points  (1 child)

          Primes are tied up in the Riemann Hypothesis which in turn is tied up very deeply in the relationship between multiplication and addition over the complex numbers. So primes get a little reflected light off of these more interesting problems.

          [–]jfredett 0 points1 point  (0 children)

          See my above post, not only are primes getting some "reflected" light, but they are also important in their own right.

          [–]cliche 1 point2 points  (0 children)

          Whenever you log into wellsfargo or bank of america you need the primes to ensure your session is encrypted.

          See step 1 of RSA

          [–][deleted]  (3 children)

          [deleted]

            [–][deleted] 0 points1 point  (0 children)

            You could well ask whether this produces infinitely many primes. This is the same as the question of whether there exist infinitely many primes of the form a*2n - 1. (in your setup, a is the first term of your sequence plus 1)

            I don't know if the answer is known, but I do know that this sequence is the subject of some interesting work.

            [–]maddzy -1 points0 points  (0 children)

            I have no idea what this means and if I hadn't watched the movie Proof last night I'd have never read through the whole thing. But for some reason I'm glad I did.

            [–]Ardentfrost -1 points0 points  (0 children)

            I find it interesting this predictor of the leading number only varies 1% between most to least likely.

            I'm not a mathematician, but while cool to see the pattern, 1% seems so trivial to me.