## HC10000 - Hofstadter–Conway 10000 dollar sequence

no tags

Hofstadter–Conway $10,000 sequence is a famous sequence, which is defined as $$a_1 = a_2 = 1,\, a_{n} = a_{a_{n-1}} + a_{n-a_{n-1}}\, (n \ge 3).$$ Your task is to find a summatory function$S(n) := \sum\limits_{i=1}^n a_i$and compute$S(n)$modulo$10^9$. ### Input The first line contains$T$($1 \le T \le 10000$), the number of test cases. Each of the next$T$lines contains a positive integer$n$($1 \le n \le 10^{18}$). ### Output For each test case, print$S(n)$modulo$10^9$. ### Example Input: 10 1 2 3 4 5 10 100 1000 1000000 1000000000 Output: 1 2 4 6 9 32 2818 269446 334706485 137951847  ### Explanation You can verify that$a_1 = a_2 = 1$,$a_3 = a_4 = 2$and$a_5 = 3$. So,$S(5) = 9$.$S(10^9) = 259987670137951847 \equiv 137951847 \pmod{10^9}$. ### Information There are 5 input files: - #1:$n \le 10^{4}$, TL = 2s. - #2:$n \le 10^{6}$, TL = 2s. - #3:$n \le 10^{8}$, TL = 3s. - #4:$n \le 10^{12}$, TL = 5s. - #5:$n \le 10^{18}\$, TL = 12s.

These time limits allow a (slow) Python2 solution to get accepted.