cp's OEIS Frontend

A001581 Winning moves in Fibonacci nim.

%I A001581 M3374 N1359 #57 Jan 05 2025 19:51:32
%S A001581 4,10,14,20,24,30,36,40,46,50,56,60,66,72,76,82,86,92,96,102,108,112,
%T A001581 118,122,128,132,138,150,160,169,176,186,192,196,202,206,212,218,222,
%U A001581 228,232,238,242,248,254,260,264,270,274,280,284,290,296,300,306,310
%N A001581 Winning moves in Fibonacci nim.
%C A001581 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
%C A001581 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
%C A001581 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
%C A001581 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
%D A001581 David L. Silverman, Your Move, McGraw Hill, 1971, page 211. Reprinted by Dover Books, 1991 (mentions this game).
%D A001581 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001581 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A001581 Boon Suan Ho, <a href="/A001581/b001581.txt">Table of n, a(n) for n = 1..165109</a> (first 1000 terms from Charlie Neder)
%H A001581 Brother U. Alfred, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/1-1/alfred3.pdf">Exploring Fibonacci numbers</a>, Fibonacci Quarterly 1(1) (1963), 63.
%H A001581 Roland Bacher, <a href="https://mathoverflow.net/q/455779/">The smallest sequence without differences among Fibonacci numbers</a>, Question 455779 at MathOverflow (October 2023).
%H A001581 David Eppstein, <a href="https://arxiv.org/abs/1804.06515">Faster Evaluation of Subtraction Games</a>, Proceedings of the 9th International Conference on Fun with Algorithms (FUN 2018), Leibniz International Proceedings in Informatics, arXiv:1804.06515 [cs.DS], 2018.
%H A001581 Solomon W. Golomb, <a href="http://dx.doi.org/10.1016/S0021-9800(66)80016-9">A mathematical investigation of games of "take-away"</a>, J. Combinatorial Theory, 1 (1966), 443-458.
%H A001581 Boon Suan Ho, <a href="/A001581/a001581.png">Plot of a(n)/n for n<=165000</a>
%H A001581 Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H A001581 Jeremy C. Pond and Donald F. Howells, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/3-1/pond.pdf">More on Fibonacci Nim</a>, Fibonacci Quarterly 3(1) (1965), 61-62.
%e A001581 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
%e A001581 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
%o A001581 (Python)
%o A001581 def a(n):
%o A001581     # returns list of values a(k) that are at most equal to n
%o A001581     fib = []
%o A001581     a, b = 1, 2
%o A001581     while a <= n:
%o A001581         fib.append(a)
%o A001581         a, b = b, a+b
%o A001581     # `fib` now contains distinct positive Fibonacci numbers that are <= n
%o A001581     seq = []
%o A001581     for m in range(n+1):
%o A001581         # inefficient; see Eppstein (2018) on how to speed up
%o A001581         if all(m-ai not in fib for ai in seq):
%o A001581             seq.append(m)
%o A001581     return seq[1:] # seq[0] == 0
%Y A001581 Cf. A030193.
%K A001581 nonn,nice
%O A001581 1,1
%A A001581 _N. J. A. Sloane_
%E A001581 More terms from _Franklin T. Adams-Watters_, Jul 14 2006