Recurrence relation problem: Given $a_n = \left \lfloor \sqrt{a_1 + a_2 + \cdots + a_{n-1}} \right \rfloor$, find $a_{1000}$. I've been struggling with this problem for some time.

Let there be a recurrent sequence ${a_n}$ such that $a_1 = 1$ and $a_n = \left \lfloor\sqrt{a_1 + a_2 + \cdots + a_{n-1}}\right \rfloor$ for all $n > 1$. Find $a_{1000}$. 

I've tried to plug in different $n$ and have noticed that the square root makes it grow slowly, and with bigger $n$ the terms become more distinct (different integers), but that still hasn't gotten me close to solving for $a_{1000}$.
Update: I've solved it. I will post my solution in a bit. The hints you guys have given me have proved valuable, and I appreciate the caution with which you guys go about giving me a full solution based on my lack of steps taken.
 A: Hint: $1$ appears four times in the series, powers of two appears three times, and all other numbers appear exactly twice.
A: 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}$. 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}$
since $2^{k+1} = 2 \times 2^k < 2n < 2n +1 = (n+1)^2 - n^2$. We 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, and 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 it's 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$, which follows from $(n +1)^2 \le n^2 + n + 2^{k+1} < (n+2)^2$.
Now we only need to show that if $n = 2^{k+1}$, then after three occurrences of $n$, an $n+1$ will follow.
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}$. Thus, $a_{1000} = \boxed{495}$.
