A014588 -id:A014588 - cp's OEIS frontend

A014589 Nim function for Take-a-Prime (or Subtract-a-Prime) Game.

0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 0, 4, 1, 5, 2, 6, 3, 4, 7, 0, 0, 1, 1, 2, 2, 3, 3, 4, 8, 5, 7, 6, 8, 9, 0, 4, 1, 5, 2, 6, 0, 4, 1, 5, 2, 6, 3, 4, 7, 5, 8, 4, 10, 5, 7, 6, 8, 4, 7, 5, 8, 6, 10, 9, 7, 4, 8, 5, 10, 6, 0, 4, 1, 5, 2, 6, 0, 4, 1, 5, 2, 6, 3

Offset: 0

Achim Flammenkamp

nonn

The zero positions are given by A025043. - Nathan Fox, May 21 2013
Concerning the January 1997 dissertation of Achim Flammenkamp, his home page (currently http://wwwhomes.uni-bielefeld.de/cgi-bin/cgiwrap/achim/index.cgi) has the link shown below, and a comment that a book was published in July 1997 by Hans-Jacobs-Verlag, Lage, Germany with the title Lange Perioden in Subtraktions-Spielen (ISBN 3-932136-10-1). This is an enlarged study (more than 200 pages) of his dissertation. - N. J. A. Sloane, Jul 25 2019
As noted by Alexis Huet, a(n) <= 11 for all n <= 32452842 (see links). - Pontus von Brömssen, Jul 09 2022
From Bert Dobbelaere, Apr 09 2024: (Start)
For n <= 10^9, a(n) <= 11.
For even n <= 10^9, if a(n)=0, n is in {0, 10, 34, 100, 310}.
For even n <= 10^9, if a(n)=1, n is in {2, 12, 36, 102, 312}.
For even n <= 10^9, if a(n)=2, n is in {4, 14, 38, 104, 314, 1574}.
For even n <= 10^9, if a(n)=3, n is in {6, 16, 40, 106, 316, 1576, 1996, 5566}.
The only odd n <= 10^9 for which a(n)=4 is 17.
The only odd n <= 10^9 for which a(n)=5 is 19.
The only odd n <= 10^9 for which a(n)=6 is 21.
The only even n <= 10^9 for which a(n)=7 is 24.
There are no even n <= 10^9 for which a(n)=8 or a(n)=10.
There are no odd n <= 10^9 for which a(n)=11. (End)

R. K. Guy, Unsolved Problems in Number Theory, E26.

Eric M. Schmidt, Table of n, a(n) for n = 0..10000
Achim Flammenkamp, Lange Perioden in Subtraktions-Spielen, Dissertation, Dept. Math., University of Bielefeld, Germany.
Alexis Huet, First 32452843 terms.
Alexis Huet, Nim function for take-a-prime game.

Cf. A025043, A014586-A014588, A355557.

def A014589_list(max) :
    res = []
    for i in range(max+1) :
        moves = list({res[i-p] for p in prime_range(i+1)})
        moves.sort()
        k = len(moves)
        mex = next((j for j in range(k) if moves[j] != j), k)
        res.append(mex)
    return res
print(A014589_list(50))
# Eric M. Schmidt, Jul 20 2013, corrected Eric M. Schmidt, Apr 24 2019

A001581 Winning moves in Fibonacci nim.

Original entry on oeis.org

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

N. J. A. Sloane

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

			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

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).

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.

Cf. A030193.

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

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

cp's OEIS Frontend

A014589 Nim function for Take-a-Prime (or Subtract-a-Prime) Game.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Sage

A019307 First time that the Grundy function G(x) for "subtract-a-Fibonacci-number" takes the value n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

C

Extensions

A001581 Winning moves in Fibonacci nim.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Python

Extensions