|
%I #43 Aug 25 2022 07:04:05
%S 0,2,5,7,10,12,15,17,20,22,34,39,44,52,57,62,65,67,72,85,95,109,119,
%T 124,127,130,132,137,142,147,150,170,177,180,182,187,192,197,204,210,
%U 215,238,243,249,255,257,260,262,267
%N Let S = squares; a(0)=0; a(n) = smallest m such that m - a(i) is not in S for any i < n.
%C Consider the following game: two players make moves in turn, initially the number on the board is n, each move consists of subtracting a perfect square from the number on the board, the player who faces 0 loses. This sequence is the set of losing positions in this game. - Mikhail Dvorkin (mikhail.dvorkin(AT)gmail.com), Jan 27 2008
%C This sequence was investigated by Golomb (1966), who proved that it is infinite. More strongly (as Ruzsa 1984 notes) the number of values up to any given n is at least proportional to sqrt(n). No two numbers in this sequence differ by a square, and this sequence can be defined as the lexicographically first (greedy) sequence with no square differences. It follows from the Furstenberg-Sárközy theorem (e.g., see Sárközy 1978) that its natural density is zero. - _David Eppstein_, Nov 20 2016
%H Karl W. Heuer, <a href="/A030193/b030193.txt">Table of n, a(n) for n = 0..61299</a>
%H Code Golf Stack Exchange, <a href="https://codegolf.stackexchange.com/questions/220159/first-sequence-with-no-square-differences">First sequence with no square differences</a>, 2021.
%H 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 S. 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 I. Ruzsa, <a href="http://dx.doi.org/10.1007/BF02454169">Difference sets without squares</a>, Period. Math. Hungar. 15 (1984), no. 3, 205-209.
%H A. Sárközy, <a href="http://dx.doi.org/10.1007/BF01896079">On difference sets of sequences of integers I</a>, Acta Mathematica Academiae Scientiarum Hungarica, March 1978, Volume 31, Issue 1, pp 125-149.
%H A. Sárközy, <a href="http://dx.doi.org/10.1007/BF01901984">On difference sets of sequences of integers III</a>, Acta Mathematica Academiae Scientiarum Hungarica, September 1978, Volume 31, Issue 3, pp 355-386.
%H A. Sárközy, <a href="http://annalesm.elte.hu/annales21-1978/Annales_1978_T-XXI.pdf">On the difference sets of sequences of integers II</a>, Eotvos Sect. Math. 21(1978), 45-53.
%t moves[n_] := Table[n - i^2, {i, 1, Sqrt[n]}]; gana[n_] := Which[n == 0, False, True,!Select[moves[n], !gana[#] &] =={}]; Select[Range[155] - 1, ! gana[#] &] (* _José María Grau Ribas_, Jul 19 2013 *)
%t Nest[Append[#, Block[{k = Last[#]}, While[AnyTrue[k - #, IntegerQ@ Sqrt@ # &], k++]; k]] &, {0}, 48] (* _Michael De Vlieger_, Jul 11 2018 *)
%Y Cf. A000037, A000290.
%K nonn
%O 0,2
%A _Jan Kristian Haugland_
%E More terms from _Karl W. Heuer_, Jun 13 2013
|
