Problem 396

Weak Goodstein sequence

For any positive integer n, the **nth weak Goodstein sequence** {g_{1}, g_{2}, g_{3}, ...} is defined as:

- g
_{1}=`n` - for
`k`1, g_{k}is obtained by writing g_{k-1}in base`k`, interpreting it as a base`k`+ 1 number, and subtracting 1.

For example, the 6th weak Goodstein sequence is {6, 11, 17, 25, ...}:

- g
_{1}= 6. - g
_{2}= 11 since 6 = 110_{2}, 110_{3}= 12, and 12 - 1 = 11. - g
_{3}= 17 since 11 = 102_{3}, 102_{4}= 18, and 18 - 1 = 17. - g
_{4}= 25 since 17 = 101_{4}, 101_{5}= 26, and 26 - 1 = 25.

It can be shown that every weak Goodstein sequence terminates.

Let G(`n`) be the number of nonzero elements in the `n`th weak Goodstein sequence.

It can be verified that G(2) = 3, G(4) = 21 and G(6) = 381.

It can also be verified that ΣG(`n`) = 2517 for 1 `n` 8.

Find the last 9 digits of ΣG(`n`) for 1 `n` 16.

**
These problems are part of
Project Euler
and are licensed under
CC BY-NC-SA 2.0 UK
**