Factor Subtractor by Barry Cipra bcipra@rconnect.com March 7, 2012 Factor Subtractor is a game played with numbers. It is intended to reinforce basic skills in arithmetic while offering something of interest to professional (or amateur) mathematicians. It can be played on paper, at the blackboard, or even, depending on the players' facility with mental arithmetic, aloud, for example during a car trip. The games start with one player factoring a large number, such as 100, as the product of two smaller numbers, such as 4x25 or 5x20. Play then proceeds with the players taking turns as follows. When it's your turn, you pick one of the two factors, subtract it from the product, and then factor the resulting difference, again as the product of two numbers. For example, suppose player A starts by factoring 100 = 4x25. The game might proceed as follows: B: 100-4 = 96 = 8x12 A: 96-12 = 84 = 6x14 B: 84-14 = 70 = 2x35 A: 70-2 = 68 = 4x17 You might have noticed, we haven't said what the object of the game is, i.e., how to win it. But note that the numbers being factored are getting smaller and smaller. So eventually we're going to run out of numbers. And that's the object: To be the player to reach 0. Let's see how this might play out by continuing the game above: B: 68-17 = 51 = 3x17 A: 51-3 = 48 = 6x8 B: 48-8 = 40 = 4x10 A: 40-10 = 30 = 2x15 B: 30-15 = 15 = 3x5 A: 15-5 = 10 = 2x5 B: 10-2 = 8 = 2x4 A: 8-4 = 4 = 2x2 B: 4-2 = 2 = 1x2 A: 2-2 = 0 so player A wins. It didn't have to end that way. It turns out, each player in this example made a couple of "bad" plays. The last one occurred when player B subtracted 15 from 30 instead of 2. Let's see why this is. The secret lies in the sequence 4,9,10,14,16,18,22,25,26,28,30,34,36,40,46,48,49,54,55,56,62,63,65,66,68,74,75,76,80,81,84,88,90,94,96 ,.... The list goes on and on; these are the one- and two-digit "target" numbers for the subtraction step, for a which a player can pick a factorization that guarantees a win. Notice that 15 is not on the list, but 28 is. Therefore, player B should have played 30-2=28 instead of 30-15=15 after A had offered 30=2x15. Had he chosen the better number to subtract, B needed to factor 28 as 4x7, because neither 28-4=24 nor 28-7=21 is on the list. (The factorization 2x14 would have been a mistake, because it would allow player A to get to either 28-2=26 or 28-14=14, both of which are on the list.) You may notice that 30 is also on the list. This means that player A actually made a mistake in factoring it as 2x15. The "correct" move would have been 30=3x10, since neither 30-3=27 nor 30-10=20 is on the list. For that matter, player B made a mistake early on, factoring 96, which is on the list, as 8x12 instead of 4x24; doing so allowed player A to get back on the list, whereas neither 92 nor 72 would have been. So where did this list come from? The short answer is, recursive computation. The list, along with its complementary list of "losing" numbers, is built starting at 1. Obviously 1, along with every prime number p, is a "loser" because you can only factor such a number as p=1xp, which allows your opponent the immediate winning move p-p=0. (Only a fool, or a very kind parent, would opt for the non-winning move p-1 for a prime p.) The first winning number is 4, since its factorization as 2x2 forces your opponent into 4-2=2=1x2. The numbers 6 and 8 are both losers because the factorizations 6=2x3 and 8=2x4 allow your opponent to counter with 6-2=4=2x2 and 8-4=4=2x2, respectively. But 9 is a winner, because 9=3x3 forces your opponent into 9-3=6=2x3. Similarly 10 is winner, because 10=2x5 leaves your opponent either 10-5=5 or 10-2=8, both of which are on the losing list. Let's do just a couple more numbers: 12 is on the losing list because 12=2x6 allows your opponent to get to the winning number 12-2=10, and 12=3x4 allows the winning move 12=3=9. Similarly for 15: it's a loser because 15=3x5 allows for 15-5=10. But 16 and 18 are on the winning list, with winning moves 16=4x4 and 18=3x6. In general, once you have a complete list of all winning numbers less than N, you can determine whether or not N goes on the list by looking at its possible factorizations. If there is a factorization N=hxk for which neither N-h nor N-k is on the list, then N goes on the list; otherwise N does not go on the list. To do one more example, let's show why 72 is not on the list. To do so, we have to consider all its factorizations: 2x36, 3x24, 4x18, 6x12, and 8x9. For 2x36, we have 72-36=36, which is on the list. For 3x24, we have 72-24=48; for 4x18, we have 72-4=68 (and also 72-18=54, but all you need is one of the two); for 6x12 we have 72-6=66; and for 8x9, we have 72-9=63. As mentioned, the list as presented shows all one- and two-digit winning numbers. The reader may wish to check that it properly omits 97, 98, and 99. (The easy case is 97: it's prime.) But what about 100? As noted, A's opening factorization 100=4x25 was a bad move, because it allowed B to get to 96. (Actually, 100-25=75 would have been a better move. As we saw, B chose the "wrong" factorization for 96. You can check that, for 75, there is no bad factorization.) Is there a different factorization of 100 that could have guaranteed A a win? Once you get started, it's possible to extend the list indefinitely, with a fairly simple computer program. Matt Richey at St. Olaf College in Northfield, Minnesota, wrote such a program and computed the list up to N=200,000. There is no readily discernible pattern to the list. Indeed, that's what makes it of possible theoretical interest: the sequence (which has yet to appear in the Online Encyclopedia of Integer Sequences, although that's likely to be self- correcting sometime soon) is easy to define, but has no obvious properties that allow one to say that a given (large) number is or isn't on the list, beyond the one obvious "theorem" that the list contains no prime numbers. For example, based on the "early returns" showing 4, 9, 16, 25, and 36 on the list, one might speculate that all squares greater than 1 are winning numbers. The next square, 49, which is also on the list, would seem to confirm that hypothesis. But then you get to 64.... Richey's computation shows there are 366 numbers on the list up to 1000, 4033 up to 10,000, and 42,563 up to 100,000, but it's unclear whether the fraction is leveling off or continuing to climb. It would be worthwhile to confirm (or correct) these calculations and to extend them for another few orders of magnitude. Just knowing a number is on the list doesn't in itself say which factorization guarantees a win (unless the number is the product of two primes, or the square or cube of a single prime). If there is any pattern here, it has eluded me. Contrast this with the classic game of Nim, in which the winning positions are easy to spot and the winning moves easy to calculate. Nim is often used as an enrichment activity in math classes, but I believe Factor Subtractor has its own pedagogical advantages. In particular, even if students play at random, they are still getting valuable practice doing arithmetic. And children seem to enjoy playing the game, in part because it provides an obvious motivation -- namely winning -- for doing what might otherwise be a tedious worksheet assignment, and in part (to toss around some educational jargon) because it "empowers" them to choose which computations they do. I have a couple of data points worth of support for this: My daughter- in-law, Sanae Tomita, has used the game with a class of middle-school children, and Kurt Hedin, a teach at Bandelier Elementary School in Albuquerque, New Mexico, whom I met and showed the game, has taught it to his fourth-grade class. I would be delighted to hear from other teachers who might have occasion to give Factor Subtractor a try with their students.