## Percentage of numbers that are prime

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

juststrange
Posts: 296
Joined: Wed Jul 23, 2008 3:57 pm UTC

### Percentage of numbers that are prime

Prime numbers have interested me for years, as they are so hard to pattern. At work at the moment, but the thought has struck me, why look for primes, why not look for numbers that aren't prime instead. Its come to my realization that the percentage of non-prime numbers (or if you subtract from one, primes) is mapped by a series, based on why they are not prime. Hence, prime numbers themselves describe the percentage of them. Half of all numbers are non-prime because they are divisible by 2. One third of all numbers are non-prime because they are divisible by 3. But half of these were already account for by the first step. One fifth are not prime because of five... etc, etc.

Basically, it forms a series, which I hold is increasing because you're always adding postives, and is bounded by 1, because it is a percentage. So its convergent, but to what (not 1, because then there would be no prime numbers)? Can anyone push this a bit further? Work has my brain fried at the moment.

[imath]( (1/2) + ((1/2)*(1/3)) + ((1/2)*(2/3)*(1/5)) + .......)[/imath]

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5965
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Percentage of numbers that are prime

If you let [imath]\pi(n)[/imath] be the number of primes less than or equal to n, then the prime number theorem tells us that
$\lim_{n\rightarrow\infty} \frac{\pi(n)\log(n)}{n} = 1.$
Therefore, because log(n) goes to infinity as n goes to infinity,
$\lim_{n\rightarrow\infty} \frac{\pi(n)}{n} = 0$
otherwise the previous limit would also be infinity. That is, the assymptotic density of primes (or in your language, the percentage of primes) is 0. This doesn't mean that there aren't any: the assymptotic density of perfect squares is 0, the assymptotic density of whole number powers of 2 is 0 etc and these sets certainly have elements in them. The elements just get more sparse as you consider larger and larger numbers.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Xanthir
My HERO!!!
Posts: 5284
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Percentage of numbers that are prime

Gauss conjectured that the density of primes less than a sufficiently large n could be estimated by 1/ln(n), and that the percentage error of this estimate would always decrease. He was later proven correct on this (though the magnitude of the error increases without bound, it does so more slowly than the number of primes increases, so that percent error always decreases).

So, pretending for a moment that we can do intuitive math with infinity, we see that the density of primes over the entire set of positive integers is 1/ln(inf), which reduces to 1/inf, which reduces to 0. For a more correct treatment, use limits as jestingrabbit does. They give the same answer.

jesting's argument is correct as well. Given any two series, one of which always increases slower than the other, the ratio of the slower to the faster will always approach 0 in the limit.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

### Re: Percentage of numbers that are prime

Yes, 1/ln(x) is an estimate for the density of primes, but I've been playing with what the OP is describing for months, and the line whose slope is produced by (1-the series) hugs 1/ln(x) very well. Unfortunately, I could only calculate it up to about 53 before my poor TI-83+'s memory gave out on me.
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.

gmalivuk
GNU Terry Pratchett
Posts: 26356
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: Percentage of numbers that are prime

juststrange wrote:So its convergent, but to what (not 1, because then there would be no prime numbers)?

That's your error. It is convergent to 1, but there are still primes. Infinitely many, in fact, just like there are infinitely many powers of 2 despite the fact that "most" integers aren't integer powers of two.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

juststrange
Posts: 296
Joined: Wed Jul 23, 2008 3:57 pm UTC

### Re: Percentage of numbers that are prime

Thank you all for the input so far. I was an engineering major with a math minor, and the real analysis class I took sparked my interest. Its good to finally have a place where I feel like I can get intelligent answers.

Edit: I have since remembered that being convergent to a number in no way means it will ever attain that value.
Last edited by juststrange on Tue Jul 29, 2008 10:08 pm UTC, edited 1 time in total.

z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

### Re: Percentage of numbers that are prime

So, pretending for a moment that we can do intuitive math with infinity, we see that the density of primes over the entire set of positive integers is 1/ln(inf), which reduces to 1/inf, which reduces to 0. For a more correct treatment, use limits as jestingrabbit does. They give the same answer.

I seem to recall that the 1/ln(x) estimate only estimated the density of primes "near" x.
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.

Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

### Re: Percentage of numbers that are prime

juststrange wrote:Edit: I have since remembered that being convergent to a number in no way means it will ever attain that value.

