The Sieve of Eratosthenes

Eratosthenes

Tonight I have been thinking about applications of the principle of inclusion-exclusion. The gist of it is how to determine how many elements are in the union of two finite sets. Ideally, you want to determine that number without examining every element. That is done by figuring out which elements need to be examined (the inclusion part) and which elements can be ignored (the exclusion part).

A wonderful example of applying the principle of inclusion-exclusion is "The Sieve of Eratosthenes" which is used to find all primes not exceeding a specified positive integer. At this point you might be thinking this is just an application of divide-and-conquer, and I agree. Simple concepts can be very powerful.

Consider that Eratosthenes lived between 276 and 194 B.C.E. He was born in Cyrene, a Greek colony west of Egypt. Eratosthenes tutored the son of King Ptolemy II and was the chief librarian at the famous library at Alexandria. His amazing feats of intellect includes measuring the size of the Earth. Carl Sagan mentions Eratosthenes in the 1980 mini series, Cosmos. He explains how Eratosthenes measured the Earth and it is amazing to think that with our modern tools a family can use these same methods to not only repeat the experiment but to prove that the Earth is [mostly] round as well.

Using Spatial Words Can Help Kids Be More Comfortable With STEM

I like the below news story:

The way you talk with your child can help them to understand science and math
https://wkow.com/news/top-stories/2018/12/24/the-way-you-talk-with-your-child-can-help-them-to-understand-science-and-math/

Although there are two points that I would like to consider:

1. I suspect that the additional time spent with your kids has a bigger impact than the subject matter.
2. The story focused on very little kids with concepts that they will almost definitely will pick up later if you don't introduce those ideas. However, if they are the last ones to learn those concepts then they might be embarrassed and will shy away from Science, Technology, Engineering, and Mathematics (STEM).

I know adults that would be hesitant about which way to turn an object if I said, "Please rotate that to the left." They definitely can figure it out but they are not comfortable with the language.

Of course, the same phrase, "rotate to the left," could mean something different to someone from a different part of the world but that consideration is about teaching to consider context.

You might be thinking that this is a silly little thing to put any thought into but imagine what it means to rotate an array to the left or right. Or to rotate a multidimensional array. You quickly start to get into college level computer science and mathematics. And we're still just talking about how to orientate your perspective.

Anyway, I like this story because at the heart of the news story is encouragement for parents to spend more time with their kids and to impart their knowledge.

Magic Square Corollary

The following definition for a Magic Square series is from the EDU-BLOG:

In recreational mathematics, a magic square of order ‘n’ is an arrangement of n2 numbers, usually distinct integers, in a square, such that the n numbers in all rows, all columns, and both diagonals sum to the same constant.  A normal magic square contains the integers from 1 to n2. The term “magic square” is also sometimes used to refer to any of various types of word square.

The constant sum in every row, column and diagonal is called the magic constant or magic sum, M. The magic constant of a normal magic square depends only on n and has the value 

Thus the magic square series is like this: 1, 5, 15, 34, 65, 111, 175, 260…

Often when I want to practice programing I'll write some code to calculate some interesting mathematical number or series. Recently I picked the magic square series. When I finished I noticed that for each order of magnitude beyond n = 20 there was a pattern.

Magic Square Corollary

for y = 0 to ∞

n	M(n)
20	4,010
200	4,000,100
2,000	4,000,001,000
20,000	4,000,000,010,000
...	...

This was done solely for the enjoyment of playing around with some numbers. I used Roger's Online Equation Editor to make the above equation image. Very handy tool.

Next I noticed that any value of n = 10, 20, 30, ..., 90 can have the above equation applied to it. For example, n = 10:

M(10) = 505

Split 505 at the two least significant digits. Maintain the order of the left half to get 500 and 5. Then apply those values on the left and right of the plus sign, as so:

M(n) = M(10 * 10^y) = 500*10^(3y)+5*10^y

M(100) = 500,050

M(1,000) = 500,000,500

...

M(90) = 364,545

M(n) = M(90 * 10^y) = 3,645*10^(3y)+45*10^y

M(900) = 364,500,450

M(9,000) = 364,500,004,500

...