A014589 -id:A014589 - cp's OEIS frontend

A014586 Nim-Grundy function for Take-a-Square (or Subtract-a-Square) game.

0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 3, 2, 3, 4, 5, 3, 2, 3, 4, 0, 1, 2, 3, 2, 0, 1, 2, 3, 2, 0, 1, 2, 3, 2, 3, 4, 5, 0, 1, 3, 4, 5, 0, 1, 3, 4, 5, 0, 1, 3, 0, 1, 0, 1, 2, 4, 3, 0, 1, 5, 6, 2, 3, 4, 5, 6, 2, 3, 4, 5, 0, 1, 6, 3, 2, 4, 2, 6, 4, 5, 0, 1, 6, 4

Offset: 0

Achim Flammenkamp

nonn

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

R. K. Guy, Unsolved Problems in Number Theory, E26.
W. W. Rouse Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, 12th Edition.

Eric M. Schmidt, Table of n, a(n) for n = 0..10000 (corrected by _Eric M. Schmidt_, Apr 23 2019)
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.
Achim Flammenkamp, Lange Perioden in Subtraktions-Spielen, Dissertation, Dept. Math., University of Bielefeld, Germany.
Sean A. Irvine, Java program (github)
Wikipedia, Sprague-Grundy theorem

Cf. A030193, A014587-A014589, A297963.

def A014586_list(max) :
    res = []
    for i in range(max+1) :
        moves = list({res[i-r^2] for r in range(1, isqrt(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
A014586_list(100)
# Eric M. Schmidt, Jul 20 2013, corrected Eric M. Schmidt, Apr 23 2019

a(n) = 0 iff n belongs to A030193. - Rémy Sigrist, May 30 2019

A014587 Nim function for Take-a-Factorial-Game (a subtraction game).

Original entry on oeis.org

0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2

Offset: 0

Achim Flammenkamp

nonn

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

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.

Cf. A014586-A014589, A355556.

def A014587(max) :
    res = []
    fact = [1]
    while fact[-1] <= max : fact.append(factorial(len(fact)))
    for i in range(max+1) :
        moves = list({res[i-f] for f in fact if f <= i})
        moves.sort()
        k = len(moves)
        mex = next((j for j in range(k) if moves[j] != j), k)
        res.append(mex)
    return res
# Eric M. Schmidt, Jul 20 2013, corrected Eric M. Schmidt, Apr 24 2019

Conjecture: Appears to be periodic with period of length 25 =  [0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3] starting with the initial term (there is no preamble). - Michel Dekking, Jul 26 2019
This conjecture is false, because moving from 10! = 3628800 to 0 is a legal move, and so a(3628800) cannot be zero. A similar argument shows that for no value of P is this sequence periodic with period P starting at term 0 (for a(P!) cannot be zero). - Nathan Fox, Jul 28 2019.
The first counterexample to the conjecture above is a(5050) = 4. - Pontus von Brömssen, Jul 09 2022

A014588 Nim function for Take-a-Fibonacci-Game (a subtraction game).

Original entry on oeis.org

0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 0, 1, 2

Offset: 0

Achim Flammenkamp

nonn

This game is also called Fibonacci nim, but there is also a different game with the same name. Its winning positions (the indexes of zeros in this sequence) are A001581 and its (much sparser) odd winning positions are A120904. - David Eppstein, Jun 14 2018

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

R. K. Guy, Unsolved Problems in Number Theory, E26.
David L. Silverman, Your Move, McGraw Hill, 1971, page 211. Reprinted by Dover Books, 1991 (mentions this game).

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.
Wikipedia, Sprague-Grundy theorem

Cf. A001581, A014586-A014589, A019307, A120904.

def A014588(max) :
    res = []
    for i in range(max+1) :
        moves = list({res[i-f] for f in fibonacci_xrange(1,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
# Eric M. Schmidt, Jul 20 2013, corrected Eric M. Schmidt, Apr 24 2019

A227691 Winning positions in the Subtract-a-Prime game.

Original entry on oeis.org

2, 3, 4, 5, 6, 7, 8, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 27, 28, 29, 30, 31, 32, 33, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 50, 51, 52, 53, 54, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74

Offset: 1

José María Grau Ribas, Jul 19 2013

nonn

Consider the following game: two players make moves in turn, initially the number on the board is n. Each move consists of subtracting a prime number that is at most the number on the board. The player who cannot play loses. This sequence is the set of winner positions in this game.

Complement of A025043.

The Grundy numbers of this game are in A014589.

moves[n_] := Table[n - Prime[i], {i, 1, PrimePi[n]}]
gana[n_] := gana[n] = If[n < 2, False,! Select[moves[n],!gana[#] &] == {}];
Select[Range[155], gana[#] &]

is(n)=if(isprime(n) || isprime(n-1), return(1)); if(n<15,return(0)); for(k=9,n-1,if(isprime(n-k) && !is(k), return(1))); 0 \\ Charles R Greathouse IV, Nov 13 2013

A355557 a(n) is the smallest position in the subtract-a-prime game for which the value of the Sprague-Grundy function (or nim-value) is n.

Original entry on oeis.org

0, 2, 4, 6, 8, 19, 21, 23, 43, 48, 67, 156

Offset: 0

Pontus von Brömssen, Jul 09 2022

a(12) > 32452842 (if it exists). See A014589.

a(12) > 10^9 if it exists. - Bert Dobbelaere, Apr 09 2024

			a(5) = 19, because the smallest k for which A014589(k) = 5 is k = 19.

Cf. A014589, A019307, A297963, A355556.

cp's OEIS Frontend

A014586 Nim-Grundy function for Take-a-Square (or Subtract-a-Square) game.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Sage

Formula

A014587 Nim function for Take-a-Factorial-Game (a subtraction game).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Sage

Formula

A014588 Nim function for Take-a-Fibonacci-Game (a subtraction game).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Sage

A227691 Winning positions in the Subtract-a-Prime game.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

A355557 a(n) is the smallest position in the subtract-a-prime game for which the value of the Sprague-Grundy function (or nim-value) is n.

Views

Author

Keywords

Comments

Examples

Crossrefs