# Prime numbers

## Recommended Posts

I still don't see why we should call a distribution random just because it is difficult to recreate. If it can be recreated, then how can it be random? The primes are not like raindrops.

If you don't see by now then so be it.

...

I'm happy to change my mind, it makes no difference to me whether the primes are called random, but why should I?

If it makes no difference to you then quit complaining here.

• Replies 139
• Created

#### Posted Images

Peter - as we have discussed before there is no known process to generate primes

I haven't read through this thread but because of the inaccuracy of this statement I feel compelled to jump in here.

Of course we can generate primes. The Sieve of Eratosthenes is one such method. Eratosthenes lived around 200BC so this method is at least 2200 years old.

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

If you imagine a magic black box programmed with the Sieve algorithm, we could push the ON button and it would sit there and spit out each and every prime number in numerical order for as long as we cared to run it.

You may be thinking of a formula for primes. As Wiki puts it, "No such formula which is efficiently computable is known."

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

That page summarizes a number of results that people have figured out in terms of prime-generating formulas.

But if we generalize the word "formula" to "process," then there are lots of processes to generate primes. Here's another one.

(1) Let x = 2.

(2) Is x prime? If yes, print it. If not, don't print anything.

(3) Let x = x + 1.

(4) Go to (2).

Edited by Someguy1
##### Share on other sites

I haven't read through this thread but because of the inaccuracy of this statement I feel compelled to jump in here.

Of course we can generate primes. The Sieve of Eratosthenes is one such method. Eratosthenes lived around 200BC so this method is at least 2200 years old.

It would have helped if you had read it. What you are describing is finding primes which no one is contending can't be done. Again, there is no equation that generates Primes in the sense that there are equations that generate points on a parabola for example.

In spite of your quibbling over imatfaal's wording, mathematicians know exactly what he means just as we know exactly what 'Primes are randomly distributed' means. Whether anyone else doesn't understand or agree is irrelevant.

##### Share on other sites

It would have helped if you had read it. What you are describing is finding primes which no one is contending can't be done. Again, there is no equation that generates Primes in the sense that there are equations that generate points on a parabola for example.

In spite of your quibbling over imatfaal's wording, mathematicians know exactly what he means just as we know exactly what 'Primes are randomly distributed' means. Whether anyone else doesn't understand or agree is irrelevant.

Well, I did read a couple of posts on this page and unfortunately my unease got worse. There is a failure to distinguish between "random" and "randomly distributed." For example the digits of pi are (strongly suspected to be) randomly distributed; but they clearly are not random. They are the output of a deterministic process.

As are the prime numbers. I already showed how to generate them. Since they are the output of a deterministic process, they are not random. They have very low Kolmogorov complexity because there is a short algorithm that cranks them out. I gave one such algorithm.

It's POSSIBLY true that the primes are randomly distributed, but I am not sure a good definition of that phrase has been given. There are a lot of suspected relationships between the distribution of primes and the Riemann hypothesis, for example. So it's likely that not only are the primes not randomly generated; they are also *possibly* not randomly distributed, either. Note the recent breakthrough on the twin prime problem for more evidence. We are learning more every day about the deep laws that determine the distribution of primes.

As far as the squares of primes being 1 mod 6, that's obviously true. A prime must already be +/- 1 mod 6, so its square is 1. But many of the comments on the randomness of primes are not accurate.

Edited by Someguy1
##### Share on other sites

Well, I did read a couple of posts on this page and unfortunately my unease got worse. There is a failure to distinguish between "random" and "randomly distributed." For example the digits of pi are (strongly suspected to be) randomly distributed; but they clearly are not random. They are the output of a deterministic process.

As are the prime numbers. I already showed how to generate them. Since they are the output of a deterministic process, they are not random. They have very low Kolmogorov complexity because there is a short algorithm that cranks them out. I gave one such algorithm.

It's POSSIBLY true that the primes are randomly distributed, but I am not sure a good definition of that phrase has been given. There are a lot of suspected relationships between the distribution of primes and the Riemann hypothesis, for example. So it's likely that not only are the primes not randomly generated; they are also *possibly* not randomly distributed, either. Note the recent breakthrough on the twin prime problem for more evidence. We are learning more every day about the deep laws that determine the distribution of primes.

