Tuesday, January 27, 2015

bus number factoring

Each bus in Ottawa has a four digit number that identifies it (like 4476 above). One thing to do while riding, if you don't have a bus transfer to play with, is to pass the time factoring that bus identifier (it's also printed on the inside of the bus, in case you miss it getting in).

We all know some basic divisibility rules to help with factoring: If it ends in a zero, it's divisible by 10, if it's even then its divisible by 2, if it ends in a 5 then it's divisible by 5. You may know that if the last two digits of a number are divisible by 4 then the whole number is also divisible by 4 (because 100 is divisible by 4, so for example a number xy76 for any old xy will be divisible by 4 because xy76 = xy00 + 76,  and both parts of the sum are divisible by 4).

Digital roots help us with multiples of 3. If a number's digital root is 3, 6, or 9, then that number is divisible by 3. A digital root is easy to calculate: You just keep summing the digits of a number until you get a single digit answer - if your answer is not a single digit, you just do it again.  For example, the digital root of 4476 is found by first calculating 4 + 4 + 7 + 6 = 21, and then 2 + 1  = 3. So 4476 is divisible by 3.

So, we know 4476 is divisible by 4 and 3. Now if you can do some dividing in your head while sitting on the bus, you'll figure out that 4476/12 = 373. Now you might try a bunch of things to factor some more, but eventually you will decide that 373 is likely prime, and it is. So 4476 = (2^2)*3*373.

I recently learned that you can also use the double digital root to help with factoring. The double digital root of a number is calculated by grouping the number's digits into pairs (starting from the right) and adding them, repeating until you get a double digit number. So 4476 gives 44 + 76 = 120, and then 1 + 20 gives 21.

How can this be helpful? Just as the digital root of n is congruent to n mod 9, the double digital root of n is congruent to n mod 99. The digital root of n helps us identify multiples of 3: if the digital root of a number is equal to a multiple of 3 (3, 6, or 9) that means that the original number when divided by 9 has a remainder divisible by 3, which means the original number is divisible by 3 also. The double digital root can help us identify multiples of 11 in a similar way (since 99 is a multiple of 11). The rule is: if the double digital root is a multiple of 11, then so is the original number. So double digital roots help identify multiples of 11 that are multi-digit numbers (not always easy) by reducing the problem down to identifying multiples of 11 that are two digit numbers (which is easy).

The double digital root of 4476 is 21, not a multiple of 11 (and we saw above that 4476 is not a multiple of 11 either). Lets try 1320: the double digital root is 13 + 20 = 33, which is divisible by 11, and it turns out that 1320 = 11 * 120. For another example, use this method to confirm that 3740 is also divisible by 11.

To be honest, I have not been on an Ottawa bus whose number is a multiple of 11 yet, but if that exotically numbered public transport is out there, I'll know it when I see it.

Tuesday, December 2, 2014

Some notes on the Kaprekar function

Consider a 3 digit number, say 395. Take its digits and form the greatest and least possible 3 digit numbers and subtract them: 935 - 359 = 594. Now do the same with the result:  954 - 459 = 495. Try it again, and you see that the process has hit a fixed point: 954 - 459 = 495.

The Kaprekar function involves taking a number, computing two shuffles of its digits (the shuffle with the greatest value, and the one with the least value), and then taking the difference of those two shuffles. So for an integer n, if g is the number you get from re-arranging the digits of n from greatest to least, and l is the number you get from re-arranging the digits of n from least to greatest, then the Kaprekar function is (n) = g - l. If you repeatedly apply the Kaprekar function to an integer n, you may end up converging to a constant value. For any n whose digits are all the same, you automatically converge to 0. Surprisingly, for any 3 digit number whose digits are not all the same, k will converge to 495 (as is the case with the numbers in this plot), for any 4 digit number whose digits are not all the same, k will converge to 6174. Numbers with more than 4 digits apparently do not have a single convergent value, but bounce around within sets of values.

