Задача 692
Зигберт и Джо

Зигберт и Джо играют в игру с кучей из $N$ камней и по очереди ходят:
1. Зигберт первый берет несколько камней. Он может взять столько камней, сколько хочет (от 1 до $N$ включительно).
2. В каждый последующий ход текущий игрок должен взять не меньше одного камня и не больше, чем дважды количество камней, взятых предыдущим игроком.
3. Игрок, взявший последний камень, побеждает.

Хотя Зигберт и может всегда побеждать, взяв первым ходом все камни, он решил сделать игру интереснее и брать первым ходом наименьшее количество камней, которое гарантирует ему победу (предполагая, что остальную игру Зигберт и Джо будут играть оптимально).

Пусть $H(N)$ будет таким наименьшим количеством камней в первый ход для кучи из $N$ камней.
$H(1)=1$, $H(4)=1$, $H(17)=1$, $H(8)=8$ и $H(18)=5$ .

Пусть $G(n)$ будет $\displaystyle{\sum_{k=1}^n H(k)}$.
$G(13)=43$.

Найдите $G(23416728348467685)$.

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