Для любого натурального n, n-тая слабая последовательность Гудштайна {g₁, g₂, g₃, ...} определяется следующим образом:

• g₁ = n
• для k > 1, g_k находится, записывая g_k-1 по основанию k, интерпретируя его как число по основанию k + 1 и вычитая 1.

Последовательность завершается, когда g_k принимает значение 0.

Например, шестая слабая последовательность Гудштайна - {6, 11, 17, 25, ...}:

• g₁ = 6;
• g₂ = 11, так как 6 = 110₂, 110₃ = 12, и 12 - 1 = 11;
• g₃ = 17, так как 11 = 102₃, 102₄ = 18, и 18 - 1 = 17;
• g₄ = 25, так как 17 = 101₄, 101₅ = 26, и 26 - 1 = 25;

и так далее.

Можно показать, что каждая слабая последовательность Гудштайна конечна.

Пусть G(n) будет количеством ненулевых элеметов n-той слабой последовательности Гудштайна.
Может быть доказано, что G(2) = 3, G(4) = 21 и G(6) = 381.
Может также быть доказано, что ΣG(n) = 2517 для 1 ≤ n < 8.

Найдите последние 9 цифр ΣG(n) для 1 ≤ n < 16.