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

Postby juststrange » Tue Jul 29, 2008 4:51 pm UTC

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]

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

Re: Percentage of numbers that are prime

Postby jestingrabbit » Tue Jul 29, 2008 5:04 pm UTC

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
[math]\lim_{n\rightarrow\infty} \frac{\pi(n)\log(n)}{n} = 1.[/math]
Therefore, because log(n) goes to infinity as n goes to infinity,
[math]\lim_{n\rightarrow\infty} \frac{\pi(n)}{n} = 0[/math]
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.

User avatar
Xanthir
My HERO!!!
Posts: 5186
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Percentage of numbers that are prime

Postby Xanthir » Tue Jul 29, 2008 5:13 pm UTC

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)))

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

Re: Percentage of numbers that are prime

Postby z4lis » Tue Jul 29, 2008 5:18 pm UTC

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.

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

Re: Percentage of numbers that are prime

Postby gmalivuk » Tue Jul 29, 2008 6:10 pm UTC

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

Postby juststrange » Tue Jul 29, 2008 9:24 pm UTC

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.

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

Re: Percentage of numbers that are prime

Postby z4lis » Tue Jul 29, 2008 9:38 pm UTC

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.

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

Re: Percentage of numbers that are prime

Postby Torn Apart By Dingos » Tue Jul 29, 2008 10:21 pm UTC

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.

User avatar
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

Postby skeptical scientist » Tue Jul 29, 2008 10:39 pm UTC

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

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

Re: Percentage of numbers that are prime

Postby z4lis » Tue Jul 29, 2008 11:51 pm UTC

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.

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

Re: Percentage of numbers that are prime

Postby NathanielJ » Wed Jul 30, 2008 12:02 am UTC

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

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

Re: Percentage of numbers that are prime

Postby z4lis » Wed Jul 30, 2008 12:50 am UTC

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

Postby juststrange » Wed Jul 30, 2008 1:19 am UTC

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?

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

Re: Percentage of numbers that are prime

Postby NathanielJ » Wed Jul 30, 2008 1:56 am UTC

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

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

Re: Percentage of numbers that are prime

Postby Torn Apart By Dingos » Wed Jul 30, 2008 10:18 am UTC

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.

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

Re: Percentage of numbers that are prime

Postby z4lis » Wed Jul 30, 2008 4:20 pm UTC

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

Postby Buttons » Wed Jul 30, 2008 4:43 pm UTC

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

Postby Aldarion » Wed Jul 30, 2008 4:50 pm UTC

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.

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

Re: Percentage of numbers that are prime

Postby chickendude » Wed Jul 30, 2008 4:59 pm UTC

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%

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

Re: Percentage of numbers that are prime

Postby z4lis » Wed Jul 30, 2008 5:11 pm UTC

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.

User avatar
MartianInvader
Posts: 757
Joined: Sat Oct 27, 2007 5:51 pm UTC

Re: Percentage of numbers that are prime

Postby MartianInvader » Wed Jul 30, 2008 5:18 pm UTC

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!

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

Re: Percentage of numbers that are prime

Postby Macbi » Wed Jul 30, 2008 5:26 pm UTC

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.

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

Re: Percentage of numbers that are prime

Postby jestingrabbit » Wed Jul 30, 2008 6:33 pm UTC

MartianInvader wrote:
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.

User avatar
MartianInvader
Posts: 757
Joined: Sat Oct 27, 2007 5:51 pm UTC

Re: Percentage of numbers that are prime

Postby MartianInvader » Wed Jul 30, 2008 8:49 pm UTC

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!

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

Re: Percentage of numbers that are prime

Postby Frimble » Wed Jul 30, 2008 9:06 pm UTC

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: 599
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Percentage of numbers that are prime

Postby Cauchy » Wed Jul 30, 2008 9:25 pm UTC

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

Postby Token » Wed Jul 30, 2008 9:32 pm UTC

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

Postby juststrange » Thu Jul 31, 2008 1:57 am UTC

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

Postby Spacemoss » Fri Apr 28, 2017 5:56 am UTC

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

User avatar
Eebster the Great
Posts: 2576
Joined: Mon Nov 10, 2008 12:58 am UTC

Re: Percentage of numbers that are prime

Postby Eebster the Great » Sat Apr 29, 2017 9:57 am UTC

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

Postby Spacemoss » Mon May 01, 2017 1:32 am UTC

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: 3064
Joined: Mon May 10, 2010 1:53 am UTC

Re: Percentage of numbers that are prime

Postby elasto » Sat May 06, 2017 11:30 pm UTC

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

Postby Spacemoss » Sun May 07, 2017 6:59 am UTC

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.

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

Re: Percentage of numbers that are prime

Postby gmalivuk » Sun May 07, 2017 12:57 pm UTC

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

Postby ppragman » Mon May 08, 2017 7:21 am UTC

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.

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

Re: Percentage of numbers that are prime

Postby gmalivuk » Mon May 08, 2017 11:54 am UTC

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

Postby Spacemoss » Mon May 22, 2017 11:33 pm UTC

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,
m1.JPG

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.
m2.JPG

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

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:
m4.JPG

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,
m5.JPG

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

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.

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

Re: Percentage of numbers that are prime

Postby gmalivuk » Tue May 23, 2017 1:52 am UTC

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)


Return to “Mathematics”

Who is online

Users browsing this forum: Baidu [Spider] and 4 guests