From:dbush@csugrad.cs.vt.edu (David Bush)Newsgroups:sci.mathSubject:the uniqueness of 11,356Summary:The infinite z-list has only one ending in a 6.Keywords:number theory z-listDate:12 Oct 92 17:48:00 GMTOrganization: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.mathFrom:cet1@cus.cam.ac.uk (C.E. Thompson)Subject:Re: the uniqueness of 11,356Keywords:number theory z-listOrganization:U of Cambridge, EnglandDate: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