As far as the squares of primes being 1 mod 6, that's obviously true. A prime must already be +/- 1 mod 6, so its square is 1. But many of the comments on the randomness of primes are not accurate.

Sure glad someguy on the internet POSSIBLY straightened things out.

Edited by Acme
##### Share on other sites

Sure glad someguy on the internet POSSIBLY straightened things out.

That's the best you can do?

##### Share on other sites

I'm still not sure of the correct view here. There seem to be differences of opinion.

Acme - Have you nothing to contribute to this? Or are you just feeling irritable?

Edited by PeterJ
##### Share on other sites

Someguy and Peter

If you wish to keep referring to finding primes within a range as being able to produce them through a process them then there is nothing we can do to stop you; but be aware that this is not normal usage.

The crux of the problem with primes, the reason they are so interesting, why so many careers are spent looking at them is that they are not the result of a function or series; they are not able to be generated, there is no pattern in their occurrence

Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the mind will never penetrate

##### Share on other sites

Someguy and Peter

If you wish to keep referring to finding primes within a range as being able to produce them through a process them then there is nothing we can do to stop you; but be aware that this is not normal usage.

The crux of the problem with primes, the reason they are so interesting, why so many careers are spent looking at them is that they are not the result of a function or series; they are not able to be generated, there is no pattern in their occurrence

I would think that prime numbers can be seem similarly to the numbers in pi.

Even if the decimals in pi are seemingly random, they are the result of a particular function.

$\pi=\sum_{n=0}^{\infty}\frac{4(-1)^{n+2}}{2n+1}$

I think this type of function can be applied to prime numbers, where recursion is what is needed to find prime numbers.

Maybe even $2^{2^{2^{...2^{1}}-b}+a}-2^{2^{2^{...2^{1}}-b}+a}...$?(just a guess from the 2^p - 1 formula)

Edited by Unity+
##### Share on other sites

The Sieve of Eratosthenes is one such method.

To sieve, means to separate wanted elements from unwanted elements. In this case primes from non primes. A true formula would allow you to skip that step and jump straight to the desired Primes.

Now all the formulas I've seen would require knowledge of all the infinite primes prior to use. Wee bit of an issue there...

Edited by Endy0816
##### Share on other sites

I would think that prime numbers can be seem similarly to the numbers in pi.

Even if the decimals in pi are seemingly random, they are the result of a particular function.

$\pi=\sum_{n=0}^{\infty}\frac{4(-1)^{n+2}}{2n+1}$

I think this type of function can be applied to prime numbers, where recursion is what is needed to find prime numbers.

Maybe even $2^{2^{2^{...2^{1}}-b}+a}-2^{2^{2^{...2^{1}}-b}+a}...$?(just a guess from the 2^p - 1 formula)

There has been probably more work trying to find something like that for primes than any other part of mathematics. That pi formula - the Leibnitz is remarkably bad at doing pi. You need to run something like half a billion iterations to get 3.141,592,653,6

##### Share on other sites

I'm still not sure of the correct view here. There seem to be differences of opinion.

Acme - Have you nothing to contribute to this? Or are you just feeling irritable?

Yes & yes. Well, imatfaal restated my position so I didn't see the need to re-re-state my position.

Sure glad someguy on the internet POSSIBLY straightened things out.

That's the best you can do?

Possibly.

... Note the recent breakthrough on the twin prime problem for more evidence. ...

Citation on the breakthrough please, and a qualification on how it shows that Primes are not randomly distributed.

##### Share on other sites

Endy - There's no need to know any primes to do the prediction. Just the list of natural numbers.

Imatfaal - Are you suggesting that there is no function for producing the products of the natural numbers? I presume so, since if there is such a function then the primes are just the gaps. If there is a way to produce the products, then there is way to produce the primes. Is this not so?

Edited by PeterJ
##### Share on other sites

Endy - There's no need to know any primes to do the prediction. Just the list of natural numbers.

Imatfaal - Are you suggesting that there is no function for producing the products of the natural numbers? I presume so, since if there is such a function then the primes are just the gaps. If there is a way to produce the products, then there is way to produce the primes. Is this not so?

