As usual in this type of problem, the value $2004$ plays no special role; it is beneficial to replace it with $k$, and prove the statement by induction on $k$. Also, we will consider a slightly stronger statement, in order for induction to work. For any positive integer $k$ there exists a $N_k$ such that any integer $n\geq N_k$ can be represented as $\displaystyle n = \sum_{i=1}^k a_i$, with $1\leq a_1 < a_2 < \cdots < a_k$, and $a_i \mid a_{i+1}$ for all $1\leq i \leq k-1$, and $1 < a_1 $ when $n$ is not a prime. The base case $k=1$ is trivial. Let us now assume the statement true for all values from $1$ to some $k\geq 1$, and consider the case $k+1$. If $n > 3$ is a prime, write $n = 1 + (n-1)$; if $n-1 \geq N_k$, then it being even, thus not a prime, can be represented as $\displaystyle n-1 = \sum_{i=1}^k b_i$, with $1<b_1$, and then we can write $\displaystyle n = \sum_{i=1}^{k+1} a_i$ by taking $a_1=1$ and $a_i = b_{i-1}$ for $2\leq i \leq k+1$. If $n=2^{\ell} \geq 2^5$, write $n = 2^j + 2^j(2^{\ell-j} - 1)$ with $j=1$ for odd $\ell$, respectively $j=2$ for even $\ell$; now $2^{\ell-j} - 1$ is not a prime, and if $2^{\ell-j} - 1 \geq N_k$, it can be represented as $\displaystyle 2^{\ell-j} - 1 = \sum_{i=1}^k b_i$, with $1<b_1$, and then we can write $\displaystyle n = \sum_{i=1}^{k+1} a_i$ by taking $a_1=2^j > 1$ and $a_i = 2^j b_{i-1}$ for $2\leq i \leq k+1$. If $n=p^{\ell} \geq p^3$, with $3\leq p \leq N_k$ an odd prime, write $n = p + p(p^{\ell-1} - 1)$; now $p^{\ell-1} - 1$ is not a prime, and if $p^{\ell-1} - 1 \geq N_k$, it can be represented as $\displaystyle p^{\ell-1} - 1 = \sum_{i=1}^k b_i$, with $1<b_1$, and then we can write $\displaystyle n = \sum_{i=1}^{k+1} a_i$ by taking $a_1= p > 1$ and $a_i = p b_{i-1}$ for $2\leq i \leq k+1$. Finally, if $n$ is a large enough composite number, then it will have a factor $d$, either a prime larger than $N_k$, or a power of a prime not larger than $N_k$, but with exponent large enough to fall into one of the cases described in the above. Then $n=dm$, and we can represent $d = \sum_{i=1}^{k+1} a_i$, whence $n = \sum_{i=1}^{k+1} (ma_i)$, with $1 < ma_1$. Thus there exists a $N_{k+1}$ with the required property.