Newsgroups: rec.puzzles
From: hoey@aic.nrl.navy.mil (Dan Hoey)
Date: 05 Dec 1994 16:46:10 GMT
Subject: Re: number theory stuff

rstim...@silver.ucs.indiana.edu (robert and stimets) wrote:

> >>can someone post describe all of the
> >>numbers n for which n! is evenly divisible by 4?
> >>Those that are   6,7,10,11,12,13,18,19,20,21,....
> >>Those that aren't  1,2,3,4,5,8,9,14,15,16,17,.....

and later clarified that he meant:

> ... that n! be divisible by an even number of factors of two, i.e.
> n! = (4^m) * k for some odd k.

In that case, you have misclassified 1, and we may as well throw in
zero: certainly 0!=1!=(4^0)*1 is of the requested form.  These are
the numbers whose binary representation contains an even number of one
bits, not counting the units place.  An easy induction shows that the
two characterizations are equivalent.

This is an important set: it is the "sparse space" of rare G-values
for Grundy's game (In Grundy's game players alternately split a heap
of stones into two unequal piles; the player to move loses when all
heaps have 1 or 2 stones.)  The G-values have been calculated up to
G(10^9), and only 1273 in that range are rare, of which G(82860)=108
is the last.  If, as seems likely, there are only finitely many rare
G-values, then the sequence G(n) will be periodic for sufficiently
large (but perhaps very, very large) n.

To read about this, see _Winning Ways_ by Berlekamp, Conway, and Guy.
There is also information about the problem in an AMS monograph
collection edited by Guy--the title is something like _Combinatorial
Games_.

ObPuzzle: Describe the numbers whose factorials are (27^m)*k for k not
          divisible by 3.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil