At Play With J

31. J be Nimble, J be Quick: Nim Addition

By Eugene McDonnell. First published in Vector, 19, 1, (June 2002), 108-118.

Nim Addition

Nim is a simple game that someone knowledgeable playing against someone naive can almost always win. It was featured in the 1960s film Last Year in Marienbad, where two men in a bar play with a number of piles of matchsticks. The players, in turn, take any number of matchsticks from any one of the piles. The object is to be the player who takes the last match or matches. Its name came perhaps from nimm, the third person singular imperative of the verb nehmen. The trick in Nim is knowing that a position is either safe or unsafe, depending on whether the Nim sum of the number of matches in each pile is or is not zero. The Nim sum can be obtained by converting the number of matchsticks in each pile to binary, and inserting not-equals, or exclusive-or over this, then converting back to integer. For example, if there are three piles, with three, five, and seven matches in the piles, the Nim sum is obtained in three steps. First, the binary forms of the numbers are taken:

   piles =: 3 5 7
   #: piles
0 1 1
1 0 1
1 1 1

The not-equal function yields the parity of its summands:

   ~: / #: piles
0 0 1

This is converted to decimal:

   #. ~: / #: piles
1

The function NS encapsulates this:

   NS =: ~: / &. #: NB. not-equal insert dual antibase
   NS piles
1

A safe move can be made if and only if the Nim sum of the piles is not zero, meaning unsafe. If a position is safe, any move will change it to unsafe. Furthermore, if the Nim sum of the piles is nonzero, it can always be made safe by subtracting from one of the piles. There will always be at least one such pile. For example, given the piles 3 5 7, with Nim sum 0 0 1, we can subtract one from any one of the piles. Thus, three different safe moves can be made, resulting in one of 2 5 7 or 3 4 7 or 3 5 6.

   NS"1 [ 2 5 7, 3 4 7,: 3 5 6
0 0 0

The choice of which pile to subtract from, when more than one is a candidate, is arbitrary.

Now, suppose we have a Nim sum of a list of piles that is a bit more complicated (the function h displays the binary form of the piles and its binary sum):

   h =: ,. @ (#: ; [: ~:/ #:)
   h 10 11 4
+-------+
|1 0 1 0|
|1 0 1 1|
|0 1 0 0|
+-------+
|0 1 0 1|
+-------+

The only solution for this is to subtract 3 from the last pile, which yields 10 11 1:

   h 10 11 1
+-------+
|1 0 1 0|
|1 0 1 1|
|0 0 0 1|
+-------+
|0 0 0 0|
+-------+

There is a certain amount of art in playing a winning game of Nim.

Nim multiplication

John H. Conway and Richard K. Guy have written The Book of Numbers. I was encouraged to read this by Ken Iverson's Lab which uses J to explore many of the parts of this book. Its last chapter is "Infinite and Transcendental Numbers", and in it, to my surprise, is a discussion of the game of Nim. Conway/Guy choose to call our ordinary decimal integers, in the Nim context, as nimbers. I think they are confusing the numbers involved with the functions used with them. Conway and Guy, in addition to discussing Nim addition, also treat Nim multiplication, which they state is valuable in studying the digital transmission of information, in particular "the integral lexicographical code of minimal distance 3". They give a multiplication table for the first sixteen nonnegative integers. They also write

And here's all you need to know about the multiplication of nimbers:

If the 'larger' of two different nimbers is 1 or 2 or 4 or 16 or 256 or 65536 or 4294967296 or ', you multiply them just as you multiply the corresponding ordinary numbers. The product of one of these special nimbers with itself is obtained by taking 1 1/2 times its ordinary value.

I found it impossible to use this rule for nimbers greater than 4. I turned to Google for help, and found that Sloane's On Line Encyclopedia of Integer Sequences contained entries on Nim multiplication. Two of these had a function which built a Nim multiplication table. The problem was that the function was written in Maple, and although I am able to read very simple Maple, this one used built-in functions with meanings I couldn't grasp, even after I found a Maple manual on the Web. After weeks of trying to come to terms with it, appealing for help to several people I thought could help, but didn't, I wrote appeals to Conway and Guy, and also appealed to the J discussion group on the Web for help. Both pleas were successful; Professor Guy replied to my letter, and Mike Day read my appeal to the J group, was able to decipher the Maple, and turned it into J. Ken Iverson made some revisions to it and I added my own changes. Here is its latest manifestation:

mt=: monad define
iN=.i.N=.y 
MT=.(>.|:)iN 1}0$~,~N
for_a. 2}.iN do.for_b. a}.iN do.
 c=.a,b,|:(#:i.@*/)a,b
 r=.<"1[0 1|:(2 1,0 3,:2 3){c
 t=.~.(~:/&.#:)"1 r{"1 2 MT
 j=.(0:i.~]e.~[:i.2:+>./)t
 MT=.j((;|.)a,b)}MT
end.end.
)

