|
| |
|
|
A001581
|
|
Winning moves in Fibonacci nim.
(Formerly M3374 N1359)
|
|
3
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
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
|
|
|
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
|
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.
|
|
|
EXAMPLE
|
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
|
|
|
PROG
|
(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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
