Does 2… n ALWAYS include a higher or equal PERCENTAGE of prime numbers tan does 2… 2n?
The number of prime numbers less than n is usually denoted by the prime number function π(x). So what you’re asking is whether
π(n)/n > π(2n)/(2n).
But it’s known that as n gets large, the ratio π(x)/x approaches 1/ln(x) (or, more formally, the limit as x goes to infinity of π(x) * ln(x)/x is 1.) This means that since
1/ln(n) > 1/ln(2n)
for all n (the natural logarithm is an increasing function), then this implies that for sufficiently large n, we have π(n)/n > π(2n)/(2n).
This isn’t a formal proof, and I suspect that it’s true for all n (not just all n above some particular threshold); but it shows why one would expect this result to be true.
For proof, you need not just the asymptotic behavior of π(x), but bounds on its worst cases. A convenient such inequality (corollary to the Prime Number Theorem for sufficiently large x) is
2x / ln (x+2) < 2π(x) < 2x / ln (x-4)
(I’ve multiplied by 2 throughout for reasons that will become apparent.) Since this holds for all sufficiently large x, we have also
2x / ln (2x+2) < π(2x) < 2x / ln (2x-4)
Clearly
ln (2x-4) > ln (x+2)
for sufficiently large x; this implies
2x / ln (2x-4) < 2x / ln (x+2)
which combines with the first inequalities for
π(2x) < 2x / ln (2x-4) < 2x / ln (x+2) < 2π(x)
or simply
π(2x) < 2π(x)
which answers OP’s question in the affirmative. For sufficiently large x.
The closest he can come to a violation, BYW, is x=4 since only half of {1,2,3,4} are prime, but fully half of {1,2,3,4,5,6,7,8} are prime.
If I understand, MikeS’s fine reply certainly makes it clear that, as numbers grow, the percentage of prime numbers in 2…n tends to get larger than the o the percentage of prime numbers in n…2n.
However, if I understand, this doesn’t quite prove that here is NO case in the lower numbers in which 2…2n has a greater percentage of prime number than does 2…n. (My question).
For example: If n is 10, the number of primes for 2…n and 2…2n is equal. (2…10 has four primes, 2.3.5.and 7. 2…20 has eight: 2.3.5.7.11.13.17.19.)
Perhaps if one goes up the numbers a bit one will find a single case where 2…n has a lower percentage of primes than does 2…2n.
The number of primes isn’t equal: one has 4 primes, the other has 8 primes.
I assume you mean to say the percentage of primes is equal. But that’s not true either:
The first one has 4/9 (approx 44.4%) primes.
The second has 8/19 (approx 42.1%) primes.
Ally Dweller writes:
“I assume you mean to say the percentage of primes is equal. But that’s not true either:
The first one has 4/9 (approx 44.4%) primes.
The second has 8/19 (approx 42.1%) primes.”
Steven Estes: But n is 10 and 2n is 20. So isn’t it 4/10 and 8/20?
Your original question was “Does 2… n ALWAYS include a higher or equal PERCENTAGE of prime numbers tan does 2… 2n?”
The sequence 2, 3, 4, 5, 6, 7, 8, 9, 10 has exactly 9 numbers in it. Count them.
Similarly, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 has exactly 19 numbers in it. Count them.
I hope this isn’t someone’s homework. I got the impression the OP actually wants π(x)/(x-1) > π(2x)/(2x-1) instead of π(x)/x > π(2x)/2x, not that it makes much difference. Once you have reasonable bounds for the prime-counting function, this should be straightforward analysis (as notes septimus). For example, if this is to be believed then for x > 598 we have
(x/log x)(1 + 0.992/log(x)) ≤ π(x) ≤ (x/log(x))( 1 + 1.2762/log(x)) .
So, to show that π(x)/(x-1) > π(2x)/(2x-1), or (π(x)/π(2x)) ⋅ ((2x-1)/(x-1)) > 1, start with
2π(x)/π(2x) ≥ ((2x/log x)(1 + 0.992/log(x))) / ((2x/log(2x))(1 + 1.2762/log(2x))
= (log(2x)/log(x))(1 + 0.992/log(x)) / (1 + 1.2762/log(2x))
= (1 + log 2/log x)(1 + 0.992 / log(x)) / (1 + 1.2762/log 2x)
> (1 + 1.685 / log x) / (1 + 1.2762 / log 2x)
but log(x) / 1.685 < log(2x) / 1.2762, so the final expression above is greater than 1.
In other words, we can check that π(x)/(x-1) > π(2x)/(2x-1) is true for all x greater than 600, say, and for small x just check it, assuming that x is integral since otherwise it’s not always true!
This is not homework and I am far from a mathematician. I am a seventy-six-year-old Professor Emeritus.
The answers given above are far moreeEncompassing, and imply proof, when all I want is a a SPECIFIC NUMBER
for whicvh n…2n has a lower percentage of prime numbers than does 2…n.
If you really mean n, …, 2n, take n=2: 2,3,4 has 66.7% primes, lower than {2} which has 100%
If you meant 2,…, n, same example.
If you meant “higher percentage” and not “lower percentage”, I don’t see how you can forego all proof, assuming the posters are correct and there is no counterexample; checking the statement for any specific number is not sufficient because there are infinitely many numbers.
Terribly sorry. My error.
I should have written:
"All I want is a a SPECIFIC NUMBER
for which n…2n has a HIGHER percentage of prime numbers than does 2…n.
DPRK wrote:
“If you meant “higher percentage” and not “lower percentage”, I don’t see how you can forego all proof, assuming the posters are correct and there is no counterexample…”
If DPRK is correct and the proofs demonstrate that there is no counter example, then, of course, he is correct that there is no answer yo my question.
However, my impression, perhaps incorrect, is that the proofs demonstrated that the prime numbers tend strongly to diminish, but NOT that there is no exception that would answer my question.
If there is an example that is, say, higher than a million,or if there is no excepton --counterexample-- then, of course, a computer test of all numbers to a million would prove nothing. But, if there i an example less than a million, a computer run would answer the question
The first formula in my #3 is a theorem that has been proved for all x > 54. If the theorem’s proof is correct then your question is answered.
I may not be competent to track down a proof (not behind a paywall) let alone understand it, but there are many similar theorems that have been around for decades. I strongly doubt that these proofs have all passed peer scrutiny if they were wrong.
It is known that many niceties of the primes are eventually violated, see for example Littlewood’s counterexample to the π(x) < li(x) conjecture — some large primes are more numerous than “expected.” It is known that there are no such primes (Littlewood’s counterexample) smaller than 10[sup]19[/sup] and they may not exist until 10[sup]316[/sup], but they do exist.
However the “violation” you seek is much more flagrant than Littlewood’s and … except for the near-exceptions at x=4 and x=10, impossibility has been proven.
If it helps, use my example of allowing x to be a non-integer: π(2.5) = 1 and 1/1.5 = 66%, but π(5) = 3 and 3/4 gives 75% ! I think that once x increases to 3 there are no further counterexamples, but I have not checked.
(Here π(x) is the number of primes less than or equal to x, but x is allowed to be any positive real number. )
ETA the Prime Number Theorem itself is not super “elementary” - I mean, even Gauss didn’t prove it - but if you are not afraid of a little analysis then you can follow such proofs. You should be interested in number theory, though, and remember some real and complex analysis.