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.

Trigonometric Proof of Pythagorean Theorem

This proof is similar to Bhaskara's second proof, but at the end we also derive an important trigonometric identity. In the diagram, A, B, C are the lengths of the sides of a right triangle. The lower case, a, represents the angle opposite of side A.

From the definitions of the common trigonometric functions of sin(a) and cos(a), sin(a) = A/C and cos(a) = B/C. These two equations can be rewritten as A = C sin(a) and B = C cos(a).

On the hypotenuse side of the triangle, C can be broken into two sub-lengths, A’ and B’, which represent the projection of sides A and B, respectively, onto side C.

From the similar triangles that are formed, sin(a) = A’/A and cos(b) = B’/B. These two equations can be rewritten as A’ = A sin(a) and B’ = B cos(a).

Substituting for sin(a) and cos(b), A’= A (A/C) and B’ = B (B/C) or A’ = A²/C and B’ = B²/C.

Given that side C = A’ + B’, we get C = A²/C and B’ = B²/C. Multiplying both sides by C, we now derive the Pythagorean Theorem:

C² = A² + B².

The above proof of the Pythagorean Theorem used the trigonometric functions to derive the terms of A² and B². Alternatively, we can keep the sin(a) and cos(a) functions to show another important identity. Returning to the terms for A’ and B’, we can also express these two lengths as A’ = A sin(a) and B’ = B cos(a). Substituting for A and B in these two equations, A’ = C sin(a) sin(a) and B’ = C cos(a) cos(a). Trigonometric convention allows these terms to be stated as A’ = C sin²(a) and B’ = C cos²(a).

Substituting these last two equations into the relationship of side C being the sum of A’ and B’,

C = A’ + B’

C = C sin²(a) + C cos²(a)

Next divide both sides of the equation by C, we now have an important trigonometric identity:

1 = sin²(a) + cos²(a)

Find Your Birthday or Phone Number in Pi

Princeton University has a site with the mathematical constant, pi, listed to 10 million digits. Readers are invited to search/find their phone number or other favorite numerical sequence in pi. I found my phone number - 7 digits, not 10-digit number, early in the the full sequence.

Tests of random numbers look for that n-digit length of numerical sequences are found with equal frequency in a sufficiently long sequence. I found my 7-digit phone number, but not unexpectedly, not my full 10-digit number, in the listing of pi. My 7-digit phone number represents one of 10 million listings so I wasn't surprised when my 7-digit number showed up. With a listing of pi's digits to more digits, I might find my full 10-digit phone number.

To try this exercise for yourself, go to the Princeton website linked above, and use your browser's "find on this page" tool to enter the numerical sequence of your choice. For my example, I used Microsoft Edge and the "find" tool is Control-F. Matching sequences on the page are highlighted.