A030193 -id:A030193 - 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

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

A224839 a(1) = 1 and a(n) is the smallest number greater than a(n-1) with no square difference with any preceding term.

Original entry on oeis.org

1, 3, 6, 8, 11, 13, 16, 18, 21, 23, 35, 40, 45, 53, 58, 63, 66, 68, 73, 86, 96, 110, 120, 125, 128, 131, 133, 138, 143, 148, 151, 171, 178, 181, 183, 188, 193, 198, 205, 211, 216, 239, 244, 250, 256, 258, 261, 263, 268, 273

Offset: 1

Jean-François Alcover, Sep 18 2013

nonn

The first 11 terms are identical to those of A210570.

This sequence represents the losing positions in the misère version of a one-heap nim game, where players remove a square number of objects (> 0) on their turn. - Kiran Ananthpur Bacche, Feb 23 2025

Jean-François Alcover, Table of n, a(n) for n = 1..1000

Cf. A030193, A210570, A010052.

a224839 n = a224839_list !! (n-1)
a224839_list = f [1..] [] where
   f (x:xs) ys = if all ((== 0) . a010052) $ map (x -) ys
                    then x : f xs (x:ys) else f xs ys
-- Reinhard Zumkeller, May 02 2014

N:= 1000: # to get all terms <= N
V:= Vector(N):
Res:= NULL:
for m from 1 to N do
  if V[m] = 0 then
    V[m]:= 1;
    Res:= Res, m;
    for k from 1 to floor(sqrt(N-m)) do V[m+k^2]:= 1 od:
  fi
od:
Res; # Robert Israel, Nov 30 2016

a[1] = 1; a[n_] := a[n] = For[k = a[n-1]+1, True, k++, If[FreeQ[k - Array[a, n-1], d_ /; IntegerQ[Sqrt[d]]], Return[k]]]; Table[a[n], {n, 1, 40}]

a(n) >= A210570(n) by definition of the latter. - Charles R Greathouse IV, Nov 28 2024

a(n) = A030193(n-1) + 1. - Kiran Ananthpur Bacche, Feb 23 2025

A275432 P-positions for the subtraction game whose allowed moves are the practical numbers (A005153).

Original entry on oeis.org

0, 3, 10, 13, 44, 47, 102, 105, 146, 149, 232, 235, 636, 639, 814, 817, 950, 953, 1208, 1211, 2994, 2997, 4922, 4925, 4996, 4999, 6748, 6751, 8026, 8029, 8478, 8481, 12092, 12095, 14004, 14007, 31934, 31937, 35824, 35827, 41568, 41571, 46118, 46121, 60056, 60059, 62530, 62533, 106986, 106989

Offset: 0

David Eppstein, Nov 20 2016

nonn

According to a general theorem of Golomb (1966) on subtraction games, this sequence is infinite, and more strongly (because of known results on the density of A005153) the number of terms below any given n is at least logarithmic in n.

			For instance, 10 is a P-position because each of the available moves (subtracting 1, 2, 4, 6, or 8 to yield 9, 8, 6, 4, or 2) can be countered: from 8, 6, 4, or 2, it is possible to win by moving directly to 0 and from 9 it is possible to win by subtracting 6 and moving to the smaller P-position 3.

S. W. Golomb, A mathematical investigation of games of "take-away", J. Combinatorial Theory, 1 (1966), 443-458.

Cf. A030193.

A338027 Lengths of games in optimal play of "subtract-a-square".

Original entry on oeis.org

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

Offset: 0

Josh Bauer, Oct 07 2020

nonn

Consider a game of "take away" where at each turn a player is presented with an integer. The valid moves are to subtract a nonzero perfect square less than or equal to the starting number to generate the number that will be given to your opponent. The person who is given 0 loses the game. The winner's goal is to win in as few moves as possible, and the loser wants to force the winner to take as many moves as possible. a(n) is the length of the game with starting number n and perfect play by both players.

The optimal strategy in the game is a minimax strategy as follows: Given a starting number n, take away all squares less than n and determine whether playing any of those moves leaves your opponent with a "losing" number. If so, choose the move that leaves your opponent with a loss in the smallest number of moves assuming both of continue with this strategy. If you cannot leave your opponent with a "losing" number, then choose the move that maximizes the number of moves your opponent must take to win assuming both of you continue with this strategy. By applying this strategy recursively with a base case of "the player with 0 as their start loses in 0 moves," a game length for any possible starting position may be determined.

			If the starting number is 0, then the starting player loses immediately (in 0 turns), so a(0) = 0. If the starting number is a perfect square, the player can give their opponent a 0 in one move by subtracting the square immediately, thus a(n^2) = 1. If the starting number is 15, the player whose turn it is cannot win unless the other player plays suboptimally. An example optimal game from this point would be: 15 (loser takes away 4), 11 (winner takes away 9), 2 (loser takes away 1), 1 (winner takes away 1), 0 (current player loses). Thus a(15) = 4, a(11) = 3, a(2) = 2, a(1) = 1, and a(0) = 0.

Josh Bauer, Table of n, a(n) for n = 0..10000
Josh Bauer, Annotated implementation in python running in O(n^(3/2)) to get the first n terms

A030193 gives all indices at which this sequence has an even value (corresponding to the losing positions).

Python
```
# See Bauer link
```

Let S(n) be the set of nonzero perfect squares less than or equal to n. Let E be the set of even numbers.
a(0) = 0;
a(n) = Min_{a(n - s) with s in S(n) and a(n - s) in E} + 1 if there are any values of s in S(n) for which a(n - s) is in E. Otherwise:
a(n) = Max_{a(n - s) with s in S(n)} + 1.

A102664 Lexically least sequence of distinct positive integers such that for all j and k, 1+a(j)-a(k) is 0, 1 or not a square.

Original entry on oeis.org

1, 2, 3, 7, 8, 12, 13, 14, 19, 24, 30, 35, 40, 41, 46, 52, 53, 57, 58, 63, 69, 74, 79, 80, 85, 86, 90, 91, 96, 97, 108, 119, 124, 130, 135, 136, 141, 147, 158, 163, 164, 174, 186, 191, 213, 224, 245, 288, 297, 299, 316, 322, 327, 338, 339, 349, 350, 355, 366, 383, 389

Offset: 1

Brendan McKay and Don Reble, Jan 27 2005

Build up an array in which the rows are the numbers n^2 + k - 1, where k is the smallest number that has not yet been covered:
1, 4, 9,16,25,...
2, 5,10,17,26,...
3, 6,11,18,27,...
7,10,15,22,...
8,11,16,23,...
12,15,20,27,...
13,16,21,28,...
14,17,22,29,...
19,22,27,...
24,27,...
30,...
Sequence gives first column.

Cf. A030193.

More terms from David Wasserman, Apr 09 2008

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

A001581 Winning moves in Fibonacci nim.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Python

Extensions

A224839 a(1) = 1 and a(n) is the smallest number greater than a(n-1) with no square difference with any preceding term.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

A275432 P-positions for the subtraction game whose allowed moves are the practical numbers (A005153).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A338027 Lengths of games in optimal play of "subtract-a-square".

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

A102664 Lexically least sequence of distinct positive integers such that for all j and k, 1+a(j)-a(k) is 0, 1 or not a square.

Views

Author

Keywords

Comments

Crossrefs

Extensions