Problem 535
Fractal Sequence
Consider the infinite integer sequence S starting with:
S = 1, 1, 2, 1, 3, 2, 4, 1, 5, 3, 6, 2, 7, 8, 4, 9, 1, 10, 11, 5, …
Circle the first occurrence of each integer.
S = ①, 1, ②, 1, ③, 2, ④, 1, ⑤, 3, ⑥, 2, ⑦, ⑧, 4, ⑨, 1, ⑩, ⑪, 5, …
The sequence is characterized by the following properties:
- The circled numbers are consecutive integers starting with 1.
- Immediately preceding each non-circled numbers ai, there are exactly ⌊√ai⌋ adjacent circled numbers, where ⌊⌋ is the floor function.
- If we remove all circled numbers, the remaining numbers form a sequence identical to S, so S is a fractal sequence.
Let T(n) be the sum of the first n elements of the sequence.
You are given T(1) = 1, T(20) = 86, T(103) = 364089 and T(109) = 498676527978348241.
Find T(1018). Give the last 9 digits of your answer.
分形序列
考虑以下无穷整数序列S，其开头部分是：
S = 1, 1, 2, 1, 3, 2, 4, 1, 5, 3, 6, 2, 7, 8, 4, 9, 1, 10, 11, 5, …
圈出序列中每个第一次出现的整数。
S = ①, 1, ②, 1, ③, 2, ④, 1, ⑤, 3, ⑥, 2, ⑦, ⑧, 4, ⑨, 1, ⑩, ⑪, 5, …
这个序列有以下一些特性：
- 被圈出的数构成从1开始的连续整数。
- 在每个没有被圈出的数ai之前，都恰好有⌊√ai⌋个连续的被圈出的数，其中⌊⌋表示下取整函数。
- 如果我们去掉所有被圈出的数，剩下的数构成的序列与S完全相同，因此S是一个分形序列。
记T(n)是该序列前n项元素的和。
已知T(1) = 1，T(20) = 86，T(103) = 364089以及T(109) = 498676527978348241。
求T(1018)，给出其后9位作为你的答案。