HOW KIDS LEARN THE SIEVING PROCEDURE

Have the children write the numbers from 1 to (say) 211 on cards, one number to a card. Next, have them fix each successive card (for 1, 2, 3, etc.) such that it hangs on one or more strings or wires and can be flipped over to its blank side. Have a blackboard on hand upon which the children can, in chalk, "summarize their discoveries".

"Let the Sieving begin!"

  1. The children start by sieving by flipping over the 1-card. We explaining that 1 is the additive and multiplicative building block or gnomon of all of our numbers. They may agree that 1 makes a very trivial kind of row. Then we turn to the number on the next card, 2. We guide the children in discovering that 2 bottle caps can build only one row (except in the trivial sense of a column of ones which rotates into a single row). So 2 is a row number.

  2. We guide the children in discovering that 2 is the gnomon or building-block of all even numbers. Two rows of twos is four, a table number. Three rows of twos is six, another table number. Etc. All the even numbers ("multiples of 2") greater than 2 are table numbers.

    • So we will sieve out all evens ABOVE TWO by flipping over the cards for 4, 6, 8, etc., up to 200, leaving only odd numbers on the string(s) or wire(s).

    • And we tell them that this has just taught us an important discovery! "From now on, above 2, a row number must be odd"

    Two Important Questions

  3. After the children have absorbed this we say, "This is going to teach us two more important discoveries!"

    We immediately guide the children in asking and answering TWO IMPORTANT QUESTIONS after each discovery of a row number.

    • The FIRST IMPORTANT QUESTION is "WHAT KIND OF NUMBER IS ON THE FIRST CARD WHICH MUST BE FLIPPED OVER BECAUSE IT IS A TABLE-NUMBER BUILT FROM THE ROW-NUMBER GNOMON WE JUST FOUND?" The row-number we just found was 2. The first table-number built from rows of 2 is 4 WHAT KIND of Table-Number is 4? 4 is A SQUARE. 4 is THE SQUARE OF 2, THE ROW-NUMBER WE JUST FOUND!

      We write, high on the blackboard, "2«4". We have flipped all "tables of twos", so we turn to

    • THE SECOND IMORTANT QUESTION:"WHAT KIND OF NUMBER IS ON THE FIRST UNFLIPPED CARD AFTER THE ROW-NUMBER WE JUST FOUND?" The children see that this cards bears the number 3? IS IT A ROW-NUMBER OR A TABLE-NUMBER?

    Answer to Two Big Questions

  4. We guide the children in discovering that 3 bottle caps CANNOT build up two equal rows. So, 3 is a row-number. We have found two-row numbers, 2 and 3.

  5. We guide the children in discovering that 6 is constructible from rows of threes, so 6 is a table-number. We guide the children in discovering that 9 is constructible from three rows of threes, so 9 is a Table-Number. 12 caps can be constructed as four rows or three caps. Etc. So, all numbers greater than 3 which are built as patterns of threes are Table-Numbers. We wish to sieve them, by flipping over their cards. But wait!

  6. What do we see on the wire of cards? We have already flipped over the 6-card. Why? Because 6 can be built as a table of 2-rows. The fact that 6 can also be built as a table of 3-rows doesn't matter because "6 is already out of the game!" And even number 12 has already been flipped over. And even number 18. Etc.

    That takes us back to our FIRST IMPORTANT QUESTION. Remember? "WHAT KIND OF NUMBER IS ON THE FIRST CARD WHICH MUST BE FLIPPED OVER BECAUSE IT IS A TABLE-NUMBER BUILT FROM THE ROW-NUMBER GNOMON WE JUST FOUND?" That row-number was 3. The first unflipped table-number bult from threes is 9. What kind of a number is 9?. A SQUARE. THE SQUARE OF THE ROW-NUMBER WE JUST FOUND: 3. On the blackboard, we write "3 « 9".

  7. We flip over 9 and all unflipped multiples of 3. These are table-numbers built from rows of threes Now we can reask our SECOND IMPORTANT QUESTION. Remember? "WHAT KIND OF NUMBER IS ON THE FIRST UNFLIPPED CARD AFTER THE ROW- NUMBER WE JUST FOUND?" The children readily find that the card bears the number 5. Is 5 a table-number or a row-number?

  8. We guide the children in discovering that 5 bottle caps cannot be turned into two or more equal rows. So, 5 is another row-number. And so are any numbers built from rows of 5. So we must flip their cards over.

  9. WHAT KIND OF NUMBER IS ON THE FIRST CARD WHICH MUST BE FLIPPED OVER BECAUSE IT IS A TABLE-NUMBER BUILT FROM THE ROW-NUMBER GNOMON WE JUST FOUND? 25. And 25 is the square of 5 the row-number we just found.

    WHAT KIND OF NUMBER IS ON THE FIRST UNFLIPPED CARD AFTER THE ROW- NUMBER WE JUST FOUND? 7. Is 7 a table-number or a row-number?

  10. The children discover that 7 is a row-number, and so are all multiples of 7, which must be sieved.

    The children answer THE FIRST IMPORTANT QUESTION by finding the first card above 7 to be turned over is 49 = 7 x 7. (We write "7 « 49" on the blackboard.) And the children discover the first unturned card above 7 is 11, and that 11 is a row-number. Etc.

