Counting Prime Numbers

(Design vector created by freepik - www.freepik.com)

Imagine challenging a fellow mathematics fan to a friendly bar bet in which the person who best estimates the number of prime numbers found between a range of two given numbers wins a drink. Let your friend pick the first number and you will pick the second number. A list of prime numbers up to 10,000,000 is available here for you to check your answers. 

What do you have to know?

You won't have to remember lengthy lists of prime numbers to win your bet. You just have to remember two numbers: 165 and 72.

After your friend suggests the first number, add 165 to get the second number of the range. To get your estimate, round the top number of the range to the nearest power of ten. Divide 72 by the number of zeros in the rounded number and this will be your estimate. So if your friend suggests 1000 for the first number, you'll state the second number will be 1165. Rounding 1165 to the nearest power of ten is 1000. Dividing 72 by 3 - the number of zeros in 1000 - yields an estimate of 72/3 = 24.

Going to the above link, if we count the number of primes between 1000 and 1165, we find the following primes: 

1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093, 1097,1103,1109,1117,1123,1129,1151,1153,1163. The count of actual primes is 24, matching your estimate.

Here's another example. Your friend picks 1 as the starting number; you add 165 so the final number is 166. Rounding 166 to the nearest power of 10 is 100. Divide 72 by 2 (the number of zeros in 100) and your estimate is 36.

Referring to the link above the the primes between 1 and 166 are: 
2, 3, 5, 7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101, 103,107,109,113,127,131,137,139,149,151,157,163. The actual count is 38. Your estimate is still very close and probably closer than what your friend could estimate or count in a quick period of time.

How does this quick estimation work?

The key to this trick is the prime number theorem which states the number of primes less than a given number, n, is approximately: n/ln(n). Alternately, we can say the relative frequency of primes near n is 1/ln(n). Note: the prime-counting function is also discussed in another post: Math Vacation: The Frequency of Prime Numbers – The Prime Number Theorem (jamesmacmath.blogspot.com).

Our estimate used the nearest power of 10 as a starting point. Counting zeros in a number that is a power of ten is the same as taking the log(base 10) of that number. Log(100) = 2, Log(1000) = 3, Log(10000) = 4 etc. The prime number theorem uses ln(n). Converting from log(n) to ln(n) is a factor of 2.3.

The prime number theorem stated the relative frequency of primes near n is 1/ln(n), so our estimate for a range of 165 should be 165/ln(n). Converting from log(n) to ln(n), our estimate becomes 165/(2.3 log(n)) or approximately 72/log(n). The range of 165 was chosen so we would end up with 72 in the numerator. Since 72 is easily divisible by many numbers, your estimation task is a little easier. 

A prior post wrote about the "Rule of 72" for quick approximations of compound interest. Now you have 2 uses of the number 72 to make quick estimations.

Credit is given to Grant Sanderson's site, 3b1b, for inspiring this trick. More on the natural logarithm is given here by Grant: 

https://www.3blue1brown.com/videos-blog/what-makes-the-natural-log-natural-lockdown-math-ep-7.