Popular in last 30 days

Saturday, June 6, 2020

Project Euler


In response to reading my blog, a friend suggested that I join Project Euler. The site has over 700 problems to challenge its members by solving mathematical problems using programming. The group just crossed over one million members this year. 

As a fan of Grant Sanderson's 3Blue1Brown site and his many videos, I took his suggestion of improving my mathematical skill by learning new programming. It's been over 25 years since I did any serious programming, so my skills are rusty and outdated. I've been learning Python and slowly I've been able to solve some of the Euler Project challenges.



Here's an example of a problem from Project Euler

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.


I gravitated toward this problem because one of my first posts on this blog dealt with Pythagorean Triples. I used the tip posted to get a head start in finding the desired triplet of (200, 375, 425). Achieving the correct answer was good reinforcement of Grant Sanderson's advice to learn new programming skills.

Monday, June 1, 2020

How Rare is That Dollar?


The one-dollar bill shown in the photo is somewhat rare. Not so rare that it is worth more than one US dollar, but rare from the perspective of its serial number. That fact may seem surprising. At first glance, the serial number 29573801 doesn't appear extraordinary in any way; it looks just like one of the random 100,000,000 possible serial numbers possible in the 8-digit sequence. You'll see why it is rare after reading the following challenge.

In a prior post, I described a friendly bar bet in which you could easily estimate the number of prime numbers found in a range between two given numbers. A good friend was disappointed with the bar bet because most of his drinking friends don't know what a prime number is. So I'm offering him a new challenge to try.

Ask your friend to take the first dollar bill out of his wallet or billfold. Without  either of you looking at the serial number, he should place it on bar with his hand covering it. Now offer him $10 if the serial number has no repeated digits; if it doesn't, you win the bill. The bill in the photo would be a winner for your friend. Its serial number of 29573801 has no repeated digits. 

The wager is heavily weighted in favor of you. Only about 1 in 55 bills will have a serial number with no repeated digits. 

To see why this occurs so infrequently, consider the specific bill pictured in the photo. Of the digits 0 through 9, it is missing 4 and 6. Let's first calculate the probability that a given bill is missing the digits 4 and 6 and doesn't repeat any of the numbers. Moving through the serial number one place at a time, to meet this criteria, the first digit can be any number except 4 or 6. That leaves 8 digits out of 10. So the probability of getting through the first digit is 8/10. Now, moving to the second digit of the serial number, we need the probability that it is not a 4, 6 or a repeat of the first digit. That leaves 7 digits, so our probability of making it through the first two digits is 8/10 x 7/10. Continuing with all the remaining serial number's digits we find a probability of 8/10 x 7/10 x 6/104 x 5/10 x 4/10 x 3/10 x 2/10 x 1/10 which equals 40320/100,000,000 = .0004032. Next we have to adjust this probability because it was for the very specific case of a bill having no repeated digits and no 4 or 6. There are a total of 45 combinations of the two excluded digits so our final probability is .000432 x 45 = 0.18144 or roughly 1 in 55.

Saturday, May 30, 2020

Counting Prime Numbers - Win a Bar Bet

(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).

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.

Thursday, May 28, 2020

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’ = A2/C and B’ = B2/C.

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

C2 = A2 + B2.

The above proof of the Pythagorean Theorem used the trigonometric functions to derive the terms of A2 and B2. 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 sin2(a) and B’ = C cos2(a).

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

C = A’ + B’

C = C sin2(a) + C cos2(a)

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

1 = sin2(a) + cos2(a)


Tuesday, May 26, 2020

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.

Monday, May 25, 2020

Pi - How Many Digits are Really Needed?


A prior post showed how to estimate pi using random numbers. The spreadsheet linked to the post can estimate pi correctly to about 3 places; however, since each set of random numbers is different, the results will vary. Readers are encouraged to extend the spreadsheet beyond 1000 random numbers to improve the accuracy of the estimation. 

Pi taken out to 50 decimal places is:
3.14159265358979323846264338327950288419716939937510...

Princeton University has a post where the digits of pi are listed to 10 million places. Beyond 100 places does not provided much immediate value. Just using pi to the 50 places listed above, one could calculate the circumference of the observable university to an accuracy smaller than the diameter of a single hydrogen atom. Readers are challenged to verify given that the estimate of the diameter of the observable universe is 8.8 x 10^26 m and the size of a hydrogen atom is about 1 angstrom (1/10,000,000,000 m).

For simple estimations, consider the following approximations and their relative error:

Approximation     Relative Error
3                            .045
22/7                       .0004
355/113                 .00000008

Sunday, May 24, 2020

Using Random Numbers to Estimate Pi


A friend recently asked that I post something about the mathematical constant, pi. It is the ratio of a circle's circumference to it diameter. To fifty digits, pi is 

3.14159265358979323846264338327950288419716939937510...

There have been many methods established for calculating pi. One of the more interesting methods is derived from Euler's solution to the zeta function:

Euler showed that this function, in its limit, is:

This result has been used in number theory to establish the probability (P) of two random numbers being relatively prime (having no common factors greater than 1) is approximately:

Now, if we generate a large number of pairs of random numbers, we can count how many are relatively prime and then use the proportion to estimate pi using the formula:
I wrote a Google Sheet to make this approximation using 1000 pairs of random numbers. A link to this sheet is here and you can try for yourself. To refresh or change the 1000 pairs of numbers, simply update a blank cell in the sheet. In my first estimate, there were 612 of the 1000 pairs that were relatively prime yielding a proportion, P, of 0.612. This gave an approximation of pi of 3.13.



 

Friday, May 22, 2020

Speed Limits and the Fibonacci Series


(By Amateria1121 - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=31513168)

Travelers between the United States and Canada have to adjust to speed limits from miles per hour to kilometres per hour. Astute drivers usually learn a few quick approximations for converting between the two systems. Some common limits and their approximate conversions are shown below.

 km/h 30 50 80 130
 mile/h 20 30 50 80

The more precise conversion is 1 mile = 1.61 km or 1 km = 0.62 mile.

If the numbers above seem familiar, you may have noticed the conversion between the two measures is very close to the golden ratio or 1.618. This ratio has the property that it's inverse equals itself minus one: 1/1.618 = 0.618 = 1.618 -1.

The calculation for the golden ratio is:



To be clear, the relationship between kilometres and miles being near the golden ratio is only a coincidence.

A common approximation to the golden ratio is given by ratio of successive elements of the Fibonacci Series. The series begins as:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

Each entry of the series is the sum of the previous two entries. Beginning with 1/1, the ratio of successive elements of the series is:

1, 2, 1.5, 1.667, 1.6, 1.625, 1.615, 1.619, 1.618 

This ratio converges to the golden ratio of 1.6180339887...

Finally, return to the approximate kilometre-mile conversion table above, as we noted about successive entries of the Fibonacci series, each entry in both rows is the sum of the previous two entries.


Project Euler

In response to reading my blog, a friend suggested that I join Project Euler . The site has over 700 problems to challenge its members by so...