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.

Wednesday, September 17, 2014

modular tables

No, not a post about IKEA furniture. A while  ago I put up a post on colouring multiplication tables by assigning ranges of numbers a colour value. You end up with something that looks like a rainbow.

This image was made in Tinkerplots, so it was easy to go from a 10 x 10 table to a 50 x 50 table (removing the numbers and just keeping the colours, and shrinking each cell down a bit):

Inspired by the "Zn Multiplication visualizer" found here and mentioned here, and thinking about modular arithmetic from the last post, I decided to make a few more images.

If you take the values in this 50 x 50 table mod 9, you'll get this nice quilt - repeating in 9 x 9 blocks.

If you choose your mod value to line up with the width of the table (take the values mod 50) you get this:

The light blue along the bottom and the right side are all zeros - anything that is a multiple of 50, as the bottom and the far right side are, will have a remainder of 0 when you divide them by 50.

If you take the values mod 2500, then you get something that looks like the rainbow we started with - except for one square (maybe you can spot it, or figure out where it will be).

Here's a 75x75 table, mod 75, in shades of blue.