Not to dissuade Endy or imatfaal from making their own replies, but both these statements are meaningless to a mathematician in regard to Primes in spite of their use of mathematical terms. Moreover, the implication that every function has an inverse is false.

In post #13 I gave a quote by Euler and imatfaal repeated it in post #33. So starting again with that quote at Wolfram Mathworld, I quote some of their material germane to this discussion. The article also includes discussion of why 1 is not considered a Prime. Bolding and underlining in the below quote is mine.

...

Euler commented "Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the mind will never penetrate" (Havil 2003, p. 163). In a 1975 lecture, D. Zagier commented "There are two facts about the distribution of prime numbers of which I hope to convince you so overwhelmingly that they will be permanently engraved in your hearts. The first is that, despite their simple definition and role as the building blocks of the natural numbers, the prime numbers grow like weeds among the natural numbers, seeming to obey no other law than that of chance, and nobody can predict where the next one will sprout. The second fact is even more astonishing, for it states just the opposite: that the prime numbers exhibit stunning regularity, that there are laws governing their behavior, and that they obey these laws with almost military precision" (Havil 2003, p. 171).

...

Prime numbers can be generated by sieving processes (such as the sieve of Eratosthenes), and lucky numbers, which are also generated by sieving, appear to share some interesting asymptotic properties with the primes. Prime numbers satisfy many strange and wonderful properties. Although there exist explicit prime formulas (i.e., formulas which either generate primes for all values or else the nth prime as a function of n), they are contrived to such an extent that they are of little practical value. ...

Peoples' unease with these Prime features and characteristics -whether mathematicians or no- is inconsequential to the veracity of these features and characteristics, notwithstanding further whining.

##### Share on other sites

That quote exactly sums up the view that I do not understand. It's no use just repeating this claim and expecting me to understand it better each time.

As it states, the primes 'obey laws with military precision'. They only appear random from a certain perspective, which means, in my book, that they are not random.

In mathematics everybody knows what they mean when they say that the primes are randomly distributed, but tell this to a layman and he will completely misunderstand the primes. He will assume you mean random like a lottery.

##### Share on other sites

That quote exactly sums up the view that I do not understand. It's no use just repeating this claim and expecting me to understand it better each time.

As it states, the primes 'obey laws with military precision'. They only appear random from a certain perspective, which means, in my book, that they are not random.

In mathematics everybody knows what they mean when they say that the primes are randomly distributed, but tell this to a layman and he will completely misunderstand the primes. He will assume you mean random like a lottery.

So what if laypeople don't understand? Mathematicians do understand and as it's mathematicians that do math, that is all that matters.

##### Share on other sites

Ah, such arrogance.

As you seem to be unable to explain why we should call the primes random I'm not going to do so. If mathematicians want to call them random that's up to them. To me it is an unrigorous and confusing use of language and on the evidence of this discussion it is indefensible. Your quote said they are law-governed and that's good enough for me. if I come across a decent reason to change my mind I will, but there does not seem to be one, or not one you can explain.

Edited by PeterJ
##### Share on other sites

Ah, such arrogance.

As you seem to be unable to explain why we should call the primes random I'm not going to do so.

It's not that I or others can't explain it, it's that you can't understand it.

If mathematicians want to call them random that's up to them.

How gracious of you to grant your approval.

To me it is an unrigorous and confusing use of language and on the evidence of this discussion it is indefensible.

Again, why should it matter what you think? That's rhetorical; it doesn't matter.

Your quote said they are law-governed and that's good enough for me. if I come across a decent reason to change my mind I will, but there does not seem to be one, or not one you can explain.

In the big scheme of things, no one cares what you think.

##### Share on other sites

With the caveat that I'm nowhere near a a number theorist, my understanding is that the distribution of the primes is pseudorandom, i.e. it appears random but is actually deterministic.

Terence Tao actually gave a talk on this subject a few years ago, and his slides (which might be worth reading for anyone interested in this topic) can be found here: http://terrytao.files.wordpress.com/2009/07/primes1.pdf

Of course, that's Terry Tao, and other mathematicians may take a different view.

Edited by John
##### Share on other sites

This makes good sense to me John. I'd be happy with 'pseudorandom'. It's accurate and seems a perfect solution.

##### Share on other sites

