Related to the thread, I had an idea a few weeks back. I assume everyone is familiar with counting the primes 2 to n linearry crossing out numbers and their multiples. But it's not a formula to give a specific number, only a process/algorythm. But what if we indirectly count the numbers "that would be crossed out" by a prime in the above process. I came up with a somewhat recursive formula.
Let's examine n = 100 case.
Each m number eliminates floor(n'/m) - 1, where n' is "the rest".
Let elim(m,n') := n' - floor(n'/m) - 1
The first m is 2, because 1 is irrelevant.
elim(2,100) = floor(100/2) - 1 = 100 - 50 - 1 = 49
The second m is 3, because it's not divisible by 2.
elim(3,49) =
The 49 remaining number are:
3,5,7,
9,11,13,
15,17,19,
21,23,25,
27,29,31,
33,35,37,
39,41,43,
45,47,49,
51,53,55,
57,59,61,
63,65,67,
69,71,73,
75,77,79,
81,83,85,
87,89,91,
93,95,97,
99
Note that every third is a multiplicate of 3.
elim(3,49) = 49 - floor(49/3) - 1 = 49 - 16 - 1 = 32
The third m is 5, because it's not divisible by either 2 or 3.
elim(5,32) = 32 - floor(32/5) - 1 = 32 - 6 - 1 = 25
The 32 remaining number are:
5,7,11,13,17,19,23,
25,29,31,
35,37,41,43,47,49,53,
55,59,61,
65,67,71,73,77,79,83,
85,89,91,
95,97
Even though it's not every 5th number that is eliminated by 5, the definition of elim holds.
The fourth m is 7, because it's not divisible by either 2 or 3 or 5.
elim(7,25) = 25 - floor(25/7) - 1 = 25 - 3 - 1 = 21
7,11,13,17,19,23,29,31,37,41,43,47,
49,53,59,61,67,71,73,
77,79,83,89,
91,97
Again, it's not every 7th number, but elim holds.
The fifth m is 11, because it's not divisible by either 2 or 3 or 5 or 7.
elim(11,21) = 21 - floor(21/11) - 1 = 19
11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97
At this point elim breaks, because 11 eliminates nothing. However note that all remaining numbers are primes, and we have passed sqrt(n).
Add the number of eliminators we have used (4).
21 + 4 = 25