Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

New Pattern Found In Prime Numbers

Soulskill posted more than 5 years ago | from the benford-and-sons dept.

Math 509

stephen.schaubach writes "Spanish Mathematicians have discovered a new pattern in primes that surprisingly has gone unnoticed until now. 'They found that the distribution of the leading digit in the prime number sequence can be described by a generalization of Benford's law. ... Besides providing insight into the nature of primes, the finding could also have applications in areas such as fraud detection and stock market analysis. ... Benford's law (BL), named after physicist Frank Benford in 1938, describes the distribution of the leading digits of the numbers in a wide variety of data sets and mathematical sequences. Somewhat unexpectedly, the leading digits aren't randomly or uniformly distributed, but instead their distribution is logarithmic. That is, 1 as a first digit appears about 30% of the time, and the following digits appear with lower and lower frequency, with 9 appearing the least often.'"

Sorry! There are no comments related to the filter you selected.

Other bases? (4, Insightful)

wiredlogic (135348) | more than 5 years ago | (#27896535)

When happens with the primes are represented in base-9 or base-11?

Re:Other bases? (5, Funny)

Anonymous Coward | more than 5 years ago | (#27896559)

It would be bad.

Re:Other bases? (5, Funny)

Anonymous Coward | more than 5 years ago | (#27896631)

Bad as in "cross the streams" bad, or "according to an AC on Slashdot" bad ?

Re:Other bases? (0)

Anonymous Coward | more than 5 years ago | (#27896827)

worse than both: "someone said it on the internet" bad! ohmagawd! noway!

Re:Other bases? (0)

Anonymous Coward | more than 5 years ago | (#27896573)

A different application of Benford's Law, presumably.

Re:Other bases? (5, Informative)

hkz (1266066) | more than 5 years ago | (#27896621)

Benson's Law is actually independent of the number base used. It wouldn't be much of a mathematical property if it wasn't. No matter how you convert a number, you will always see the same bias.

Re:Other bases? (4, Insightful)

jonaskoelker (922170) | more than 5 years ago | (#27896689)

I don't know; it might be interesting to know that the leading digits of powers-of-k are distributed in some interesting way in base not-k. They obviously all have a leading 1 in base k.

Re:Other bases? (4, Interesting)

Anonymous Coward | more than 5 years ago | (#27896749)

Benson's Law is actually independent of the number base used. It wouldn't be much of a mathematical property if it wasn't.

Err, what? The study of representations of numbers is a valid field of mathematics itself.

Re:Other bases? (0)

Anonymous Coward | more than 5 years ago | (#27896761)

Do you have a proof of that?

Re:Other bases? (0)

Anonymous Coward | more than 5 years ago | (#27896793)

if that law can make me win the lotto, I totally follow it...

Re:Other bases? (5, Funny)

Lillesvin (797939) | more than 5 years ago | (#27896901)

I'm pretty sure that in base-2 with no zero-padding, 100% will start with 1. :-p

Re:Other bases? (5, Insightful)

dynamo52 (890601) | more than 5 years ago | (#27897003)

I'm pretty sure that in base-2 with no zero-padding, 100% will start with 1.

...and all but one would end with 1 as well.

Re:Other bases? (4, Interesting)

stonewallred (1465497) | more than 5 years ago | (#27896961)

Code this have cryptographical uses? IANAMOG, but I know primes play a role in many crypto schemes.

Re:Other bases? (1)

MeatBag PussRocket (1475317) | more than 5 years ago | (#27896677)

all your bases are belong to primes.

Re:Other bases? (5, Funny)

Megaweapon (25185) | more than 5 years ago | (#27896697)

base-9 or base-11?

NEVER FORGET

Re:Other bases? (5, Informative)

pdxp (1213906) | more than 5 years ago | (#27896699)

It wouldn't change the logarithmic nature of the distribution of the digits, AFAIK.

My math degree is getting dusty, but I'm pretty sure that the same pattern could be represented in another base by changing their generalization of Benford's law to include it, and the distribution would look like log(x)/log(9) or log(x)/log(11). Remember, changing the base of a logarithm is easy: for example, log(x)/log(e) = ln(x)

So you get the same distribution, different base.

Re:Other bases? (0)

ubungy (1471733) | more than 5 years ago | (#27896727)

All the base are belong to this.

Re:Other bases? (2, Interesting)

Kjella (173770) | more than 5 years ago | (#27896773)

If you got more numbers in 10-19 than 90-99, you probably also have more numbers in 0x10-0x1f than 0xf0-0xff...

Re:Other bases? (2, Interesting)

Anonymous Coward | more than 5 years ago | (#27896783)

(Warning, IANAM)
It's base independent. Basically, primes are distributed on a logarithmic scale (prime number theorem). For sufficently large intervals, there are always more primes in interval starting at x than the interval of the same size starting at y if xy. Like, there are more prime numbers in 1000..1999 than in 9000..9999.

Re:Other bases? (4, Informative)

dave1g (680091) | more than 5 years ago | (#27896797)

from benfords law link:

"The result holds regardless of the base in which the numbers are expressed, although the exact proportions change."

Re:Other bases? (3, Funny)

AvitarX (172628) | more than 5 years ago | (#27896813)

I just did it in base-2 and found that 100% of all primes start with the digit 1.

Re:Other bases? (1)

BobReturns (1424847) | more than 5 years ago | (#27897023)

And, all the primes (except for one of them) end with the digit 1 as well.

Re:Other bases? (5, Funny)

CaseyB (1105) | more than 5 years ago | (#27896819)

All your base are belong to Benford.

Re:Other bases? (1)

Tubal-Cain (1289912) | more than 5 years ago | (#27896861)

I've often wondered how many patterns we are missing, especially in regards to our "special" numbers (Pi, Phi, e, primes....) because we mostly deal in base10. If we suffer a Class 1 or Class 2 Apocalypse [tvtropes.org] , I intend to seize the opportunity and implement hexadecimal as a default number system.

Re:Other bases? (1)

Rayban (13436) | more than 5 years ago | (#27896887)

obxkcd:

http://xkcd.com/567/ [xkcd.com]

Re:Other bases? (1)

maraist (68387) | more than 5 years ago | (#27897073)

As you know, the 'leading digit' is related the highest power of a base. Logs pull the exponents off a power - with only the highest power having any great effect. Namely, with 2 * 10^2 + 9 * 10^1, the 9 part is neglegable.

Benford's law (BL) is based on the distribution the log-scale, so obviously the 'base' (the 10) is meaningless.

However, if you used a number system that wasn't based on exponential powers, then you could definitely reveal different patterns. Maybe a non-linear, a circular, a factorial number system.

9999991 (0)

Anonymous Coward | more than 5 years ago | (#27896545)

Explain 9999991 then. :P

Re:9999991 (4, Insightful)

Aranykai (1053846) | more than 5 years ago | (#27896583)

Explain one man being hit seven times with lightning. http://en.wikipedia.org/wiki/Roy_Sullivan [wikipedia.org]
Improbable doesn't mean impossible.

Re:9999991 (2, Interesting)

anss123 (985305) | more than 5 years ago | (#27896739)

Explain one man being hit seven times with lightning. http://en.wikipedia.org/wiki/Roy_Sullivan [wikipedia.org]

Poor bastard. After the fourth! time he began carrying a pitcher of water with him... I find it hard not to be amused.

Re:9999991 (1)

kylemonger (686302) | more than 5 years ago | (#27896879)

Explain one man being hit seven times with lightning.

Easy. He lied about the last six strikes.

Re:9999991 (1)

RudeIota (1131331) | more than 5 years ago | (#27897075)

According to National Geographic's Flash Facts About Lightning, the odds of being struck in a lifetime is three-thousand to one.

That sounds surprisingly likely... but I'm inclined to think he was lying.

I mean, doesn't lightning heat the surrounding air enough to melt sand into glass? We're talking thousands of degrees here. How could someone survive that ONCE, let alone 6 more times?

Re:9999991 (0)

Anonymous Coward | more than 5 years ago | (#27896593)

Well it is 9 shy of 10,000,000. See 9999991+9= 10,000,000.

9 not too common? (1)

pdxp (1213906) | more than 5 years ago | (#27896565)

with 9 appearing the least often

Maybe they didn't count high enough? I wouldn't blame them, I get tired of computing primes by 7...

Re:9 not too common? (4, Funny)

doti (966971) | more than 5 years ago | (#27896753)

that makes my /. id even more impressive :)

Re:9 not too common? (1)

pdxp (1213906) | more than 5 years ago | (#27896849)

I'm jealous... mine is off by 1!

Duh (3, Insightful)

Anonymous Coward | more than 5 years ago | (#27896567)

Benford's "law" is not a law at all... any exponential distribution will exhibit this behavior.

Re:Duh (2, Funny)

Anonymous Coward | more than 5 years ago | (#27896837)

You're right! I'm writing to my congress asking them to repeal Benford's Law.

Well fuck me (-1, Offtopic)

Anonymous Coward | more than 5 years ago | (#27896569)

It turns out that they're all odd numbers [goatse.fr] .

Why do people study "math" in college? (-1, Offtopic)

commodore64_love (1445365) | more than 5 years ago | (#27896577)

I don't get it. Surely there's a better major than "mathematics"? I recently went to my college's "scholar day" wherein students created posters and described what they were working on for classroom projects. The engineering students received lots of attention, since they were building "cool" stuff like solar cabins or battery-powered boats or whatever.

But then I noticed one cute young lady was standing all by herself, in front of her project, which consisted of lots of esoteric math. I felt sorry for her because she was basically being ignored, so I asked her to give her brief explanation. When she was done I wondered if she was going to be unemployed in a few years, because I could not see how her knowledge had any application in the real world.

Re:Why do people study "math" in college? (1)

drinkypoo (153816) | more than 5 years ago | (#27896639)

When she was done I wondered if she was going to be unemployed in a few years, because I could not see how her knowledge had any application in the real world.

Your anecdote does not contain any interesting information. What was her "esoteric math" about?

Re:Why do people study "math" in college? (4, Funny)

Anonymous Coward | more than 5 years ago | (#27896701)

The real question is did his feigned interest result in sexual intercourse?

Re:Why do people study "math" in college? (0)

Anonymous Coward | more than 5 years ago | (#27896679)

http://xkcd.com/435/
That and the fact higher math can be quite beautiful.

Re:Why do people study "math" in college? (4, Insightful)

wjh31 (1372867) | more than 5 years ago | (#27896711)

hello troll, your inability to understand mathematics does not mean it has no real world application. her little project may well have been able to provide the basis for some ecomonic or social model, or may proove vital in unlocking the bit of physics that enables the next revolution in technology. Besides all these very important uses that skip the average joe, mathematics is often elegant and beautiful, and may be considered a form of art by some people

Re:Why do people study "math" in college? (3, Insightful)

MikeUW (999162) | more than 5 years ago | (#27896729)

Perhaps she was wondering the same about you as you walked away looking dumbfounded.

Just because something is complicated and difficult for most people to grasp doesn't mean it hasn't got some real-world application at some point. That's why we need people like her to make sense of that sort of stuff, to the benefit of the rest of us.

Re:Why do people study "math" in college? (1)

Nihixul (1430251) | more than 5 years ago | (#27896745)

"Top * Lists" aren't necessarily unassailable data, but mathematicians, statisticians, and actuaries [wsj.com] can do pretty well.

Re:Why do people study "math" in college? (0)

Anonymous Coward | more than 5 years ago | (#27896751)

A *lot* of physics would not be possible without mathematics, a lot of chemistry and 'engineering' would not be possible without physics...get it?

Besides it's a beautiful occupation that show truly beautiful things and brings great understanding, it's also very good for learning how to think properly which I really miss in a lot of 'non mathematicians'. (sure they have a lot of knowledge, but they still think in goofed up ways)

Plenty of reasons people study math (4, Insightful)

sirwired (27582) | more than 5 years ago | (#27896785)

A few examples:

For the same reason some people take Philosophy, Ancient Literature, Paleontology, etc. Because they think the subject is cool, and aren't necessarily at school to learn a trade. (Indeed, Engineering students that are paying attention also discover they aren't directly being taught a trade either. Or at least they aren't in any Engineering college worthy of the name.)

They want to become an actuary. This is a fairly well-paid job that is also rather difficult to do, and even harder to do well.

They want to become math teachers; a valuable and much-needed profession. Math is a useful tool in teaching students how to think. We certainly don't torture legions of high school students with the details of conic sections because anybody is under the impression this is a directly practical skill for most citizens to have. Nor are hundreds of thousands of college students subjected to the horrors of calculus because of some kind of employment program for math post-docs.

They are double-majors in a field in which math is extremely important (physics, astronomy, computer science, every type of engineering, linguistics, medicine, biology, etc. Pretty much every field outside the humanities. Oh, and some of the humanities make extensive use of math too.)

SirWired

1... (-1)

noz (253073) | more than 5 years ago | (#27896611)

1st post?

Like batting orders (3, Interesting)

sam_handelman (519767) | more than 5 years ago | (#27896617)

I'm not a mathematician, could someone explain why this is surprising in terms that a computer programmer or biologist could follow? First thing I thought - no matter how many innings you have, you can guarantee that the top of the order will be up at least as many times as the bottom of the order.

  Okay, if you have a random number along the interval (1,10^X), all the leading digits will be equally likely.

  If you have some other interval (1,n*10^X), 1<=n<=9, then the leading digits > n will appear roughly 1/10 as often as leading digits 1..n.

  If you have a large sample which is drawn from an admixture of some huge number of random distributions (1,n*10^X), with the "n" of each sub-distribution evenly distributed on 1..9, then the lower leading digits will be moderately more common, yeah?

  Prime numbers, meanwhile, become decreasingly common as you get larger and larger, is that not correct? So it seems to me this is the obvious way to model prime numbers, no?

On the density of prime numbers (4, Insightful)

jonaskoelker (922170) | more than 5 years ago | (#27896779)

Prime numbers, meanwhile, become decreasingly common as you get larger and larger, is that not correct?

Yes, that is correct. There are roughly logarithmically many of them.

Bertrand's Conjecture (proven by Chebyshev) states than for all n > 1, there's a prime p with n < p < 2n.

If you look only at powers of two, it's readily seen that there are n primes between 1 and 2^n; setting k=2^n, there are log(k) primes between 1 and k.

A logarithmic upper bound follows from the Prime Number Theorem, which doesn't have an easy proof (AFAIK). It says something much more specific than just "It's O(log n)", though. Maybe there's a simple theorem from which you can derive O(log n), but I don't know.

Re:On the density of prime numbers (4, Informative)

jonaskoelker (922170) | more than 5 years ago | (#27896857)

Maybe if I had read the prime number theorem, I would have known that it's O(n / log n), which is somewhat bigger...

Re:On the density of prime numbers (0)

Anonymous Coward | more than 5 years ago | (#27897001)

Okay, so what about the second digit? Wouldn't that follow a pattern as well, though less pronounced?

Re:Like batting orders (1)

thomasw_lrd (1203850) | more than 5 years ago | (#27896937)

You can't be computer science without being a mathematician.

Optimus Prime (0)

Anonymous Coward | more than 5 years ago | (#27896629)

Where does Optimus Prime fit in?

Stock market analysis? (4, Interesting)

MSTCrow5429 (642744) | more than 5 years ago | (#27896635)

I am admittedly not a mathematician, but I do have a good understanding of economics and finance, and I am not seeing how a pattern found in prime numbers could have any application to stock market analysis. Where is the interaction between prime numbers and the praxeology of buying and selling securities? Even if you're only focusing on automated buying and selling, those algorithms were still programmed by humans with their own subjective approaches and underlying premises.

Re:Stock market analysis? (0)

Anonymous Coward | more than 5 years ago | (#27896721)

Large primes are used for encryption schemes, authentications, and other applications, but I agree with you that there doesn't seem to be an application of this knowledge to finance. There isn't any way to make a mathematical model of the stock market without invoking the "rational consumer" as a component. Since participants are not rational, no amount of theory will make up for the goofiness of their behaviour. It isn't even random.

Re:Stock market analysis? (1)

wjh31 (1372867) | more than 5 years ago | (#27896743)

it makes more sense to me if you read that benfords law had applications in stock markets, fraud etc, but that isnt news...

Re:Stock market analysis? (1)

thedohman (932417) | more than 5 years ago | (#27896817)

Where is the interaction between prime numbers and the praxeology of buying and selling securities?

Primes don't have anything to do with Stock Market analysis.

From the article (ha! I didn't read it, I just skimmed it, but it's not think with maths), what the researchers found, using primes, is a generalization of Benford's Law. It's this Generalized Benford's Law that can be used in Analysis.

In addition, many applications that have been developed for Benford's law could eventually be generalized to the wider context of the Generalized Benford's law. One such application is fraud detection: while naturally generated data obey Benford's law, randomly guessed (fraudulent) data do not, in general.

(OK, so the article doesn't mention stock market except for the part that is quoted in the summary, but better fraud detection would play a part in stock market analysis, yes?)

Re:Stock market analysis? (2, Informative)

maxume (22995) | more than 5 years ago | (#27896833)

Benford's law can be used to detect fraud (the article states this, I don't have any reason to doubt it). They studied primes and found a pattern that is associated with a related property that they are calling Generalized Benford's Law. Presumably, the generalized rule can be used to detect a wider range of unnatural activity than Benford's law itself.

Re:Stock market analysis? (4, Funny)

Rayban (13436) | more than 5 years ago | (#27896893)

I've always wondering how I could figure out when someone was trying to pass off a list of fraudulent primes. Glad to see that this problem is finally solved!

Re:Stock market analysis? (4, Interesting)

arth1 (260657) | more than 5 years ago | (#27896995)

I've always wondering how I could figure out when someone was trying to pass off a list of fraudulent primes. Glad to see that this problem is finally solved!

You're jesting, but I imagine that many fields of encryption would benefit from this, like dual key encryption, where the security lies in the ability to trust that the product really is of two primes, and that factoring this would be extremely time consuming.

Sets with a backdoor inserted may indeed have a different signature, and to be able to quickly see that one set differs would be invaluable. It wouldn't prove anything, but if, say, keys received from a certain company's key generator stood out like a sore thumb in a Benford distribution check, you would have reason to suspect foul play, incompetence or both.

Re:Stock market analysis? (1)

JustOK (667959) | more than 5 years ago | (#27897047)

Now you can start looking for typos in the digits of pi

Re:Stock market analysis? (2, Interesting)

maxume (22995) | more than 5 years ago | (#27897065)

"I have poor reading comprehension" isn't that great of a joke.

If you really didn't figure it out yet (I suspect you actually have), the ability to detect a pattern that should occur in natural data but probably will not be present in fraudulent data (a sophisticated fraudster can generate to any test...) is what makes it interesting for detecting fraud, not the fact that the pattern was first elucidated from prime numbers.

Re:Stock market analysis? (1)

maraist (68387) | more than 5 years ago | (#27896963)

Read the articles. This is pretty cool stuff. There's a hundred+ year old model called Benford's Law (BL), and more recently, seemingly originated via the study of prime, a generalization (GBL). Lots of data-sets apparently have a log-scale even probability distribution instead of a uniform probability distribution or bell-shaped-curve probability distribution. Things that grow exponentially have a log-scale even distribution (the articles give several examples). And thus the BL applies (the leading 1 occurs more than 2, than 3, etc, in all bases). This is useful for fraud-detection. Namely if you know BL distributions should apply, but you are handed numbers by a potentially fraudulent vendor. Simply test for BL. Granted, a careful fraudulent vendor would randomize their fraudulent data by BL instead of uniform distribution. But if the vendor can't control the data set (say there is a stock market intermediary that is in a position to sell stock that doesn't exist, even if only on a small scale), then it is the aggregate sales would reveal such an anomaly.

What GBL does is open up the statistical model so it applies to more data-sets that were previously considered without a pattern. Prime numbers are an example. And the key was that it was scale-dependent. An infinite number of prime numbers has an even distribution of leading digits. But smaller data-sets DID express BL distributions. GBL applies by using the scale of the data-set. And that scale factor is the new component in GBL.

Re:Stock market analysis? (0)

Anonymous Coward | more than 5 years ago | (#27896965)

I don't think this really has any serious application to trading or picking stocks. Benford's law (BL) just talks about the distribution of numerical data (prices). The only application for BL in the stock market that i know of, is that the difference between 10 and 20 is 100% while 90 and 100 is only 11% so you'd expect many more stocks 10-20. BL applying to primes shouldn't add too much insight to the stock market.

However, most investors already be think in percentages/logarithms instead of nominally, so BL just becomes a curious fact.

Re:Stock market analysis? (4, Funny)

rackserverdeals (1503561) | more than 5 years ago | (#27896981)

I am admittedly not a mathematician, but I do have a good understanding of economics and finance, and I am not seeing how a pattern found in prime numbers could have any application to stock market analysis. Where is the interaction between prime numbers and the praxeology of buying and selling securities?

By understanding the patterns in prime numbers you can learn to spot them and avoid the sub-prime mortgage backed securities. Duh.

Not suprising (-1, Redundant)

Anonymous Coward | more than 5 years ago | (#27896651)

As numbers get larger, there are more lower primes it can potentially be a multiple of.

It would be logical that a number starting with a "1" would be more likely to be prime than a number between five and nine times larger.

I fail to understand what was "discovered" here.

The real article, and what it does and doesn't say (2, Informative)

jonaskoelker (922170) | more than 5 years ago | (#27896667)

You can find the mathematicians' article at http://www.citeulike.org/group/3214/article/3664693 [citeulike.org] or http://arxiv.org/pdf/0811.3302 [arxiv.org] (pdf warning).

I find it interesting that the article doesn't prove any theorems. At least searching for the word "theorem" in the pdf only gives references to other theorems. Searching for "proof" gives no hits.

That leaves me thinking: what does this article tell us that we couldn't find out ourselves by ripping through some prime numbers? I thought the real power of math was to say something 100% certain about some infinitude of stuff, so we don't have to go and check every case by hand.

Oh well, I guess every open question needs some results on the form "this holds for all n <= bignum"; say, like the Goldbach Conjecture (every even number n > 2 is the sum of two primes).

Re:The real article, and what it does and doesn't (3, Insightful)

quarrel (194077) | more than 5 years ago | (#27896821)

> That leaves me thinking: what does this article tell us that we couldn't find out ourselves by ripping through some prime numbers?

Nothing?

The important thing is that they ripped through some prime numbers and did notice, and they were the first to publish what they noticed.

The world moves forward in tiny steps like this. Maybe the next mathematician gets his 'Ahuh' moment on the back of an insight like this and bang modern crypto is fucked. He might even be able to prove it for you.

--Q

Re:The real article, and what it does and doesn't (1)

product byproduct (628318) | more than 5 years ago | (#27896835)

Their experimental result is a trivial consequence of the fact that prime number density around n is about 1/log(n). One could work out the exact theoretical distribution in one paragraph and that'd be all. I guess the authors are either ignorant or they prefer to market their result as "mysterious". Probably both.

Re:The real article, and what it does and doesn't (1)

anomalous cohort (704239) | more than 5 years ago | (#27896903)

OK, not the most exciting science story of all time. Perhaps Carl Sagan either implanted or discovered a potential capacity for fascination with the science of primes in his novel "Contact" where a large sequence of prime numbers is used as an attempt by extra terrestrials to communicate with humanity.

Re:The real article, and what it does and doesn't (1)

vesuvana (1166821) | more than 5 years ago | (#27896845)

Harsh critic--the article doesn't boast about solving theorems or offering 100% certain proofs. It is sufficient to bring to greater notice that this pattern, which had gone unnoticed, has now been noticed. Maybe someone will do something further with it. Sooner or later it's likely that this piece of information will get incorporated into something economically useful. But for now, as pure science, noticing the pattern that had not been noticed before is good enough for publication.

Cryptography? (5, Funny)

PolygamousRanchKid (1290638) | more than 5 years ago | (#27896709)

Could this have any applications there?

"Well, I wasn't expecting The Spanish Mathematician . . ."

Re:Cryptography? (4, Funny)

MRe_nl (306212) | more than 5 years ago | (#27896781)

Our two main powers are insight into the nature of primes, fraud detection
and stock market analysis.
I'll come in again...

Re:Cryptography? (0)

Anonymous Coward | more than 5 years ago | (#27896933)

It might have an application to key generation, but not directly based on most algorithms used to generate keys. (PGP generates prime numbers which all begin with binary 11. I wonder if there's a pattern to the third binary digit. Probably there is, with more 0s than 1s, but it's probably not that significant.)

Re:Cryptography? (1)

Kal Zekdor (826142) | more than 5 years ago | (#27896983)

Could this have any applications there?

While public key cryptography does use a prime number in order to generate a shared secret key, this prime number is transmitted openly and assumed to be known by all attackers. Diffie-Hellman key exchange [wikipedia.org]

The security of the protocol comes from the difficulty of solving the discrete logarithm problem, which has nothing to do with the prediction of prime numbers.

I'm unsure if your question was about the security of current cryptography (i.e. hacking), or development of new, more secure, cryptography algorithms. In the second case, the ability to help predict primes may help reduce the computing cost of encryption, if not decryption, though I doubt it will lead to any additional security.

A disclaimer, I am a computer programmer, but I have only a passing familiarity with the mathematics of cryptography.

Good for them (4, Funny)

l00sr (266426) | more than 5 years ago | (#27896715)

Nobody expects the Spanish Mathematicians!

Isn't this obvious? (1, Informative)

Anonymous Coward | more than 5 years ago | (#27896725)

TFA does provide many details, but I believe everyone doing maths is taught that the number of primes before some number n is approached by n/ln n ( http://en.wikipedia.org/wiki/Prime_counting_function). This has been known for more that a century.

As specified by this formula, the prime density decreases, so it seems obvious that if one considers all primes with a set number of digits, fewer start with a nine than with a one.

Maybe I'm missing something but this does not seem to provide any new information or new pattern.

This is news? (0)

Anonymous Coward | more than 5 years ago | (#27896775)

This... should not come as a surprise to anyone. We all know primes occur less often as you go higher, which makes sense by the definition of a prime. So there are going to be more primes between 1000 and 2000 than between 2000 and 3000, and so on. Meaning the leading digit will be a 1 more often than a 2, a 2 more often than a 3, etc.

stupid question (0)

Anonymous Coward | more than 5 years ago | (#27896777)

I hope this is more than just the bias you'd expect from the Prime Number Theorem, a corollary of which is that the population of primes decreases exponentially with N.

In each "decade" (10*p.. 10*(p+1)-1, for positive integer p), digits with leading digit 1 come first, and digits with leading digit 9 come last.
For example, with p=2 the numbers (100..199) are in the first group, while (900..999) are in the last group. So you would expect the group with leading digit 1 to have, on average, more primes than the group with leading digit 9.

Rinse and repeat for every decade with that same Prime Number Theorem bias.

Just as in an ideal NFL draft with uniformly competent general managers and no trades, the team picking first in each round is supposed to have a better draft than the team picking last in each round. (Of course, in real life we have the Detroit Lions).

Breaking news!!! (1)

mykelyk (1469041) | more than 5 years ago | (#27896801)

Prime numbers follow a logarithmic curve!!

Film at 11.

Old? [wikipedia.org]

What the arXiv paper says (2, Informative)

Anonymous Coward | more than 5 years ago | (#27896805)

Before I begin, I am a math phd candidate, but not in number theory. The following is probably better than a lay interpretation, but not an expert either.

Basically, they have generalized BL (Benson's Law) to get a GBL. They then tested the primes in the range [1,10^11] against GBL, and verified they were satisfied. They DID NOT PROVE THIS HOLDS FOR ALL PRIMES!!! They then went on to conjecture the applications of this to other areas (finance, etc).

Though the result is interesting, I really see this paper as a conjecture on the nature of primes, related to the Riemann zeta function. (From what I understand someone has proved zeros of the zeta function follow GBL.)

Stat Foop (1)

oldhack (1037484) | more than 5 years ago | (#27896831)

Yeah, it only looks like that because started finding primes from 1 up. If we started finding them from infinity down...

Is public key encryption affected? (1)

mmell (832646) | more than 5 years ago | (#27896871)

Could this be the beginnings of a non-quantum solution to, say, the problem of factoring large numbers? Not a solution itself, but the beginnings of a method for breaking RSA without resorting to the use of q-bits et. al.?

Re:Is public key encryption affected? (1)

russotto (537200) | more than 5 years ago | (#27896895)

Could this be the beginnings of a non-quantum solution to, say, the problem of factoring large numbers? Not a solution itself, but the beginnings of a method for breaking RSA without resorting to the use of q-bits et. al.?

Probably not. It's an interesting result, but it's not specific to prime numbers. Rather, it applies to all sets whose density is related to 1/log n.

Gotcha. (1)

mmell (832646) | more than 5 years ago | (#27897087)

Hey, I wonder if this holds true beyond Skewes number? (I don't remember all the particulars, but seemingly primes start to become more common beyond some incredibly high value. I vaguely remember reading an article by Isaac Asimov in SF monthly on the subject. At that time, Mr. Asimov suggested that there would be another point where that would reverse, but (with his dry sense of humor) he suggested that attempting to calculate Skewes number already left him skewered, and computing that second reversal point left him super-skewered.

I never heard such nonsense (0)

Anonymous Coward | more than 5 years ago | (#27896877)

I call BS, why would primes care what they look like in base10? And how could something like this be equally true for different base notations at the same time, which is what the Wikipedia article claims. I mean does this really apply equally to base 2 binary and base 9?

And a quick glance at the wikipedia list of sequences that are supposed to follow this "Benfords law" shows a lot of areas where the unit of measurement can be chosen somewhat arbitrarily and where humans pick the numbers:

This counter-intuitive result has been found to apply to a wide variety of data sets, including electricity bills

People might irrationally be more likely to say what 100 Kwh? Time to start saving energy. And there might be all sorts of discounts/ tax incentives that kick in at a 100 something per something.

street addresses,

Sounds like house numbers to me, again something entirely under the control of humans and their peculiar preferences for certain base 10 numbers. Though I kind of expect the lack of thirteenth floors to mess up this example.

stock prices,

I am not gonna bother debating whether there a bunches of stock traders who use chicken entrails when deciding when to buy and sell at a time when almost everyone worries that the chicken entail guys might be the more rational ones on the major financial markets.

Of course if humans have to set millions of the prices at which they will trade per day they some of them will go for round numbers and might favor a leading one. We would be loucky if that was the worst thing stock traders did.

population numbers,

Interesting for countries, not for populations for which its easier to decide to invest in and move into and out of like cities. Of course humans if over time millions of people have to make the decision to I migrate into/out of and invest into a town then people will say 95.000 inhabitants? too small to invest/stay, 100.000? thats just big enough.

death rates,

deaths per what?

lengths of rivers,

Well how many big rivers are there anyway? I will concede this as a coincidence with the note that that might be some unit of measurement preferences going on.

physical and mathematical constants,

that are not named and might have been cherry picked.

and processes described by power laws (which are very common in nature).

which, if I understand the "Benford distribution" correctly, is somewhat of a circular argument.

I think I will stick to using prime based crypto for now.

Quite obvious, this one (1)

gweihir (88907) | more than 5 years ago | (#27896939)

On the other hand, in binary it will be 1 in all cases. Time for a new law? I don't think so...

Isn't this really obvious? (1)

ThatsLoseNotLoose (719462) | more than 5 years ago | (#27896955)

Isn't this just a consequence of prime numbers getting sparser as you climb higher?

i.e, there are 135 primes between 1000 and 2000, and there are 127 between 2000 and 3000.

If you're dealing with phone numbers (5, Interesting)

Ralph Spoilsport (673134) | more than 5 years ago | (#27896991)

It has less to do with math and more to do wit physics: as in how to use a an old school phone. Phone numbers, until comparatively recently would "prefer" lower numbers because they are EASIER TO DIAL. If a company had the phone number (909)999-9009 you would HATE dialing that thing. It would take about half a minute just to dial the damn number.

Ssssshhhhhhik!
diggadiggadiggadiggadiggadiggadiggadiggadigga!

Total pain in the finger.

1 as a first number was reserved for "other stuff" like international calls, so the lowest possible area codes (first numbers) went to places like New York City (212 - very quick to dial) or LA (213) because millions of people would be dialing that number, so it made for an overall faster dialing experience for (on average) more people.

This is compared to the relatively few people who lived in more obscure parts of the country, like Saginaw MI (989) or Bryan TX (979).

So, you have millions of phones in 212, thousands in 979. The result: saved effort in dialing.

Also, to this end there was a preference for exchanges to have lower numbers as well to save on dialing effort, and phone numbers with lower (but NON-ZERO) values were sought after. You'd see advertisments like "Call RotoRooter - 213 464 1111 !" or "Call us NOW for a free analysis! 201 738 1122 !" etc. and so on.

So, lower numbers in phone numbers have been a product of primitive dialing technology. Now with touchtone - all that is out the window - but the historic trend is still there and quite powerful - people will pay good money for a 212 area code for the distinction of being in the "real" New York Area code...

RS

Re:If you're dealing with phone numbers (2, Insightful)

Sir_Lewk (967686) | more than 5 years ago | (#27897061)

Where are my mod points when I need them, that's pretty damned interesting.

Is this surprising? (1)

RobinH (124750) | more than 5 years ago | (#27897005)

It's already obvious that as you increase in size, the primes are further apart (because there are more and more lower numbers that are potential factors).

So given any range of numbers from (10^x) to (10^(x+1)), wouldn't you expect that the density of primes in the bottom end of that range would be higher than at the top end?

I don't know, it just seems obvious. It's an artifact of using a base 10 number system.

Now if you used binary, you wouldn't see this effect. That is, a range from (2^x) to (2^(x+1)) all "start" with the digit 1. Also, if you used a base-infinity number system (where every number has it's own symbol then you also wouldn't see this effect because the maximum number of possible primes in any given "leading digit category" is effectively 1.

Independent Verification (5, Interesting)

eldavojohn (898314) | more than 5 years ago | (#27897031)

Here's what I got on my own counts using the first million primes [utm.edu] :

1: 415441
2: 77025
3: 75290
4: 74114
5: 72951
6: 72257
7: 71564
8: 71038
9: 70320

Which puts the probabilities at:

1: 0.415441
2: 0.077025
3: 0.07529
4: 0.074114
5: 0.072951
6: 0.072257
7: 0.071564
8: 0.071038
9: 0.07032

My computer is currently crunching the first fifty million primes and I will post those as a reply to this post later today when it is done.

These ratios on numbers 2-9 seem far too close in range for this to be a true log scale. Hopefully with more data it will be more logarithmic.

Experts? (0)

Anonymous Coward | more than 5 years ago | (#27897033)

How about only people with 5 digit slashdot ids answer this one? Let's skip the chaff and go straight to the wheat.

Counter-example ... (1)

Sepiraph (1162995) | more than 5 years ago | (#27897055)

I bet this law doesn't apply in base 2 ...

Enron (4, Interesting)

Anna Merikin (529843) | more than 5 years ago | (#27897059)

was busted by auditors who found the books were "cooked" by applying the law of first numbers described in the /. blurb and TFA. The independent auditors found the first figures were randomly distributed instead of following Benford's law with the number 1 the most plentiful and nine the least -- therefore, the entries were fraudulent.

Benford's law knocked my out at the time; I thought of how many bogus figures I had entered in my expense accounts over the years....

This is true only for a finite range (1)

mark-t (151149) | more than 5 years ago | (#27897081)

The set of integers is countable, and any subset of it, including the set of primes beginning with a particular digit, is also countable. One can always define a mapping of any infinite subset of any countable set to the complete set of positive integers, which means, perhaps rather counterintuitively, that they actually have the exact same number of elements.

"...that surprisingly has gone unnoticed until now (2, Funny)

DarkIye (875062) | more than 5 years ago | (#27897083)

They found that the distribution of the leading digit in the prime number sequence can be described by a generalization of Benford's law.

Yeah, how did we miss that? We need to pay more attention.

Load More Comments
Slashdot Login

Need an Account?

Forgot your password?