NOW A PATTERN BEGINS TO UNFOLD!

The answer to the first important question always involves the square of the number just discovered to be a row number. The answer to the second important question involves the next row number.

We have "planted" the basis (to be developed later) for an algorithm which minimizes the number of tests needed to determine if a number is a row- number (prime number) or a table-number (a composite number).

A Row-Number (Prime Number) Algorithm

We have discovered that the row-number (prime number) is the multiplicative gnomon or bulding block of numbers. To see how to factor a number, we need only test for row-number (prime) factors. The answers to those TWO IMPORTANT QUESTIONS tell us how to conduct such a test.

The answers to that FIRST IMPORTANT QUESTION always involved squares of row-numbers (primes). The answers to that SECOND IMPORTANT QUESTION always involved the "next" row-number (prime).

Please notice. Since the square of that "next" number (answered in the second question) is greater than the square in the answer of the first question, that second answer gives us a cut-off for testing! Thus, the answers to those two important questions put an upper bound on the number of row-number (prime) tests we need to make.

We have written on the blackboard (or we remember): "2«4; 3«9; 5«25; 7«49; 11«121; 13«169", etc. We can ignore the first pair, since, above 2, all prime numbers (row-number) must be odd. (Note: Perhaps 40 years ago, I read in a couple of text-lines about this algorithm. A few years ago, I discovered this "Flip-Card Sieving" procdure to motivate kids to discover this Algorithm for themselves.)

Application of Our Algorithm

Suppose we wish to test 91 for primality. 91 lies between the prime-squares 49 and 121. But 121 is the square of 11, "the next prime number above 7". So we can ignore 11. We need only test 91 for 3, 5, 7 -- only three tests!

Now, there exists a simple test (related to "casting out nines", described in an associated file) for the 3-factor. You add the digits of the number, repeatedly, until a single digit number is obtained. That number is the remainder when you divide by 3. Clearly, a number has a 3-factor if, and only if, that remainder is zero. Given 91, 9 + 1 = 10, and 1 + 0 = 1. So, 91 divided by 3 yields remainder 1. Obviously, the 3-test fails for 91.

A 5-factor? A number has a 5-factor if and only if the number ends in 0 or 5. So the 5-test fails for 91.

There is no easy 7-test. You must try division. You discover that 91 = 7 x 13. The 7-test clearly shows that 91 is not prime and we're done, because the other factor, 13, is also a prime. 91 cannot be further factored. Please notice also that 13 is above that "next prime", 11, which we put above our "ceiling" or "upper bound" on testing 91 (since 49 < 91 < 121).

We don't have to worry above higher primes. The primes in our "test series" will flush out any possible "higher prime".