0%

# Problem 396

Weak Goodstein sequence

For any positive integer n, the nth weak Goodstein sequence {g1, g2, g3, …} is defined as:

• g1 = n
• for k > 1, gk is obtained by writing gk-1 in base k, interpreting it as a base k + 1 number, and subtracting 1.

The sequence terminates when gk becomes 0.

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

• g1 = 6.
• g2 = 11 since 6 = 1102, 1103 = 12, and 12 - 1 = 11.
• g3 = 17 since 11 = 1023, 1024 = 18, and 18 - 1 = 17.
• g4 = 25 since 17 = 1014, 1015 = 26, and 26 - 1 = 25.
and so on.

It can be shown that every weak Goodstein sequence terminates.

Let G(n) be the number of nonzero elements in the nth 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.

• g1 = n
• 对于k > 1，将gk-1写成k进制表示，然后将其视为k+1进制的数，最后减去1，得到gk

• g1 = 6。
• g2 = 11，因为6 = 1102，然后1103 = 12，最后12 - 1 = 11。
• g3 = 17，因为11 = 1023，然后1024 = 18，最后18 - 1 = 17。
• g4 = 25，因为17 = 1014，然后1015 = 26，最后26 - 1 = 25。
依此类推。