A001581 Winning moves in Fibonacci nim.

4, 10, 14, 20, 24, 30, 36, 40, 46, 50, 56, 60, 66, 72, 76, 82, 86, 92, 96, 102, 108, 112, 118, 122, 128, 132, 138, 150, 160, 169, 176, 186, 192, 196, 202, 206, 212, 218, 222, 228, 232, 238, 242, 248, 254, 260, 264, 270, 274, 280, 284, 290, 296, 300, 306, 310

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice

Comments

The "Fibonacci nim" considered here is the one with a pile of n stones from which, at each move, a player removes a Fibonacci number of stones, with the last player to move winning. It should be distinguished from a different game with the same name, in which any number of stones up to twice the previous move can be removed. The nim-values for this game are given in A014588; this sequence gives the indexes at which A014588 is zero. Most of the winning positions of the game appear to be even, but some (for instance 169) are not; A120904 gives the odd winning positions. - David Eppstein, Jun 14 2018

With an initial 0, the lexicographically least sequence such that all pairwise differences are in A001690 (complement of the Fibonacci numbers). - Charlie Neder, Feb 23 2019

As first observed by Pond and Howells (1965), the density of this sequence is at most 1/5, since a(n+1) - a(n) = 4 implies a(n+2) - a(n+1) != 4 (because otherwise a(n+2) - a(n) = 8 would be a Fibonacci number), and a(n+2) - a(n+1) != 1, 2, 3, 5 (because those are Fibonacci numbers), so a(n+2) - a(n+1) >= 6, implying that the average gap between consecutive a(n) is at least 5. Golomb (1966), Theorem 4.1 implies that this sequence is infinite. The first person to pose this problem seems to be Brother U. Alfred (1963). Empirically (for a(n)<=10^6 at least), Bacher (2023) observed that the plot of a(n)/n oscillates somewhat like a sawtooth between roughly 5.5 and 6.2, and also that the values of a(n) appear largely equidistributed modulo an odd integer. Only 384 of the first 100,000 terms of this sequence are odd. - Boon Suan Ho, Oct 05 2023

In his 1992 dissertation, Simon Plouffe conjectured that the generating function of this sequence is given by 2(1 + z)(3z^5 + 2z^3 + z^2 + z + 2) / ((z^6 + z^5 + z^4 + z^3 + z^2 + z + 1)(z - 1)^2). This agrees with the sequence up to the z^26 term in the expansion (138z^26), but disagrees at z^27 with coefficient 144 instead of 150. - Boon Suan Ho, Oct 07 2023

Examples

			Starting with a heap of size 10, your opponent can move to 9, 8, 7, 5, or 2. If your opponent moves to 8, 5, or 2, you can move directly to 0, and if they move to 9 or 7, you can move to 4, a winning position. Therefore 10 is also winning. - _Charlie Neder_, Feb 23 2019
Interpreting this sequence together with a(0) = 0 as the lexicographically least subset of nonnegative integers with no two elements differing by a (positive) Fibonacci number, we have a(1) = 4, since a(0) = 0, and a(1) - a(0) cannot be 1, 2, or 3 as they are Fibonacci numbers. Then a(2) = 10, since a(2) - a(1) cannot be 1, 2, 3, or 5, and a(2) - a(0) cannot be 8. - _Boon Suan Ho_, Oct 05 2023
		

References

• David L. Silverman, Your Move, McGraw Hill, 1971, page 211. Reprinted by Dover Books, 1991 (mentions this game).
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Boon Suan Ho, Table of n, a(n) for n = 1..165109 (first 1000 terms from Charlie Neder)
• Brother U. Alfred, Exploring Fibonacci numbers, Fibonacci Quarterly 1(1) (1963), 63.
• Roland Bacher, The smallest sequence without differences among Fibonacci numbers, Question 455779 at MathOverflow (October 2023).
• David Eppstein, Faster Evaluation of Subtraction Games, Proceedings of the 9th International Conference on Fun with Algorithms (FUN 2018), Leibniz International Proceedings in Informatics, arXiv:1804.06515 [cs.DS], 2018.
• Solomon W. Golomb, A mathematical investigation of games of "take-away", J. Combinatorial Theory, 1 (1966), 443-458.
• Boon Suan Ho, Plot of a(n)/n for n<=165000
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Jeremy C. Pond and Donald F. Howells, More on Fibonacci Nim, Fibonacci Quarterly 3(1) (1965), 61-62.

Crossrefs

Cf. A030193.

Programs

Python

def a(n):
    # returns list of values a(k) that are at most equal to n
    fib = []
    a, b = 1, 2
    while a <= n:
        fib.append(a)
        a, b = b, a+b
    # `fib` now contains distinct positive Fibonacci numbers that are <= n
    seq = []
    for m in range(n+1):
        # inefficient; see Eppstein (2018) on how to speed up
        if all(m-ai not in fib for ai in seq):
            seq.append(m)
    return seq[1:] # seq[0] == 0

Extensions

More terms from Franklin T. Adams-Watters, Jul 14 2006