With the caveat that I'm nowhere near a a number theorist, my understanding is that the distribution of the primes is pseudorandom, i.e. it appears random but is actually deterministic.

Terence Tao actually gave a talk on this subject a few years ago, and his slides (which might be worth reading for anyone interested in this topic) can be found here: http://terrytao.files.wordpress.com/2009/07/primes1.pdf

Of course, that's Terry Tao, and other mathematicians may take a different view.

Did you even read the slides you cite here? He repeats several times that there are no deterministic methods to generate primes.

This is exactly what has been said the last 40 posts or so. If someone thinks there is a deterministic way of generating primes, then present it. And then go and collect your Fields Medal or other similar prizes in mathematics. Because no one has found a deterministic method to date.

Then, the next slides in your link there go on to talk about some of the random and pseudomethod random methods that have shown some success. But none of them are anywhere near 100% accurate. Some show some promising leads into the idea, but again, if anyone actually could demonstrate something definitive, it would be a major advancement.

I get the appeal of looking for a pattern in the primes. The human mind craves patterns. But we can't claim a pattern unless it is demonstrated. This doesn't mean that we shouldn't keep looking or that even if the looking is never successful, that it wouldn't be worth it.

And so, with no definite pattern been proven, and no deterministic method available... what other words describes our current state of knowledge about the distribution of primes other than 'random'?

Edited by Bignose
##### Share on other sites

Did you even read the slides you cite here? He repeats several times that there are no deterministic methods to generate primes to our knowledge.

Just because one conclusion is not proven does not make other correct.

And so, with no definite pattern been proven, and no deterministic method available... what other words describes our current state of knowledge about the distribution of primes other than 'random'?

Our knowledge is unfinished, of course.

Edited by Unity+
##### Share on other sites

Just because one conclusion is not proven does not make other correct.

That is meaningless drivel.

Our knowledge is unfinished, of course.

A tautology.

##### Share on other sites

That is meaningless drivel.

How is it meaningless drivel? My point was even if one conclusion is not proven, does not make the other automatically correct(unless proven by theorem or where proper deduction is made). This would be a assumption, considered heresy in Mathematics(also please explain your accusations upon such statements when presenting the allegation. It makes for more proper discussion).

EDIT: Clarifying this, in this case even if there is no known deterministic function for primes does not mean that one does not exist. There is a reason why unsolved problems within Mathematics exist.

A tautology.

Nein, no it is not. It is upon a broader perspective that one conclusion being not proven making the other not automatically correct means that our knowledge of the subject is not complete and more research is needed.

EDIT: What you might have meant to say is a conclusion based upon a viable argument.

Edited by Unity+
##### Share on other sites

How is it meaningless drivel?

Your implication was that Primes are not randomly distributed. That's drivel of the meaningless kind.

My point was even if one conclusion is not proven, does not make the other automatically correct(unless proven by theorem or where proper deduction is made). This would be a assumption, considered heresy in Mathematics(also please explain your accusations upon such statements when presenting the allegation. It makes for more proper discussion).

Please don't presume to instruct me on how to discuss things. As I told Peter, the lack is your understanding; not my explication.

Nein, no it is not. It is upon a broader perspective that one conclusion being not proven making the other not automatically correct means that our knowledge of the subject is not complete and more research is needed.

Ja, yes it is.

tau·tol·o·gy (tô-tl-j)

n. pl. tau·tol·o·gies

1.

a. Needless repetition of the same sense in different words; redundancy.

b. An instance of such repetition.

2. Logic An empty or vacuous statement composed of simpler statements in a fashion that makes it logically true whether the simpler statements are factually true or false; for example, the statement Either it will rain tomorrow or it will not rain tomorrow.

EDIT: What you might have meant to say is a conclusion based upon a viable argument.

No.

I see someguy1 is banned so there certainly will be no citation that I asked him for on the Twin-Prime breakthrough he invoked. But as John mentioned Terrence Tao and Terrence was a part of the team working on that breakthrough I will provide my own citation. NOTE!: That work neither proves the Twin-Prime Conjecture nor does it show Primes are anything but randomly distributed. I'm a little pressed for time so I will just give a link for now and save quoting the pertinent parts for later.

## Create an account

Register a new account