Almost Half Full!
Let
S
be the set of all natural numbers
n
such that there are exactly
⌊
2
n
⌋
prime numbers less than or equal to
n
.
What is the cardinality of the set S ?
Image Credit: Wikimedia Cardinality
The answer is 8.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
2 solutions
Prime counting theorem! Yay!.
The elements of S are S = { 1 , 2 , 4 , 6 , 8 , 9 , 1 1 , 1 3 } . For all natural numbers n higher than 13, the number of primes would be less ⌊ 2 n ⌋ .
Hence, the cardinality is 8 .
I missed 1 on my first attempt. :) It's interesting to note that if we change the condition to ⌊ k n ⌋ for any integer k > 2 the only element of S k will be 1 .
Another variation of your question is to make the inequality strict, i.e., just count the prime numbers less than n . Then the cardinality of S would be 1 1 , (I think).
Could you provide a proof,sir?
Maybe I've just gone stupid, but why do the odd ones count for this? Take 11: there are 5 primes less than or equal to it (2,3,5,7,11), which is clearly not equal to n/2. Is there some rounding going on?
Also, why doesn't 0 get counted? There aren't any primes less than or equal to it, so I'd think it would fit.
Log in to reply
The expression ⌊ 2 n ⌋ is the greatest integer function, which returns the greatest integer less than or equal to 2 n . So in the case of n = 1 1 we have
⌊ 2 n ⌋ = ⌊ 2 1 1 ⌋ = ⌊ 5 . 5 ⌋ = 5 ,
and there are indeed 5 primes less than or equal to 1 1 .
As for 0 , we are only looking for natural numbers, i.e., positive integers. If S were to be composed of non-negative integers then yes, 0 would have to be included.
By the prime number theorem, π ( n ) ≈ ln ( n ) n but ln ( n ) n < 2 n when n > e 2 , and by n = 2 0 , it is clear that ⌊ 2 n ⌋ ≫ ln ( n ) n . Therefore we need only check the integers from 1 to 2 0 . Doing so gives the set S = { 1 , 2 , 4 , 6 , 8 , 9 , 1 1 , 1 3 } with a cardinality of 8 .