That's not what's going on here. The percentage of primes is 0 because there are so few primes that they wouldn't make up some percentage x of the natural numbers for any x>0. For example, what percentage of natural numbers are equal to 1? There's only one such number, but infinitely many natural numbers, so informally, we can say that the percentage is [imath]"1/\infty"=0[/imath]. Formally, the asymptotic density is the limit as n tends to infinity of (# of integers [imath]\leq n[/imath] that are equal to 1)/n = 1/n, the limit of which is 0.

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

### Re: Percentage of numbers that are prime

Torn Apart By Dingos wrote:
juststrange wrote:Edit: I have since remembered that being convergent to a number in no way means it will ever attain that value.

That's not what's going on here.

That's totally what's going on here. The limit of the percentage of the first n numbers which are prime is 0, but the percentage never actually becomes 0 for n>1.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

### Re: Percentage of numbers that are prime

So, from the prime number theorem, we can conclude that the above sum is zero?

That is, the sum of the inverses of the primes, minus the inverses of the products of two primes that do not repeat primes (i.e. 2(2) and 5(5) would not be included), plus such products of three primes, minus such products of four primes, on and on is zero.
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.

NathanielJ
Posts: 882
Joined: Sun Jan 13, 2008 9:04 pm UTC

### Re: Percentage of numbers that are prime

z4lis wrote:So, from the prime number theorem, we can conclude that the above sum is zero?

That is, the sum of the inverses of the primes, minus the inverses of the products of two primes that do not repeat primes (i.e. 2(2) and 5(5) would not be included), plus such products of three primes, minus such products of four primes, on and on is zero.

The sum in the original post must be equal to 1. The sum you described, if I'm reading it right, is at best conditionally convergent because the sum of the inverses of the primes diverges.
Homepage: http://www.njohnston.ca
Conway's Game of Life: http://www.conwaylife.com

z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

### Re: Percentage of numbers that are prime

NathanielJ wrote:
The sum in the original post must be equal to 1. The sum you described, if I'm reading it right, is at best conditionally convergent because the sum of the inverses of the primes diverges.

Yes, one. The sum in original post is the sum I described.
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.

juststrange
Posts: 296
Joined: Wed Jul 23, 2008 3:57 pm UTC

### Re: Percentage of numbers that are prime

z4lis wrote:the sum of the inverses of the primes diverges.

Is this true? I understand that the harmonic series diverges, as do 1/2n etc, as they are just fractional multiples of the harmonic series. How could one prove this, given the spacing of odd numbers. Prime number theory combined with the fact that a harmonic series is divergent?

NathanielJ
Posts: 882
Joined: Sun Jan 13, 2008 9:04 pm UTC

### Re: Percentage of numbers that are prime

juststrange wrote:
z4lis wrote:the sum of the inverses of the primes diverges.

Is this true? I understand that the harmonic series diverges, as do 1/2n etc, as they are just fractional multiples of the harmonic series. How could one prove this, given the spacing of odd numbers. Prime number theory combined with the fact that a harmonic series is divergent?

There are four proofs provided here: http://en.wikipedia.org/wiki/Proof_that_the_sum_of_the_reciprocals_of_the_primes_diverges

The second proof is probably the easiest to accept without any prior prime number theory knowledge, while the fourth proof is the shortest/simplest, but of course relies a LOT on prime number theory.
Homepage: http://www.njohnston.ca
Conway's Game of Life: http://www.conwaylife.com

Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

### Re: Percentage of numbers that are prime

skeptical scientist wrote:
Torn Apart By Dingos wrote:
juststrange wrote:Edit: I have since remembered that being convergent to a number in no way means it will ever attain that value.

That's not what's going on here.

That's totally what's going on here. The limit of the percentage of the first n numbers which are prime is 0, but the percentage never actually becomes 0 for n>1.
Obviously, or otherwise all but finitely many terms would be 0. I took his comment as an explanation of why 100% of something needn't be all of it, somewhat like the "argument" that 0.999... only "approaches" 1 but doesn't equal it. But I see where you're coming from and I may have misinterpreted it.

z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

### Re: Percentage of numbers that are prime

This little snag has more to do with my ignorance of the mathematics of infinite series. Basically, the series is the above. (Not the OP's series, which I just realized is not mine because it lacks the subtraction terms. I think he meant to put up mine since he talks about the subtraction.) Edit: actually, our series are different, but describe the same thing.

1. We can see that, in constructing the series for simply 2, and then 3, and then 5, and then on for any prime number, the series will stay safely snuggled between 0 and 1. For instance, the first value we get is 1/2. The next is 1/2 + 1/3 - 1/6. Then 1/2 + 1/3 + 1/5 - 1/(2*3) - 1/(2*5) - 1/(3*5) + 1/(2*3*5). We can actually just give a recursive means of finding the value for the next prime. If a is the previous value for the pth prime, and p' is the next prime, then the next value is a' = (1/p') - a([1/p']-1). (Please check this!) We are all sort of assuming that, since this is indeed a measure of probability, it lies between 0 and 1 for all primes. It, at the very least, is always positive, because our first number, 1/2, is positive. With a little induction, we see that they all are.

2. However, look at it on an infinite scale. (1/2 + 1/3 + 1/5 + ...) - (1/(2*3) + 1/(2*5) + ... + 1/(3*5) + ...) + (1/(2*3*5) + 1/(2*3*7) + ... ) - ...

We will group each set of sums together in pairs; group each positive sum with the negative one that follows it. In the first case, we have 1/2 + 1/3 + 1/5 + ... and 1/(2*3) + 1/(2*5) + ... + 1/(3*5) + .... My issue: we can factor out every inverse prime from the second, as follows: 1/(2*3) + 1/(2*5) + ... + 1/(3*5) + ... = (1/2)(1/3 + 1/5 + 1/7 + ...) + (1/3)(1/5 + 1/7 + ...) + (1/5)(1/7 + 1/11 + 1/13 + ...) + .... Note that each of the series in the right hand expression are not convergent. Comparing the new expression (the one on the right of the previous equation) to the expression 1/2 + 1/3 + 1/5 + ..., we see that the second one is much larger than the first, since the latter multiplies every term of the former by a sum that does not converge. This means that 0 > (1/2 + 1/3 + 1/5 + ...) - (1/(2*3) + 1/(2*5) + ... + 1/(3*5) + ...). More craziness happens when you realize that a similar procedure can be done for every pair of sums. The difference of the sum of the inverses with 3 prime terms minus the sum of the inverses with 4 prime terms is also less than 0. And so on for every pair. Now we sum up a set of numbers all less than zero, and our result is less than zero. But we assumed above that we would get a number between 0 and 1, and we know it is always positive. What's the problem with what I've done here?

The only issue I see is that I am claiming that one convergent series is "less" than another, which might not be acceptable. Perhaps what I've done with the series (the rearranging and factoring) is also either completely wrong (please let me know if it is) or simply not acceptable.
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.

Buttons
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

### Re: Percentage of numbers that are prime

The issue is what NathanielJ said: your series is at best conditionally convergent. That means that if it does indeed converge, then what it converges to depends on the order in which you add stuff, which you haven't clearly defined. By rearranging the order of the terms in a conditionally convergent series, you can make it sum to any real number.

Aldarion
Posts: 133
Joined: Thu Jul 19, 2007 7:00 pm UTC

### Re: Percentage of numbers that are prime

Regarding the subject, I think this site might interest you: http://members.aol.com/Scirealm/PrimeSieve.html
The author, John Wilson, is basically abusing the sieve of Erathostenes to prove that
>80% of all whole numbers are not prime

Then he proceeds to use the same method to - hang on - prove the Twin Prime conjecture!
You are invited to try and make sense out of his "proof" here: http://members.aol.com/Scirealm/TwinPrimes.html
I'm not good, I'm not nice, I'm just right.

chickendude
Posts: 33
Joined: Fri Jun 15, 2007 12:48 am UTC
Location: Massachusetts
Contact:

### Re: Percentage of numbers that are prime

Isn't that first one pretty trivial?

Especially since the percentage is asymptotically approaching 100%, it's no big deal to show that it is larger than 80%

z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

### Re: Percentage of numbers that are prime

I played with sieve analysis to solve the twin prime conjecture. I think the best I did was proving that there are an infinite amount of pairs such that one is prime and one is a coprime. Maybe not that much.
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.

Posts: 784
Joined: Sat Oct 27, 2007 5:51 pm UTC

### Re: Percentage of numbers that are prime

Buttons wrote:The issue is what NathanielJ said: your series is at best conditionally convergent. That means that if it does indeed converge, then what it converges to depends on the order in which you add stuff, which you haven't clearly defined. By rearranging the order of the terms in a conditionally convergent series, you can make it sum to any real number.

Or, as in your case, you can make it converge to infinity.
Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!

Macbi
Posts: 941
Joined: Mon Apr 09, 2007 8:32 am UTC
Location: UKvia

### Re: Percentage of numbers that are prime

z4lis wrote:I played with sieve analysis to solve the twin prime conjecture. I think the best I did was proving that there are an infinite amount of pairs such that one is prime and one is a coprime. Maybe not that much.

Coprime to what? If you mean to the prime then that's highly trivial.
Indigo is a lie.
Which idiot decided that websites can't go within 4cm of the edge of the screen?
There should be a null word, for the question "Is anybody there?" and to see if microphones are on.

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5965
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Percentage of numbers that are prime

Buttons wrote:The issue is what NathanielJ said: your series is at best conditionally convergent. That means that if it does indeed converge, then what it converges to depends on the order in which you add stuff, which you haven't clearly defined. By rearranging the order of the terms in a conditionally convergent series, you can make it sum to any real number.

Or, as in your case, you can make it converge to infinity.

This is always the case.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Posts: 784
Joined: Sat Oct 27, 2007 5:51 pm UTC

### Re: Percentage of numbers that are prime

To clarify: It is always the case that you CAN rearrange terms to make it go to infinity, which is what your particular arrangement did. Not every arrangement causes the series to go to infinity, obviously (e.g. the original convergent arrangement). I just meant to take the statement "you can make it go to any real number" and append on "or make it go to infinity, which is what you did." But yeah, I think everyone understands now
Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!

Frimble
Posts: 480
Joined: Thu Apr 10, 2008 6:57 pm UTC
Location: UK

### Re: Percentage of numbers that are prime

Why are we using limits to determine the percentage of integers that are prime, rather than looking at the cardinal value of infinity which describes the number of primes? Surely, in the same way the number of integers is equal to the number of even numbers, the number of primes must also be equal to the number of integers.

If on the other hand you are talking about the percentage of real numbers that are prime, then the answer is fairly obviously 0.
"Absolute precision buys the freedom to dream meaningfully." - Donal O' Shea: The Poincaré Conjecture.
"We need a reality check here. Roll a D20." - Algernon the Radish
"Should I marry W? Not unless she tells me what the other letters in her name are" Woody Allen.

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

### Re: Percentage of numbers that are prime

Frimble wrote:Why are we using limits to determine the percentage of integers that are prime, rather than looking at the cardinal value of infinity which describes the number of primes? Surely, in the same way the number of integers is equal to the number of even numbers, the number of primes must also be equal to the number of integers.

Because that's not very useful in this context. For instance, while there are the same number of integers as even integers, we'd like to be able to say that, for instance, as a subset of the integers, the even integers take up "1/2" of the integers. The limit of density lets us do this.

Of course, we could always use the Schnirelmann density, but that doesn't return a very interesting answer for the primes, regardless of how dense they may be.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

### Re: Percentage of numbers that are prime

Frimble wrote:Why are we using limits to determine the percentage of integers that are prime, rather than looking at the cardinal value of infinity which describes the number of primes? Surely, in the same way the number of integers is equal to the number of even numbers, the number of primes must also be equal to the number of integers.

Further to the above... follow that reasoning to it's conclusion. The set of integers and set of primes both have cardinality [imath]\aleph_0[/imath]. Does that mean 100% of integers are prime?
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

juststrange
Posts: 296
Joined: Wed Jul 23, 2008 3:57 pm UTC

### Re: Percentage of numbers that are prime

The original intent behind this thought experiment was to learn something about the "pattern" of primes. I figured this series would reveal something to me about the spacing of primes as the value got higher. I chose the series because I figured investigating non-primes was easier, and the information I wanted would effectively "fall out", of whatever conclusions I gained about non-primes. It seems this has strayed far from my original intentions, but I must say I am not disappointed with where it went.

Spacemoss
Posts: 13
Joined: Fri Jul 08, 2016 12:39 am UTC

### Re: Percentage of numbers that are prime

Here is the Exact Percentage, noting that the percentage is variable, in that the greater the number, the less % that are prime. There are many versions of this, some simpler than others, but here is the original one:

Define F(x) = Sum[(Cos(2*pi*x/k)-Cos(1/k)+Abs(Cos(2*pi*x/k)-Cos(1/k)))/(2*(1-Cos(1/k))),k=2..j] where j ≥ x
Then G(x) = (F(x)-1+Abs(F(x)-1))/2
Then H(x) = (1-G(x)+Abs(1-G(x)))/2
Then L(x) = 1-H(x)
Then Pi(x) = x-1-Sum[L(n),n=1..x]

Then the exact Percentage is Pi(x)/x

Eebster the Great
Posts: 2980
Joined: Mon Nov 10, 2008 12:58 am UTC

### Re: Percentage of numbers that are prime

Spacemoss wrote:Here is the Exact Percentage, noting that the percentage is variable, in that the greater the number, the less % that are prime. There are many versions of this, some simpler than others, but here is the original one:

Define F(x) = Sum[(Cos(2*pi*x/k)-Cos(1/k)+Abs(Cos(2*pi*x/k)-Cos(1/k)))/(2*(1-Cos(1/k))),k=2..j] where j ≥ x
Then G(x) = (F(x)-1+Abs(F(x)-1))/2
Then H(x) = (1-G(x)+Abs(1-G(x)))/2
Then L(x) = 1-H(x)
Then Pi(x) = x-1-Sum[L(n),n=1..x]

Then the exact Percentage is Pi(x)/x

Can you explain where you got this from? Unless I am misreading it, it appears that this gives an irrational value for all integers x, when obviously what is required is a rational value for all integers x.

Spacemoss
Posts: 13
Joined: Fri Jul 08, 2016 12:39 am UTC

### Re: Percentage of numbers that are prime

Hello Eebster the Great, thanks for the reply. I created this system of composite functions. You just start with F(x) and feed it itno g(x) and do on. You can do all the manipulations at once and just get the full expanded pi(x) at the end, but it's more intuitive in these steps when you see the accompanying graphs. Oh, and it outputs integers, unless I'm missing something I entered incorrectly.

I also posted in a similar thread, but neither quite captures the scope of the material I have. And, since I can now post links, I will make a proper post so anyone who wants to discuss the equations may do so. If it turns out, to better suit an existing thread, that's fine, but I suspect it merits its own space.

elasto
Posts: 3460
Joined: Mon May 10, 2010 1:53 am UTC

### Re: Percentage of numbers that are prime

Having read the facebook page, I could be wrong but it just seems like a really obfuscated sieve of Eratosthenes:

- Number buckets from 1-n
- Place a bean in every 2nd bucket
- Place a bean in every 3rd bucket
- Place a bean in every 4th bucket...

Now empty every bucket with only 1 bean for all composites, or every bucket with more than 1 bean for all primes (up to n) - and the percentage of primes can be calculated accordingly.

Spacemoss
Posts: 13
Joined: Fri Jul 08, 2016 12:39 am UTC

### Re: Percentage of numbers that are prime

Having read the facebook page, I could be wrong but it just seems like a really obfuscated sieve of Eratosthenes:

The difference is, until this point, no one showed how to use the sieve to show the exact distribution, or knew the exact distribution without brute forcing the next term, and no one had the exact percentage of primes in one single formula. Nor did they have the pattern in one formula. Nor did they see the exact relation to calculate the next prime versus testing for it. This puts it all in one formula, and opens the door to equivalency relations for the summation that did not exist previously. It is indeed a Sieve of Eratosthenes at some level, as all solutions to the prime pattern have that built in.

gmalivuk
GNU Terry Pratchett
Posts: 26356
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: Percentage of numbers that are prime

I'm sure others have put it all in one formula before, it just didn't gain traction because it's not useful. The sieve is brute forcing, and is one of the slowest ways to do anything with primes.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

ppragman
Posts: 2
Joined: Sun May 07, 2017 8:37 pm UTC

### Re: Percentage of numbers that are prime

I could be wrong here (hapless undergrad checking in), but the naturals and the primes can be put into a "one-to-one" correspondence with one another(infinitude of primes, and primes being a subset of \mathBB{N}), so they have the same cardinality - namely Aleph Nought, so to say "what percentage" of numbers are prime is kind of meaningless because the sets have the same "size" - they are both countably infinite. If I were a betting man, I'd bet that the ratio of primes to naturals is 1 because the sets have the same size.

gmalivuk
GNU Terry Pratchett
Posts: 26356
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: Percentage of numbers that are prime

ppragman wrote:I could be wrong here (hapless undergrad checking in), but the naturals and the primes can be put into a "one-to-one" correspondence with one another(infinitude of primes, and primes being a subset of \mathBB{N}), so they have the same cardinality - namely Aleph Nought, so to say "what percentage" of numbers are prime is kind of meaningless because the sets have the same "size" - they are both countably infinite. If I were a betting man, I'd bet that the ratio of primes to naturals is 1 because the sets have the same size.

You're not wrong about the number of primes but you are wrong about the question being meaningless.

For one thing, if it were meaningless to compare the sizes of equinumerous sets, then it would be meaningless to say a 2x2 square is four times the size of a 1x1 square, because the same number of points are in each.

And while we can't do quite the same thing with integers, it's common to ask what fraction of integers from 0 to N have some property, and then ask what happens to that fraction as N goes to infinity. In this way it is completely meaningful to say half of all integers are even, for example.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Spacemoss
Posts: 13
Joined: Fri Jul 08, 2016 12:39 am UTC

### Re: Percentage of numbers that are prime

gmalivuk wrote:The sieve is brute forcing, and is one of the slowest ways to do anything with primes.

When considering the speed at which primes are manipulated for usefulness, it's usually the case that a probabilistic primality testing method is faster than a deterministic primality proving method, and in that comparison the sieve will always be the slowest, in that it is the determined pattern of the primes from the get go. In one regard, a probabilistic method is useful because it is fast, while a deterministic method is useful because it is always correct. How then, is usefulness differently considered?
gmalivuk wrote:it just didn't gain traction because it's not useful.

Usefulness in math applications differs in nature from usefulness in pure math. While a formula in the realm of math application may be useful to get some calculation done, and lead to public traction, a formula in pure math may be useful because it shows a relationship that creates new applied formulas, and may be less known. It seems then, that deterministic, pure math concepts are useful for a slightly different reason.
gmalivuk wrote:I'm sure others have put it all in one formula before,

Hmm, any ideas who or where? I'd love to see. It's one thing to know how the sieve works, it's another to know how to use it spit out the distribution numerically. According to Wikipedia, this is their general take:
On their Prime number page they show a well quoted statement that,

which seems to counter what we know from the sieve. The sieve is the pattern, so why add the heir of mystery here? They go on to say no efficient formula for the n-th prime is known, but do not define efficiency in this case. Putting aside discussions of equation simplicity or efficiency they continue with 3 possibly useful and related formulae: one using Wilson's Theorem, one using a system of 9 Diophantine equations, and one using Mill's Wright theorem.

The formula I provide is more accessible than any of those. Next they go on to talk of the prime counting function here:

They say there are algorithms to do it faster than calculating primes, which is fine, but the method I show is a formula not an algorithm, and so it serves a different purpose. Furthermore, they say that the prime number theorem states that pi of n is approximately n over log n but never list it exactly? Why use an approximation when you have the original? Or at least, if the theorem is just about the approximation, one would think the actual formula would appear somewhere in the discussion. On their Prime Number Theorem page they show this:

which goes on to talk about the distribution approximately, with "bounds" on the counting function and "approximations" for the nth prime, but never give the actual function for the counting function or the nth prime. Mine does. Then on to,

we again see that its all about efficiency. And lastly they have:

which goes on to say the prime counting function is "of great interest", and that "more precise estimates" are now known. Yet they only ever speak of estimates without providing the exact thing.

In this regard, my formulae are concise, unique, and stand out amongst the provided equations by showing greater information captured in a more intuitive form. The equations are simple in nature, as equation simplicity is defined. That is, only composed of addition, subtraction, multiplication, and division operations. A such, they make a great addition to the field, and stand as a new starting point that could eventually be refined further into more efficient applied versions, some of which I have already offered.

gmalivuk
GNU Terry Pratchett
Posts: 26356
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: Percentage of numbers that are prime

All the interest is in formulas and algorithms that tell us something about primes *without* first needing to count all of them one by one.

What you've produced, if it's accurate, may be interesting to you, but it is not a groundbreaking new contribution to the field of number theory.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)