The pattern on the left comes from making 9 columns of numbers, the leftmost column is a listing of 100 to 199 (starting at the bottom), the rightmost column is a listing of 900 to 999. These are coloured based on how quickly each number causes the Kaprekar function to converge to a constant value. Mathworld shows a similar plot for four-digit numbers taken from an article that appeared in Mathematics Teacher.

Here's a few examples of 3 digit numbers converging to 495:

949 -> 495 (white)
950 -> 891 -> 792 -> 693 -> 594 -> 495 (dark pink)
951 -> 792 -> 693 -> 594 -> 495 (somewhat dark pink)
952 -> 693 -> 594 -> 495 (somewhat light pink)
953 -> 594 -> 495 (light pink)
954 -> 495 (white)

949 converges quickly: 994 - 499 = 495; 953 takes a little longer, first you get 953 - 359 = 594. and then 594 gives us 954 - 459 = 495. You can test out the other chains, and also try it with any three digit number whose digits are not all the same: they always end up at 495. A 3 digit number whose digits are all the same gives 0.

Here are two observations that help me understand what is going on with this:

(1) If you take the difference of two shuffles of the same number, the result is always divisible by 9.

(2) Any number that is divisible by 9, when shuffled, will also be divisible by 9.

I found these two things very surprising at first, but both can be understood if you think about digital roots.

When you apply the Kaprekar function to a number, your result is not just any old number, but a member of a much smaller set: the multiples of 9. And since many of those multiples of 9 are just shuffles of other multiples of 9, they behave the same when the Kaprekar function is applied to them.

Why does the pattern for the three digit numbers seem to repeat and shift up to the right? The shift corresponds to adding 111. Adding 111 generally increases each digit by 1 (except if one of the digits is a 9), leaving the difference between the greatest and least shuffles unchanged.

Monday, October 20, 2014

GSP and LOGO (for MITx: 11.132x)

Note: This post is an assignment for the Edx MOOC MITx: 11.132x Design and Development of Educational Technology. The assignment had to be posted online, and since it relates somewhat to the themes of this blog, I put it here.

Educational Technology Then and Now: Geometer's Sketchpad and LOGO

Geomter's Sketchpad (GSP) is an example of current educational technology that is based on design and educational principles that can generally be described as constructionist. Widely used in contemporary classrooms, GSP is based on ideas about computer-human interaction that date back to the 1960s, and bears interesting points of comparison with LOGO, an educational technology which approaches a similar subject from a distinctly different direction.
A classic GSP construction: Pythagoras Tree

GSP is an environment for dynamic geometry exploration - it allows uses to start from some simple elements (point, line segments, circles) and construct sophisticated geometric forms. Transformations, iterations, and animation can take these forms well beyond what can be done with ruler and compass. The dynamic element resides in how the initial inputs (the free points) can be dragged, mapped, or animated while preserving the structures that were constructed with them. GSP is commonly used in middle school and high school, but is also used in elementary school settings, and at the university level - its simple, yet powerful design make it useable in many settings. 

In the 1980s, the original developers of GSP based their ideas on earlier earlier work from the 1960s on human-computer interaction (the SKETCHPAD program, 1967), and ultimately on the concepts of Euclidian geometry, which date back over two millennia.  Since the time of its release in the early 1990s, GSP has gone through several iterations, maturing and inspiring other dynamic geometry software, such as GeoGebra.

The way that GSP embodies the concepts of Euclidian geometry make it educational without seeming to explicitly trying to teach. It allows students to act as practitioners, creating their own works by providing them the means of discovering and applying geometric concepts. This is one of its sources of charm and power - presenting itself as a tool that is useful both to learners, to general geometry enthusiasts, and mathematicians.

One difficulty that teachers and students can initially encounter with GSP is its complete openness: it presents a blank canvass, with no prompts, few tool icons, and a set of menu items that seem to be disabled. Only when the correct inputs are highlighted do constructions become possible: when two points are selected, you can opt to construct a circle, line, segment or ray. When three points are selected you can choose to make a triangle, or an arc. As you learn what elements are required to construct new elements, you can begin to use geometric constructions to create something interesting. The pitfall that some students fall into is to treat GSP as a "drawing" program instead of a "constructing" program. Teachers find it difficult sometimes to lead students through the many steps required to build up a sketch. A solution to both dilemmas is to have students add to and explore pre-existing sketches, a GSP technique sometimes called the "SWIMMM" approach (Start with Immediately Meaningful Mathematical Models).

