Floors!

If we write down some of the first numbers, we get: $(1,1,1,1,2,2,2,3,3,4,4,4,5,5,6,6,7,7,8,8,8,9,9,…)$ . From this it is visible that number $1$ appears four times, while all other numbers appear twice, thrice at most. We will further define that numbers that appear thrice are the powers of $2$ , starting with $2^1$ . All other numbers therefore appear twice.

Suppose we wrote down the beginning of the sequence until the first occurrence of the number $n(n>1)$ . And that the sequence visibly behaves as defined.

Let $k$ be the largest integer satisfying $2^{k}<n$ . Then the sum of all the values is:

$s_1 = (1+2+...+n) + (1+2+...+n-1) + (1+2+2^2+...+2^k) +1 = n^2 + 2^{k+1}$ .

Because $2^{k+1} = 2 \times 2^k < 2n < 2n +1 = (n+1)^2 - n^2.$ . Whe have $s_1 < (n+1)^2$ and the following member is therefore $\lfloor\sqrt{s_1}\rfloor = n$ .

Now we define the next member in this order, we see that the sum is now: $s_2 = s_1 + n = n^2 + n + 2^{k+1}$ , so if $2^{k+1} < n+1$ , then $s_2 < (n+1)^2$ and the next member is $n$ .

However $k$ is the largest integer satisfying $2^k < n$ , so its true that $n\le 2^{k+1}$ . The previous situation therefore occurs iff $2^{k+1} = n$ .

When $n$ isn't a power of two, the next member is $n+1$ , because $n+1\le 2^{k+1} < 2n < 3n +4$ , because $(n +1)^2 \le n^2 + n + 2^{k+1} < (n+2)^2.$

Now it is only needed to show, that if $n = 2^{k+1}$ , then after three occurences of $n$ , a $n+1$ will follow.

So now the sum is:

$s_3 = s_2 + n = n^2 + 2n + 2^{k+1} = n^2 + 3n$ , and we immediately get the inequality $(n+1)^2 < s_3 < (n+2)^2$ .

Now we finally see that $500 = a_{1010} = a_{1009}$ , from where we finish $a_{1000} = \boxed{495}$ .

The regularity is obvious.But I persuade myself to treat this problem rigorously.

Let’s show that

$a_{2^k +k-1}= a_{2^k +k}= a_{2^k +k+1}=2^{k-1}$ ,
$a_{2^k +k+1+2j-1}= a_{2^k +k+1+2j}=2^{k-1}+j$ , for all $k\ge 2$ and $1\le j\le 2^{k-1}-1$ .........(#)

Do induction on $k$ . For $k=2$ ,we have $a_{5}=a_{6}=a_{7}=2,a_{8}=a_{9}=3$ .

Assume that we now have (#) for the cases $2,…,k(k\ge 2)$ ,then we get

$\displaystyle\sum_{i=1}^{2^{k+1}+k+1-2}a_{i} =1+2\sum_{i=1}^{2^k -1}i +\sum_{i=0}^{k-1}2^i=1+2^k(2^k -1)+(2^k -1)=2^{2k}$ .

And so $a_{2^{k+1} +k+1-1}=\lfloor \sqrt{\displaystyle\sum_{i=1}^{2^{k+1}+k+1-2}a_{i}} \rfloor=\lfloor \sqrt{2^{2k}} \rfloor =2^{k}$ .

It leads to the result $a_{2^{k+1} +k+1}=\color{#3D99F6}\lfloor \sqrt{2^{2k}+2^k} \rfloor=2^k$ , and $a_{2^{k+1} +k+1+1}=\color{#3D99F6}\lfloor \sqrt{2^{2k}+2^k+2^k} \rfloor=2^k$ ,

since $\lfloor \sqrt{2^{2k}+2^k} \rfloor=2^k \iff 2^k \le \sqrt{2^{2k}+2^k} < 2^k +1 \iff 2^{2k}\le 2^{2k}+2^k < 2^{2k}+2\cdot 2^k+1$ holds true evidently and the latter can be obtained in the same way.

__Using this method,we can obtain several similar equalities (they're colored in blue and you can check them on your own) .

Then do induction on $j$ in the case $k+1$ .

it's easy to check the case when $j=1$ :

$a_{(2^{k+1} +k+1+1)+1}=\color{#3D99F6}\lfloor \sqrt{2^{2k}+2^k+2^k+2^k} \rfloor=2^k +1$ , and $a_{(2^{k+1} +k+1+1)+2}=\color{#3D99F6}\lfloor \sqrt{2^{2k}+2^k+2^k+2^k+(2^k+1)} \rfloor=2^k+1$ .

Assume that we have showed the cases $1,...,j(j\ge1)$ ,then we got

$a_{(2^{k+1} +k+1+1)+2j+1}=\lfloor \sqrt{2^{2k}+2^k+2^k+2^k+\displaystyle\sum_{i=1}^{j}(a_{(2^{k+1} +k+1+1)+2i-1}+ a_{(2^{k+1}+k+1+1)+2i}) }\rfloor$

$=\lfloor \sqrt{2^{2k}+3\cdot 2^{k}+\displaystyle 2\sum_{i=1}^{j}( 2^k +i ) } \rfloor= \color{#3D99F6}\lfloor \sqrt{2^{2k}+ 3\cdot 2^{k} +j\cdot 2^{k+1}+j(j+1) } \rfloor=2^k +j+1$ .

and we can get $a_{(2^{ k+1}+k+1+1)+2j+2 }=2^k +j+1$ in the same way.

So we've finished the proof.In fact, using the proved results we can culculate every term in the sequence separately .

So $a_{1000}=a_{2^9 +9+1+2\cdot 239}=2^8 +239=\boxed{495}$ .