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.



Monday, September 15, 2014

squashing multiples

An elementary school exercise leads to writing a simple program, a little proof by contradiction, and learning about some mostly-forgotten calculation tricks: just some of the fun that can be had when playing with simple math. Sound good? It all starts with squashing numbers...

No doubt you've noticed some patterns in the non-zero multiples of 9: 9, 18, 27, 36, 45,... One thing to notice is that if you (repeatedly) add up all the digits of a multiple of 9, you always get 9 as your answer.

This works immediately for many multiples of 9, like 9*14 = 126 (1 + 2 + 6 = 9), for others you need to keep squashing - if the first digit sum itself has more than one digit, sum those digits and repeat until you get a single digit answer. For example 9 * 42 = 378 (3 + 7 + 8 = 18, which has two digits, so keep squashing: 1 + 8 = 9). 


All multiples of 9 squash down to 9, which is neat. More importantly this also works in the other direction: any positive integer that squashes to 9 is a multiple of 9. This makes squashing an easy divisibility test for 9 and makes it easy to find multiples of 9 (is 359 a multiple of 9? No, but 369 is, and so is 459).  Also: Any number made by rearranging the digits of a multiple of 9 will also be a multiple of 9 (re-arranging the digits won't change the squash value). So, since I know that 882 is a multiple of 9, I also know that 288 and 828 are also multiples of 9.

Can you always squash a number? Could there ever be a number that gets bigger when you sum its digits?

One (wordy) argument goes like this: To obtain a contradiction, assume there are some positive integers greater than 9, whose digit sums are equal to or greater than the original number. Such a number would be a problem for us: we need to be sure that any number with two or more digits will always have a digit sum less than itself (so we can keep doing digit sums until the number is squashed down to a single digit).  Choose n to be the smallest such troublesome number. Suppose the digit sum of n is another number k such that n <= k. Now we are going to build a new number m by taking the digits of n and changing one of them: chose a non-zero digit in a position bigger than the ones place and decrease it by 1. For example, if our number n was 567 (which it isn't) our new number m could be 557. Now m is at least 10 less than n, but its digit sum is only one less than k (since only one digit was decreased by 1). Now m <= n -10 < - 1 <= k-1, and so m is also less than its digit sum (k - 1). But n was chosen to be the smallest number with this property, and m is definitely smaller than n. So we have a contradiction: it cannot happen that the digit sum of a number is greater than the number itself. This means that it is safe to squash: you will always get smaller and smaller numbers until you get down to the single digits.

Squashing multiples of 9 was interesting: What about patterns in other multiples? Consider positive multiples of 3: 3, 6, 9, 12, 15, 18, 21, 27, ... they don't squash down to the same value, but if you try it out you'll notice a pattern: 3, 6, 9, 3, 6, 9, 3, 6, 9, .... It's easy to see this if you write the multiples in a 3 column table.



In the chart above, the first column entries all squash to 3, the second to 6, and the third to 9. Some other multiples produces similar charts, for example 6 and 12. (I noticed these squashing patterns when looking at material from the JUMP math program for grades 3 and 4, where tables like these are used to explore patterns for learning multiplication facts.)



Not all integers will have their multiples fit into this pattern. For example, 4 needs a 9 column table to show a squash pattern.

You might want to write a little program to do your squashing for you - whether you do or squash by hand, you'll see a clear pattern.

Just a brief note on the Java utility below: the while(true) statement in the squash() method relies on our assumption that digit sums get smaller - otherwise we'd potentially have an infinite loop.  The digits() method is simple example of recursion.

package squash;
import java.util.ArrayList;
import java.util.List;

public class SquashCalculator {

public List digits(Integer start) {
if (start == 0) {
return new ArrayList();
}
int val = start % 10;
List recur = digits(start/10);
recur.add(val);
return recur;
}

public Integer sum(List list) {
Integer sum = 0;
for (Integer i: list) {
sum += i;
}
return sum;
}

public Integer digitSum(Integer i) {
return sum(digits(i));
}

public Integer squash(Integer n) {
if (n == 0) {
return 0;
}
Integer current = n;
while(true) {
current = digitSum(current);
if (digits(current).size() == 1) break;
}
return current;
}
}


Here's what you'll observe squashing the numbers 1 - 40:


Maybe you knew that this would happen, but I didn't. I was surprised at first that squashing numbers formed this regular pattern, but it really isn't surprising if you think about it. If you consider the squash of n  and then wonder what squash of n + 1 should be, it should just be one more, unless the squash of n was already 9, in which case adding one more will give you squash of 10, which is 1.

So, the squash function maps the integers onto a structure like the one on the right below, that is very close to taking the number "mod 9".


Putting the integers from 1 to 36 in a 9 column chart like the "multiples of 4" above shows this also.


This suggests that there is a direct formula for the squash of a number close to its mod 9 value. It turns out this can be expressed as:







One aspect of this is that n and squash (n) are congruent modulo 9 (which means that if you divide n by 9, or the squash of n by 9, you will get the same remainder).





This is the important relationship that makes squashing useful. It's kind of amazing that you can take a number and completely re-arrange its digits, or sum up all its digits, and still retain something about the original number (the remainder after dividing by 9). When you do something this violent to a number it's surprising that some information about the original number remains.

This is why every number that can be squashed to 9 is divisible by 9 (both are equal to 0 mod 9). This also helps to explain the number of columns in the tables above. For a number m whose multiples we are playing with, if m is divisible by 3 (like 3, 6, and 12), its multiples will have the same squash with a period of 3 (and will repeat in a 3 column table). If m is not divisible by 3 (the only factor 9 other than 1 and itself), then the squash of the multiples of m will have a period of 9 (and will repeat in a 9 column table). If m is a multiple of 9, then its multiples will be multiples of 9 also, and their squash will always be 9.

We also get a divisibility test for 3: If a number's squash value is 3, 6, or 9, then that number is divisible by 3. For example, suppose n squashes to 6. That means that n is congruent to 6 mod 9, which means that there is some positive integer k such that n = 9k + 6. Since the right hand side of that equation is divisible by 3 (dividing the right  by 3 gives 3k +2), so is the  left hand side.

But wait, there is more. Calculating squash values mod 9 has a short-cut: when you are adding up all the digits, you can throw out any multiples of 9, since they will always end up contributing zero to the final answer (because multiples of 9 have a remainder of 0 when divided by 9). This calculation is part of an error-checking technique called "casting out nines" which can be used to check arithmetic. When casting out nines, you essentially squash (ignoring 9s and multiples of 9s) the inputs and outputs of your calculation, and if they are different then you know you made a mistake.

If you want to learn more about this (and there is a lot more), you should Google "digital root" which is the standard name for what I've been calling "squash."

Friday, June 20, 2014

Wednesday, May 28, 2014

origami workshop


I mentioned in the previous post that I was considering doing some modular Sonobe origami in an upcoming workshop for middle school students. Wondering if this is a good idea, and thinking that I had better have some backup plans, I decided to make a list of origami models that I have used in school workshops in the past.

Simple Triangles
These simple models are nice for the very young and for beginners. Start with a triangle made from cutting standard origami paper along a diagonal.


A bit of playing around with the triangles should be enough for you to figure out how to fold examples like the ones above, and maybe even to come up with a few of your own. The instructions for the sailboat are on the OrigamiUSA diagrams page.

Hopping Frog
This is a very nice toy model from OrigamiUSA. See this post for some notes on it. Whenever I have used this with younger kids, I have always brought some pre-folded ones with me for them to play with and draw on.


Paper Cup
A traditional model using a square origami paper, the instructions are also available from OrigamiUSA. It makes a nice pocket to put your frog into. See this post for more on this model.


Shirt
The origami t-shirt is a model that I use to start off workshops for older students - for younger children I usually bring some paper that has had the initial folds completed, so they can get to the finished product in a few folds - this motivates them to go back and do the whole model themselves. You can find the many origami shirts online, the one I use is one by Gay Merrill Gross that appeared in the first issue of Creased magazine.

Envelope
Maybe its because we don't send letters much that this model does not grab everyone as overly exciting. I like it, and it is good to have some origami that you can do with standard letter paper (lots of these available in schools). See this post about the crease pattern. Also from the OrigamiUSA page.


Traditional Boat
This is the first and only origami model that I learned as child and I enjoy sharing it with children. It's another model (like the frog and the cup) that you can play with, and like the envelope it can be made from standard letter paper. The diagram is available on OrigamiUSA.  The boat becomes even more  playful when it is used as "storigami" in the tale of The Captain's Shirt. Happily destroying your boat while reciting the tragic story teaches an essential lesson about the impermanence of the origami art form.

Waterbomb Octahedron
I had success with this model in a workshop for grade 7 and 8 students. There is a very nice overview of it here, and the model was also featured in Creased magazine under the name "origami blowtop," but I have not found the issue.

Its modules are the first few folds of the waterbomb, another popular model for beginners. The waterbomb base has also made its way into origami tessellations (see here). If I were to do a tessellation in a workshop, it would be the waterbomb.

Picture Frame
All of the lesson plans for Creased magazine's "Teachers' Corner" are available online here. The picture frame is presented here in lesson 2. The blinz base used to create the picture frame is know to many children as the preliminary folds for the fortune teller or cootie catcher - another origami toy that is always fun to make.

Robinson's Butterfly
I've not yet used this in a workshop, but have enjoyed showing people how to fold it. You can make these from those pesky magazine inserts, or maybe from bus transfers. The model comes from Robinson's book "The Origami Bible." I have a post about it here.



When considering how to present these models, and how to conduct workshops for young people, I've looked into the "origametria" approach described in this paper by Miri Golan and Paul Jackson. Perhaps because I have only done origami with students in workshop settings where the emphasis is not on the mathematical value (which I hope is intrinsic anyway), rather than as part of a regular classroom program, I have not followed the origametria principles very closely. However, their advice on using positive language and respecting the students's work and efforts are essential in any setting - any feeling students have about what they experience will outlive anything mathematical they happen to notice about the creases.

The resources on OrigamiUSA and Creased are great, but keep in mind that very few beginners are good at reading origami diagrams, and most children are put off by them. I like to have the instructions available for the students, but most of them learn the pieces by following along with you, and having you (and others) repeat the folds in front of them. A document camera is a plus, but you have to be willing to walk around and demonstrate the folds, and recruit helpers who are ahead of the others to assist you.

Update: A handout used for the workshop, which did include a little modular origami, is here.

Monday, May 26, 2014

simple sonobe

I'm prepping for an origami workshop for middle school students, and am thinking about focusing on modular origami with sonobe units. In modular origami, many folded pieces of paper are assembled to make a model. Usually, all the pieces of paper (called units) are folded the same way. Like other forms of origami, modular origami is generally done without glue or scissors, so the pieces need to fit together so that they lock in place - putting the pieces together often feels like weaving or braiding. In past workshops for children at this age I have used a simple waterbomb octahedron (like this), but the sonobe presents a bit of a challenge - I might fall back on something with less frustration potential. On the other hand, that frustration is part of the lesson that sonobe teaches - it always seems like it just is not going to come together, and then it does.

There are some good instructions for modular origami projects using the sonobe unit out there - for folding the unit this one is good, and for assembly I like this one.

The version of the unit that I like to use is a simpler one than is presented in the instructions that I have found online, and is taken from Origami for the Connoisseur, by Kasahara and Takahama (not really being a connoisseur, it is one of the very few things I can put together from this book). I've attempted some diagrams for this below.

The unit has a few less folds than the standard version, and this makes a difference when you are making 30 or more of them.

The Simple Sonobe Unit





Sonobe Unit Assembly




Update: a handout based on these diagrams is here.

Monday, February 24, 2014

Thursday, January 9, 2014

art for maths sake

"Let none be ashamed to learn, for a good work requireth good counsel."
- Albrecht Dürer, 1520

Mathematics and Art, sometimes thought to be opposite poles of human experience and activity, can sometimes sit down together in conversation.

Sometimes we might think of the conversation as more of a lecture - with Mathematics providing some technical advice. Perspective drawing is the prime example - where mathematics allows artists to create realistic images, or else to subvert the expectations of realism (as in anamorphic art). Art does reply - for these mathematical tools, it repays the favor by providing Mathematics with inspiring teaching and learning opportunities (in the case perspective drawing, see this essay by mathematician Annalisa Crannell).

Art may ask questions of Mathematics - after all, math is not merely a tool; it's often the inspiration for Art's work. Geometry, often in the form of polygons, polyhedra, and tessellations, makes many appearances in art from the old (see for example the work of Albrecht Druer, or this essay on Raphael's famous painting The School of Athens), to the new (check out the latest Bridges mathematical art galleries). Art that springs from Math can, in turn, say something back to Math - providing motivation in math education (see most posts from mathmunch), and inspiration for working mathematicians. A big part of what gets me excited about the recreational math that I do are the pretty pictures (I've been putting pictures from this blog that I like over on this tumblr for a while).

The book Beautiful Geometry gives us a rare opportunity to listen in on an extended and fascinating dialog between Math and Art: here they are talking like old friends, sharing jokes, and discussing other subjects like history and literature through the pairing of brief and interesting essays by mathematician Eli Maor and beautiful illustrations by artist Eugen Jost.

You will likely want to join in the conversation - the essays and artwork in Beautiful Geometry are inspiring and motivating - prompting me, at least, to try to play around with their ideas. For example, the images below are from a Geometer's Sketchpad iteration based on Jost's artwork entitled 3/3 = 4/4, which accompanies Maor's essay on geometric series (Chapter 30).


These images represent some early partial sums of the series below - can you see how?



Jost's piece Pentagons and Pentagrams (Chapter 22), similarly had me reaching for GSP:


Although some of Jost's pieces allow themselves to be mimicked by us amateurs (armed with appropriate software), many are true art works, conveying an aesthetic that keeps them from being mere diagrams (while still saying something substantive about mathematics).

Several of the topics that Maor writes about are ones I've looked at before (Lissajous figures, means, hypocycloids, figurate numbers), but even in these somewhat familiar areas the essays and illustrations are nudging me to look back and explore some more. (I even learned something new about quadrilaterals: connecting the midpoints of a  quadrilateral always yields a parallelogram - Chapter 3).

Jost's art and Maor's articles are going to inspire many of us to continue experiencing mathematics through beauty, and to look at art with a greater understanding of the math that helps to make it beautiful.