LOGO, developed by Seymore Papert and others around 1967, introduced a new language and perspective for creating geometric forms and learning programming concepts: turtle graphics. Allowing students to draw on a canvas by providing simple procedural commands to move a point (sometimes conceptualized as a turtle with a pen tied to its tail), LOGO was an environment and programming language of surprising power and expressiveness.

Educational technology is sometimes evaluated by the "low floor, high ceiling, wide wall" rubric, meaning that it should be easy to get started with, be empowering, and admit a wide range of expressiveness. Classical implementations of LOGO present difficulties to young learners because of the failure-prone nature of typing in the sometimes tricky syntax into command-line style interpreters. More contemporary implementations of LOGO help overcome this problem: The "pen" and "movement" operations in SCRATCH provide a LOGO-like environment that makes writing programs much easier. The SNAP extended implementation of SCRATCH features a logo-like turtle-cursor, making it easy to get started with turtle graphics.   

LOGO-style turtle graphics in SNAP

LOGO and GSP both greet their user with a blank canvas and an invitation to create geometric shapes and patterns through interaction and experimentation, but each provides a very different interactive experience. LOGO presents a "turtle's eye view" of geometry - a procedural exploration of analytic (Cartesian) geometry where a kinesthetic approach that engages learners' proprioception is used to navigate the Cartesian plane. GSP provides a more traditional synthetic (Euclidian) approach, where the geometer has a more global view (as opposed to the turtle's necessarily local one). 

In addition to offering different perspectives on geometry, GSP and LOGO also present different views of human-computer interaction: two different approaches to computer programming. Learners engaging with LOGO learn the fundamentals of computer programming in a rather direct way: the LOGO language's procedural flow and its constructs make it look very much like many other programming languages. GSP also introduces programming ideas, but more abstractly and less recognizably. The Pythagoras tree sketch, shown at the top of this post uses fundamental programming ideas of iteration (to create the diminishing repeated elements of the sketch) and parameterization (the colour of the squares is a function of their area). Both LOGO and GSP help their users learn how to provide input and instructions to computers (i.e. the basics of computer programming), but in very different ways.

Viewed as educational technologies, LOGO and GSP both follow a constructive approach, providing open environments that encourage an affective and aesthetic engagement with learning mathematics. The differences in approach taken by these tools to the same learning goals show how varied educational technology can be.

Thursday, October 2, 2014

Monday, September 29, 2014

A year of tinkering

You really should take advantage of the free until August 2015 license that is currently being offered with a fresh download TinkerPlots. Would that it was freely available in perpetuity without condition, but a year of tinkering is nice.

If you are a middle school teacher, then this is designed for you and yours. If, like me, you are not, you may find it fun to play with anyway.  Here is something I was playing with recently:

An elementary school number sense activity

In the JUMP math curriculum for grades 3 and 4, there are lessons where students investigate the patterns formed when multiples of a number are written in a 3 or 4 column grid. After some number talk students play a game where some entries in the table are covered up or erased, and students have to identify the blanked out value and state the corresponding multiplication fact.

An interactive game like this is easy to make in TP - in the above screen shot multiples of 3 are arranged in a 3 column table. When a student provides an answer, clicking on the square will cause the answer to be highlighted in the number line. For fun, I added an additional plot that shows where the number would lie in a 10 point circle diagram (which students may have already been using to help remember and identify patterns in multiples). The multiple used and the number of columns displayed can be adjusted using sliders, and the "blanks" can be re-randomized by clicking Ctrl-Y. The file is here.

Update: John Mighton gives an overview of the kind of lesson that uses charts like these in JUMPs guided discovery method here.