A271620 First row (row 0) of the Sprague-Grundy values of "3-pile Sharing Nim".

0, 0, 1, 0, 0, 0, 1, 0, 3, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 12, 0, 1, 0, 0, 0, 1, 0, 2, 0, 1, 0, 0, 0, 1, 0, 3, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 4, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 2, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 3, 0, 1, 0, 0, 0, 1, 0, 3, 0, 1, 0, 0, 0, 1, 0, 2, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 2, 0, 1, 0, 0, 0, 1, 0, 2

Offset: 0

Author

Howard A. Landman, Apr 10 2016

Keywords

• nonn
• easy

Comments

a(n) is G(0,0,n) = G(0,n,n) for 3-pile Sharing Nim.

If n is odd, a(n)=0. If n={4,12,16,20,28} (mod 32), a(n) is also 0.

If n=2 (mod 4), a(n)=1.

Thus all the "interesting" values are for n={0,8,24} (mod 32).

Ho conjectures that the sequence may be bounded. The highest value in the first thousand entries is a(24)=12.

Despite the simplicity of the "uninteresting" values, the "interesting" ones are provably not periodic, which means the entire sequence is not periodic.

Examples

			a(0)=a(1)=0 because there are no moves from (0,0,0) or (0,0,1). a(2)=1 because there is a move from (0,0,2) to (0,1,1), which has no moves and hence is value 0.
		

Links

• Nhan Bao Ho, 3-pile Sharing Nim and the linear time winning strategy, arXiv:1506.06961 [math.CO], 2015, submitted to Theoretical Computer Science D. (Note that Ho indexes everything from 1, but the equations are simpler when indexed from 0, so I have used 0 in this entry.)

Formula

a(n)=0 if and only if n=0 or n=2^{2i}(2j+1) for some i,j>=0. This by itself proves the aperiodicity, since even the locations of the 0's are not periodic. Note that i=0 covers the "n is odd" case, i=1 covers the "n={4,12,20,28} (mod 32)" cases, i=2 covers the "n=16 (mod 32)" case, and i>=3 all fall under "n=0 (mod 32)". Thus the values for n={8,24} (mod 32) can never be 0.

The formula also implies that the limit of the density of zeros as n goes to infinity is 1/2 + 1/8 + 1/32 + 1/128 + ... = 2/3. - Howard A. Landman, Apr 20 2016