На левом краю клетчатой полосы стоит фишка...

[Ktina]

На левом краю клетчатой полосы стоит фишка. Играют двое. За ход разрешается передвинуть фишку вправо на количество клеток, равное простому числу. Проигрывает тот, кто не может сделать ход. При какой длине полосы выигрывает начинающий, а при какой - его партнёр?

Простым перебором можно убедиться, что если длина полосы равна $1, 2, 10, 11, 26, 35$ или $36$, то выигрывает второй. Есть ли тут какая-то закономерность? Кто, например, выиграет, если длина полосы равна $1000$? Как это вычислить без перебора?

[daniel starodubtsev]

A072545?

[Aritaborian]

(daniel starodubtsev)

Тут специально для таких страдальцев, как вы и Ktina, (да и сам его использую иногда), придуман тег [oeis]. Кнопка находится над полем набора текста, среди всех прочих.

[daniel starodubtsev]

Я для удобства немного переформулирую задачу: Выбирается неотрицательное начальное число $n$. Далее в свой ход разрешается вычесть из него простое число. Если после очередного хода игрока получилось отрицательное число - он проиграл. Тут второй игрок выигрывает при $n = 0,1,9,10,25,34,35$... Здесь можно было бы побеждать, всегда оставляя противнику число, являющееся квадратом нечетного числа, то есть $n = (2k - 1)^2 = 4k^2-4k+1$, однако это получится сделать не всегда (например при $n = 32$ первый игрок может использовать эту тактику, а при любом нечетном $n \ne k^2+2$ - нет)