0%

Problem 535


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位作为你的答案。