The argument N=.y is the size of the square desired. Nim multiplication is commutative so the derivation of one nondiagonal value allows its symmetrical twin to be created at the same time. The list iN of the first N nonnegative integers serves to initialize row 1 and column 1, and is also used to determine the values of the loop counters a and b. An NxN matrix of zeros is created (0$~,~N) and its first row is amended with iN; column 1 is set by choosing the maximum of this matrix and its transpose (>.|:). For N=5 the result is:

   y =:5
   ]iN=.i.N=.y 
0 1 2 3 4
   ]MT=.(>.|:)iN 1}0$~,~N
0 0 0 0 0
0 1 2 3 4
0 2 0 0 0
0 3 0 0 0
0 4 0 0 0

The first value to be created is that in row 2, column 2. After that comes row 2 column 3 and row 3 column 2, and so on until row 2 is completed. Then comes 3 3 and 3 4 (and 4 3), and finally 4 4. The process for 2 2 is as follows:

   a=.b=.2
   |:(#:i.@*/)a,b
0 0 1 1
0 1 0 1

The matrix gets two new rows, a row of all a's on a row of all b's. The resulting four rows correspond to those labeled a, b, i and j in the Maple function. Combinations of these rows can be assembled so that critical values preceding the one currently being made can be used according to a rule which I can't explain, since I don't understand it.

   ]c=.a,b,|:(#:i.@*/)a,b
2 2 2 2
2 2 2 2
0 0 1 1
0 1 0 1

The actual selection uses items at 2 1 (i,b), 0 3 (a,j), and 2 3 (i,j).

   (2 1,0 3,:2 3){c
0 0 1 1
2 2 2 2

2 2 2 2
0 1 0 1

0 0 1 1
0 1 0 1

These are transposed by placing the first two axes at the end (0 1|:)

   0 1|:(2 1,0 3,:2 3){c
0 2
2 0
0 0

0 2
2 1
0 1

1 2
2 0
1 0

1 2
2 1
1 1

In order for these to be used as indices to MT, their rows are boxed:

    ]r=.<"1[0 1|:(2 1,0 3,:2 3){c
+---+---+---+
|0 2|2 0|0 0|
+---+---+---+
|0 2|2 1|0 1|
+---+---+---+
|1 2|2 0|1 0|
+---+---+---+
|1 2|2 1|1 1|
+---+---+---+

The table of indices selects the needed values: ( r{"1 2 MT ), then the Nim sums of the rows are determined with ( (~:/&.#:)"1 ) and duplicate sums are removed (~.)

   r{"1 2 MT
0 0 0
0 2 0
2 0 0
2 2 1
   t=.~.(~:/&.#:)"1 r{"1 2 MT
   t
0 2 1

The mysterious part comes now. The value j to be stored at (a,b) is the least nonneg not in t. Why this produces the Nim multiplication of a and b is beyond me to explain.

The candidates for j are all in the first 2+>./t nonnegs:

   i.2+>./t
0 1 2 3

The ones already present in t are identified:

   t e.~ 0 1 2 3
1 1 1 0

and j is the index of the first zero in this list:

   0 i.~1 1 1 0
3

Here's the whole:

   ]j=.(0:i.~]e.~[:i.2:+>./)t
3

and here is the finished 5x5 table:

   mt 5
0 0 0  0  0
0 1 2  3  4
0 2 3  1  8
0 3 1  2 12
0 4 8 12  6

We now know how to make a Nim multiplication table, but still don't know how to Nim multiply two arbitrary numbers.

Here is Mike Day's program mt which accurately translates the Maple program I had asked for help with. Without Mike's contribution I couldn't have got any further:

   nimsum =: ~:/&.#:@,"0/~    NB. EEmcD
   mt =: verb define 
iN =. i. >: N =. y
NB. ======================================================
NB. lines 1 to 6
MT =. 0 $~ 2 # N + 1    NB. initialise MT with 0 top & left
MT =. iN 1 } MT         NB. and indices in row 1
NB. MT =. iN 1 }"_1 MT  NB. originally also in col 1
NB. - We can defer symmetrising and just work on diag 
NB. and upper triangle
NB. ======================================================
NB. lines 7 - 11 - should be able to cut out some loops 
                   NB. by eg recursion or scan 
for_a. 2 }. iN do.    
 for_b. iN }.~ a do.  
  t1 =. i. 0           
  for_i. i. a do.
   for_j. i. b do. 
