- FindStat

edit this statistic or download as text // json

Identifier

St000792: Binary words ⟶ ℤ

Values

0 => 0

1 => 1

00 => 0

01 => 2

10 => 1

11 => 3

000 => 0

001 => 1

010 => 2

011 => 3

100 => 1

101 => 0

110 => 3

111 => 2

0000 => 0

0001 => 4

0010 => 1

0011 => 5

0100 => 2

0101 => 6

0110 => 3

0111 => 7

1000 => 1

1001 => 5

1010 => 0

1011 => 4

1100 => 3

1101 => 7

1110 => 2

1111 => 6

00000 => 0

00001 => 1

00010 => 4

00011 => 5

00100 => 1

00101 => 0

00110 => 5

00111 => 4

01000 => 2

01001 => 3

01010 => 6

01011 => 7

01100 => 3

01101 => 2

01110 => 7

01111 => 6

10000 => 1

10001 => 0

10010 => 5

10011 => 4

10100 => 0

10101 => 1

10110 => 4

10111 => 5

11000 => 3

11001 => 2

11010 => 7

11011 => 6

11100 => 2

11101 => 3

11110 => 6

11111 => 7

000000 => 0

000001 => 2

000010 => 1

000011 => 3

000100 => 4

000101 => 6

000110 => 5

000111 => 7

001000 => 1

001001 => 3

001010 => 0

001011 => 2

001100 => 5

001101 => 7

001110 => 4

001111 => 6

010000 => 2

010001 => 0

010010 => 3

010011 => 1

010100 => 6

010101 => 4

010110 => 7

010111 => 5

011000 => 3

011001 => 1

011010 => 2

011011 => 0

011100 => 7

011101 => 5

011110 => 6

011111 => 4

100000 => 1

100001 => 3

100010 => 0

100011 => 2

100100 => 5

100101 => 7

100110 => 4

>>> Load all 2189 entries. <<<

search for individual values

searching the database for the individual values of this statistic

/ search for generating function

searching the database for statistics with the same generating function

click to show known generating functions

Description

The Grundy value for the game of ruler on a binary word.
Two players alternately may switch any consecutive sequence of numbers that ends with a 1. The player facing the word which has only 0's looses.

References

[1] Lugo, M. Sprague-Grundy sequence for the ruler game MathOverflow:39165

Code

def statistic(w):
    two_adic = Zp(2)
    res = 0
    for i, e in enumerate(w):
        if e == 1:
            res = res^^(2^ZZ((two_adic(i+1).ordp())))
    return res

# CodeLanguage: Sage, naive implementation
@cached_function
def statistic_alt(w):
    """Return the Grundy value of the binary word w for the ruler game.

    """
    def children(w):
        for i in range(len(w)):
            if w[i] == 1:
                for j in range(i+1):
                    yield w[:j] + tuple(1-w[k] for k in range(j,i+1)) + w[i+1:]

    l = [statistic_alt(tuple(v)) for v in children(tuple(w))]
    i = 0
    while i in l:
        i += 1
    return i

Created

May 01, 2017 at 07:36 by Martin Rubey

Updated

May 02, 2018 at 23:04 by Martin Rubey