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 < n - 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."