Задача 334
Рассыпание бобов

В раю Платона существует бесконечное количество мисок, выложенных в прямую линию.
В каждой миске находится либо конечное число бобов, либо нет бобов вообще.
Ребенок играет в игру, в которой разрешен только один вид хода: забрать два боба из любой миски и положить по одному в каждую из двух соседних мисок.
Игра закончится, когда в каждой миске будет находиться либо один боб, либо ни одного.

К примеру, рассмотрим две рядом расположенные миски, в которых лежат, соответственно, 2 и 3 боба. Все остальные миски - пустые. Следующими восьмью ходами можно завершить игру:

Заданы следующие последовательности:

t0 = 123456.
ti =
ti-1
2
, если ti-1 четно
ti-1
2
926252, если ti-1 нечетно
где ⌊x⌋ - функция округления вниз,
а оператор поэлементного исключающего ИЛИ.
bi = ( ti mod 211) + 1.

Первые два члена этой последовательности равны b1 = 289 и b2 = 145.
Если начать с b1 и b2 бобами в двух соседних мисках, то для завершения игры потребуется 3419100 ходов.

Теперь, рассмотрим 1500 последовательных мисок, в каждой из которых, соответственно, лежат b1, b2,..., b1500 бобов.Остальные миски - пустые. Найдите, сколько ходов необходимо сделать, чтобы завершить игру.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net