From:           dbush@csugrad.cs.vt.edu (David Bush)
Newsgroups:     sci.math
Subject:        the uniqueness of 11,356
Summary:        The infinite z-list has only one ending in a 6.
Keywords:       number theory z-list
Date:           12 Oct 92 17:48:00 GMT
Organization:   Virginia Tech Computer Science Dept, Blacksburg, VA

   Here's a curious sidepath in number theory, based on an
old "problematical recreations" puzzle from Litton Industries.
In the game "subtract-a-square," a natural number is written
down and two players alternate moves. A move consists of
subtracting a nonzero square from the current value, producing
a new current value for the other player. You may not subtract
more than the current value. The player who reaches 0 wins.
For example, 1 is a winning value because having this value on
your move means you can win the game. In fact, from 1 you can
win in 1 move by subtracting 1. 2, on the other hand, is a
"zugzwang value," or z-value, because no matter what move you
make, your opponent will be left with a winning value. In fact
the only legal move from 2 is to subtract 1 leaving 1 for the 
other player. Every natural number is either a winning value
or a z-value, but never both. Zugzwang is a chess term
indicating a position wherein the obligation to move is a
disadvantage. The z-list, or the set of all z-values, can be
generated by these production rules:

  1. 0 is the first z-value. (This simplifies matters.)
  2. Given that you have a list of all z-values less than n,
     n is a winning
     value IF AND ONLY IF it is greater than some z-value on
                          the list by a nonzero square.
           OTHERWISE, n must be a z-value.

    Out of all the over 180,000 z-values less than 40 million,
ONLY ONE z-value ends in a 6: 11,356. Z-values that end in 1,
3, or 8 are also few and far between. I suspect the set of
all z-values that = 1(mod 5) or 3(mod 5) is finite. Perhaps
this has something to do with the fact that both 5 and 10 can
be expressed as the sum of 2 different squares. A cursory
statistical analysis of the distribution of z-values with
respect to other modulus bases seems to corroborate this.
Modulus bases 13 and 17, which can also be expressed as the
sum of 2 different squares, show some uneven distribution, but
nothing as severe as bases that are multiples of 5. Other
bases, which are neither the sum of 2 different squares nor
multiples of such a base, show remarkably even distribution.
   The set of z-pairs, or z-values that differ by 2, appears
to be infinite. The largest such pair found so far is
39,955,435 and 39,955,437. The z-list itself must be infinite,
since assuming there exists some greatest z-value G leads to
a contradiction when you consider that G^2 + G + 1 must be a
z-value.
   There are plenty of directions to go from here; for example
there are related games "subtract-a-cube," "subtract-a-power"
etc. One could abandon the restriction that the generation
rules be based on any game at all. Regrettably, my only access
to the net is through a monitor, so I cannot send my software
or data. Thanks for your time.  :)

Newsgroups:     sci.math
From:           cet1@cus.cam.ac.uk (C.E. Thompson)
Subject:        Re: the uniqueness of 11,356
Keywords:       number theory z-list
Organization:   U of Cambridge, England
Date:           Sat, 31 Oct 1992 00:02:17 GMT

I am a bit suprised that this thread hasn't been followed up: too rec.puzzle-ish?
For those who have forgotten the context, this is the impartial game in which
positions are non-negative integers, a move decrements the integer by a non-zero
square, and normal ending rules apply (player unable to move loses). The 'z-values'
are the positions with Nim value 0, i.e. which are wins for the second player.

In article <a_rubin.719615301@dn66>, a_rubin@dsg4.dse.beckman.com (Arthur Rubin)
writes:
|> In <Bw0s41.4Bq@csugrad.cs.vt.edu> dbush@csugrad.cs.vt.edu (David Bush) writes:
|> 
|> >    Out of all the over 180,000 z-values less than 40 million,
|> >ONLY ONE z-value ends in a 6: 11,356.
|> Agree up to 2^28 = 268,435,456
|> 
|> >ONLY ONE z-value ends in a 6: 11,356. Z-values that end in 1,
|> >3, or 8 are also few and far between. I suspect the set of
|> >all z-values that = 1(mod 5) or 3(mod 5) is finite.
|> Here they are up to 2^28:
|> 
|> 238, 243, 613, 663, 793, 918, 923, 928, 1978, 2233, 2288, 4323, 7638,
|> 11356, 13093, 13351, 14073, 15613, 17498, 17583, 19223, 25703, 26168,
|> 29668, 30583, 31473, 31688, 34221, 38461, 40671, 52113, 60203, 62298,
|> 68991, 75121, 102928, 131073, 132243, 193518, 259838, 522121, 749853,
|> 1031043, 3687288.
|> 
|> The count modulo 5 of z-values up to 2^28 is: 310665, 8, 355023, 36, 25515
|> so that it does not seem impossible that the number of z-values congruent
|> to 4 mod 5 might also be finite.

It would be interesting to have more statistical data: is the proportion of
z-values congruent to 4 mod 5 decreasing significantly? One can make a hand
waving argument that they ought to disappear eventually, which goes like this.

Consider the distribution of z-values mod N. Numbers are prevented from being
z-values by being a smaller z-value plus a square. Thus an excess of values in
one residue class will tend to suppress subsequent z-values in classes differing
from the first by a quadratic residue mod N, and a deficit to enhance them. If
-1 is a quadratic residue mod N this leads to positive feedback between the two
residue classes, and (especially dramatic hand wave here) one will eventually
kill off the other completely. The non-zero quadratic residues mod 5 being +1
and -1, we see the enhancement of 0 and 2 practically preventing 1 ever appearing
at all, while 3 gets more of a chance with less suppression from 4 than from 2.
0 and 4 are fighting each other and 0 must eventually suppress 4 entirely.

The same sort of effect ought to happen mod 13, 17, 29, ... and it would also
be interesting to have statistics for these also. The argument above would 
suggest that the only surviving residue classes should form a set such that
no pair differ by a quadratic residue.

|> 
|> >   The set of z-pairs, or z-values that differ by 2, appears
|> >to be infinite. The largest such pair found so far is
|> >39,955,435 and 39,955,437.
|> 
|> There are 2816 pairs less than 2^28, with the largest being 268,063,140 and
|> 268,063,150.
   ^^^^^^^^^^^ (Arthur Rubin has sent me e-mail correcting this to 268,063,142)

If the above argument is correct, they ought eventually to disappear, as 2 is
a quadratic residue mod 17 (for example). In fact, the gaps between z-values
should tend to infinity, though no doubt terribly slowly.

Another question concerns the computational cost of determining the z-values
up to N. To compute the Nim values of all positions up to N would cost N^{3/2}
using the obvious methods, but one can do better than this if one only wants 
the z-values as one can use early abort strategies (you know a value is not a
z-value as soon as you have found *one* z-value and *one* square that sum to 
it). How much does/could this save?

Chris Thompson
JANET:    cet1@uk.ac.cam.phx
Internet: cet1@phx.cam.ac.uk