home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #23 / NN_1992_23.iso / spool / sci / math / 13056 < prev    next >
Encoding:
Internet Message Format  |  1992-10-12  |  3.1 KB
  1. Path: sparky!uunet!vtserf!csugrad!dbush
  2. From: dbush@csugrad.cs.vt.edu (David Bush)
  3. Newsgroups: sci.math
  4. Subject: the uniqueness of 11,356
  5. Summary: The infinite z-list has only one ending in a 6.
  6. Keywords: number theory z-list
  7. Message-ID: <Bw0s41.4Bq@csugrad.cs.vt.edu>
  8. Date: 12 Oct 92 17:48:00 GMT
  9. Organization: Virginia Tech Computer Science Dept, Blacksburg, VA
  10. Lines: 52
  11.  
  12.  
  13.    Here's a curious sidepath in number theory, based on an
  14. old "problematical recreations" puzzle from Litton Industries.
  15. In the game "subtract-a-square," a natural number is written
  16. down and two players alternate moves. A move consists of
  17. subtracting a nonzero square from the current value, producing
  18. a new current value for the other player. You may not subtract
  19. more than the current value. The player who reaches 0 wins.
  20. For example, 1 is a winning value because having this value on
  21. your move means you can win the game. In fact, from 1 you can
  22. win in 1 move by subtracting 1. 2, on the other hand, is a
  23. "zugzwang value," or z-value, because no matter what move you
  24. make, your opponent will be left with a winning value. In fact
  25. the only legal move from 2 is to subtract 1 leaving 1 for the 
  26. other player. Every natural number is either a winning value
  27. or a z-value, but never both. Zugzwang is a chess term
  28. indicating a position wherein the obligation to move is a
  29. disadvantage. The z-list, or the set of all z-values, can be
  30. generated by these production rules:
  31.  
  32.   1. 0 is the first z-value. (This simplifies matters.)
  33.   2. Given that you have a list of all z-values less than n,
  34.      n is a winning
  35.      value IF AND ONLY IF it is greater than some z-value on
  36.                           the list by a nonzero square.
  37.            OTHERWISE, n must be a z-value.
  38.  
  39.     Out of all the over 180,000 z-values less than 40 million,
  40. ONLY ONE z-value ends in a 6: 11,356. Z-values that end in 1,
  41. 3, or 8 are also few and far between. I suspect the set of
  42. all z-values that = 1(mod 5) or 3(mod 5) is finite. Perhaps
  43. this has something to do with the fact that both 5 and 10 can
  44. be expressed as the sum of 2 different squares. A cursory
  45. statistical analysis of the distribution of z-values with
  46. respect to other modulus bases seems to corroborate this.
  47. Modulus bases 13 and 17, which can also be expressed as the
  48. sum of 2 different squares, show some uneven distribution, but
  49. nothing as severe as bases that are multiples of 5. Other
  50. bases, which are neither the sum of 2 different squares nor
  51. multiples of such a base, show remarkably even distribution.
  52.    The set of z-pairs, or z-values that differ by 2, appears
  53. to be infinite. The largest such pair found so far is
  54. 39,955,435 and 39,955,437. The z-list itself must be infinite,
  55. since assuming there exists some greatest z-value G leads to
  56. a contradiction when you consider that G^2 + G + 1 must be a
  57. z-value.
  58.    There are plenty of directions to go from here; for example
  59. there are related games "subtract-a-cube," "subtract-a-power"
  60. etc. One could abandon the restriction that the generation
  61. rules be based on any game at all. Regrettably, my only access
  62. to the net is through a monitor, so I cannot send my software
  63. or data. Thanks for your time.  :)
  64.