NB. ======================================================
    NB. lines 12-24 are preamble to line 25
    NB. references to stored AT where available  
    NB. or nimsum where not avail. obscures the process - 
    NB. This is ok on a fast m/c and/or for small N

    NB. line 25 (26 is a comment) ... 
    NB. sort refs since using diag and upper triangle only
    refs =. sort each (i,b);(a,j);(i,j)
    t1 =. t1 , nimsum / refs { MT
NB. ======================================================
   end.   NB. line 27
  end.    NB. line 28
NB. ======================================================  
  NB. line 29 - seems to require the nub
  t2 =. sort ~. t1  
NB. ======================================================
  NB. lines 31 - 36 - locate first element of t2 
  NB. not equal to its index
  j =. 1 i.~ t2 ~: i. # t2
NB. ======================================================  
  NB. line 37 only 
  MT =. j (<a,b) } MT  NB. don't need line 38 
NB. ======================================================
 end.     NB. line 39
end.      NB. line 40
NB. ======================================================

NB. extra line to symmetrise
MT + (iN >/ iN) * |: MT   
)

I found that the number of times t the inner j loop of Day's program was used, for differing sizes s of arguments, to be:

The fifth difference of t is zero, so a polynomial of degree 4 could be found:

   diff=:2: -~/\ ]
   t =. 4 19 55 125 245 434 714
   diff t
15 36 70 120 189 280
   diff^:2 t
21 34 50 69 91
   diff^:3 t
13 16 19 22
   diff^:4 t
3 3 3
   diff^:5 t
0 0

The polynomial is formed like this:

   x=:i.#t
   t %. x^/i.5x
4 97r12 43r8 17r12 1r8

These can be made the numerators for a rational polynomial:

   ]c=. 24 2 3 2 3*4 97 43 17 1
96 194 129 34 3
   polyn=: c&p.%24&p.
   polyn i.7
4 19 55 125 245 434 714

I'll make a slight detour here, to explore the result of polyn t further. I found that the fourth degree polynomial for the figurate numbers of order 5 is relevant. These numbers are those in the fifth diagonal of the Pascal triangle. In fact, I found that a multiple of these added to the figurate numbers of order 4 gives us our numbers:

   ]p4=:3!3+i.7
1 4 10 20 35 56 84
   ]p5=:4!4+i.7
1 5 15 35 70 126 210
   p4+3*p5
4 19 55 125 245 434 714

The detour is over. Now I'll use our polynomial to find how often the inner loop is entered for a size 209 table:

   poly 209x
251673415

A quarter of a thousand million iterations seems excessive.

This makes clear how ridiculous and expensive it is to have to make a 209x209 table in order to get the Nim product of 167 and 208! The letter I got from Professor Guy helps here. I had asked him how to Nim multiply 8x8, and his letter showed how, and also how to multiply 5 by 11.

Here it is. He uses the plus and times signs within circles, and I've substituted + and *. I've also replaced his linear ordering of equal statements with Iverson's convention of placing them one below the other.

   Dear Eugene McDonnell,

