4. Let $c$ be a natural number. The sequence $a_{1}, a_{2}, \ldots$ is defined by $a_{1}=c$ and $a_{n+1}=a_{n}^{2}+a_{n}+c^{3}$ for every natural number $n$. Determine all values of $c$ for which there exist integers $k \geqslant 1$ and $m \geqslant 2$ such that the number $a_{k}^{2}+c^{3}$ is equal to the $m$-th power of some natural number.

(Bulgaria)
4. For $k>1$ from the recurrence relation we get

$$
a_{k}^{2}+c^{3}=a_{k+1}-a_{k}=a_{k}^{2}+a_{k}-a_{k-1}^{2}-a_{k-1}^{2}=\left(a_{k}-a_{k-1}\right)\left(a_{k}+a_{k-1}+1\right)
$$

Assume that $d \mid a_{k}-a_{k-1}$ and $d \mid a_{k}+a_{k-1}+1$. Then $d \mid 2 a_{k}+1$ and $d \mid 2 a_{k-1}+1$. From the recurrence relation, $2\left(2 a_{n}+1\right)=\left(2 a_{n-1}+1\right)^{2}+4 c^{3}+1$, it follows that $d \mid 4 c^{3}+1$, and further that $d \mid 2 a_{n}+1$ for all $n<k$. Therefore, $d \mid 2 a_{1}+1=2 c+1$. However, then $d \mid 2\left(4 c^{3}+1\right)-(2 c+1)\left(4 c^{2}-2 c+1\right)=1$, i.e., $d=1$.

Now, if $a_{k+1}-a_{k}$ is an $m$-th power, from $(*)$ it follows that $a_{k}-a_{k-1}$ is also a perfect power. Continuing this process, we conclude that $a_{2}-a_{1}=c^{2}(c+1)$ is an $m$-th power, and from $\left(c^{2}, c+1\right)=1$ it follows that both $c^{2}$ and $c+1$ are. However, $c$ cannot be an $m$-th power, so $m$ must be even (moreover, $m=2$), i.e., $c+1$ is a perfect square.

On the other hand, if $c+1$ is a square, then $a_{1}^{2}+c^{3}=c^{2}(c+1)$ is also a square.