Nim-multiplication is tricky, but you can probably catch on by remembering to deal with the exponents in the same way that you deal with numbers in nim-addition, namely split them into powers of 2. Nim multiplication of powers of 2 is defined, in the first instance, only for the 'Fermat powers of 2'  

  (2^2^0) = 2
  (2^2^1) = 4
  (2^2^2) = 16
  (2^2^3) = 256
  (2^2^4) = 65536
  ...

  each, after the first, being the square of the previous one, but if instead of 'square' you mean 'nim-multiply by itself', than the answer is defined to be  

  (x*x)
  (3%2)*x

  (just if x is a Fermat power of 2). To deal with other powers of 2, you work at one level higher up, thinking of (2`^`13), for example, as (2`^`(8+4+1)) and use the associative, commutative and distributive laws, e.g.,  

  8*8
  (2^3)*(2^3)
  (2^(2+1))*((2^(2+1))
  (2^2)*(2^1)*(2^2)*(2^1)
  ((2^2)*(2^2))*((2^1)*(2^1))
  (4*4)*(2*2)
  6*3
  (4+2)*(2+1)
  (4*2)+(4*1)+(2*2)+(2*1)
  8+4+3+2
  13

  To deal with numbers which are not powers of 2 leads to a corresponding extra level of complication. E.g.,  

  5*11
  (4+1)*(8+2+1)
  (4*8)+(4*2)+(4*1)+(1*8)+(1*2)+(1*1)
  (4*4*2)+8+4+8+2+1
  (6*2)+7
  ((4+2)*2)+7
  (4*2)+(2*2)+7
  8+3+7
  12

  8 is the first power of 2 that is not a Fermat power, and the first place where you run into any difficulty.

Best wishes,

Yours sincerely,

Richard K. Guy,

Faculty Professor of Mathematics

University of Calgary

I end with complete 16x16 Nim addition and multiplication tables.

Here is the Nim addition table:

   NP=: 4 : 'NS x,y'"0 NB. Nim-Plus based on Nim-Sum
   (NS 3 9) , (3 NP 9) NB. A table-entry (both ways)
10 10
   NP table i.16
+--+-----------------------------------------------+
|  | 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15|
+--+-----------------------------------------------+
| 0| 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15|
| 1| 1  0  3  2  5  4  7  6  9  8 11 10 13 12 15 14|
| 2| 2  3  0  1  6  7  4  5 10 11  8  9 14 15 12 13|
| 3| 3  2  1  0  7  6  5  4 11 10  9  8 15 14 13 12|
| 4| 4  5  6  7  0  1  2  3 12 13 14 15  8  9 10 11|
| 5| 5  4  7  6  1  0  3  2 13 12 15 14  9  8 11 10|
| 6| 6  7  4  5  2  3  0  1 14 15 12 13 10 11  8  9|
| 7| 7  6  5  4  3  2  1  0 15 14 13 12 11 10  9  8|
| 8| 8  9 10 11 12 13 14 15  0  1  2  3  4  5  6  7|
| 9| 9  8 11 10 13 12 15 14  1  0  3  2  5  4  7  6|
|10|10 11  8  9 14 15 12 13  2  3  0  1  6  7  4  5|
|11|11 10  9  8 15 14 13 12  3  2  1  0  7  6  5  4|
|12|12 13 14 15  8  9 10 11  4  5  6  7  0  1  2  3|
|13|13 12 15 14  9  8 11 10  5  4  7  6  1  0  3  2|
|14|14 15 12 13 10 11  8  9  6  7  4  5  2  3  0  1|
|15|15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0|
+--+-----------------------------------------------+

Here is the multiplication table:

  label=: 4 : '(x;":,.i.#y),.({.;}.)":(i.{:$y),y'   
  '**' label mt 16
+--+----------------------------------------------+
|  |0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15|
+--+----------------------------------------------+
|0 |0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0|
|1 |0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15|
|2 |0  2  3  1  8 10 11  9 12 14 15 13  4  6  7  5|
|3 |0  3  1  2 12 15 13 14  4  7  5  6  8 11  9 10|
|4 |0  4  8 12  6  2 14 10 11 15  3  7 13  9  5  1|
|5 |0  5 10 15  2  7  8 13  3  6  9 12  1  4 11 14|
|6 |0  6 11 13 14  8  5  3  7  1 12 10  9 15  2  4|
|7 |0  7  9 14 10 13  3  4 15  8  6  1  5  2 12 11|
|8 |0  8 12  4 11  3  7 15 13  5  1  9  6 14 10  2|
|9 |0  9 14  7 15  6  1  8  5 12 11  2 10  3  4 13|
|10|0 10 15  5  3  9 12  6  1 11 14  4  2  8 13  7|
|11|0 11 13  6  7 12 10  1  9  2  4 15 14  5  3  8|
|12|0 12  4  8 13  1  9  5  6 10  2 14 11  7 15  3|
|13|0 13  6 11  9  4 15  2 14  3  8  5  7 10  1 12|
|14|0 14  7  9  5 11  2 12 10  4 13  3 15  1  8  6|
|15|0 15  5 10  1 14  4 11  2 13  7  8  3 12  6  9|
+--+----------------------------------------------+

This is identical with Table 10.2 in the Conway and Guy book.

Reference

[1] Conway, J. H., Guy, R., The Book of Numbers. Springer (Feb 1998), ISBN 978 0 3879 7993 9.

Endnote

Thanks to RogerHui for the definition of: label.
To produce the addition table we were able to use the standard J utility: table with our own special Nim “plus-sign”: NP, which needs to be called for every entry in the table. But for the multiplication table we have an efficiently computed table: mt 16, hence the need for a special verb: label just to append row and column numbers. Note that label requires a left argument: the character(s) to appear in the top left corner of the formatted output. IanClark

Doc/Articles/Play191

31. J be Nimble, J be Quick: Nim Addition

Reference

Endnote