Since $a_{n+1}$ is uniquely determined by $a_n$, it suffices to show for every $a$ that $(a_n)$ is not strictly increasing. Suppose the contrary. So, there is some $a=a_1$ such that $d(a_{n+1})>d(a_n)$ for all $n$. Consider this sequence. Note that $d(m)\le\sqrt m$ iff $m$ is not prime. If there is $n$ such that $a_n=p$ is prime, then $a_{n+1}=2p-1$ is prime as well (suppose not, then $d(a_{n+1})\le\sqrt{2p-1}<p=d(a_n)$, a contradiction). Therefore, by induction, $a_{n+k}=2^k(p-1)+1$ is a prime number for all $k\ge0$. But $p\mid 2^{p-1}(p-1)+1=a_{n+p-1}>a_n=p$, so $a_{n+p-1}$ is not prime. Contradiction. Thus, $a_n$ is never a prime and so $d(a_n)\le\sqrt{a_n}$ for all $n\ge1$. Therefore, $\sqrt{a_{n+1}}\le\sqrt{a_n+\sqrt{a_n}-1}<\sqrt{a_n}+0.5$, so $\sqrt{a_n}<\sqrt{a_1}+0.5(n-1)<0.6n$ for all large enough $n$ and $a_{n+1}-a_n=(\sqrt{a_{n+1}}-\sqrt{a_n})(\sqrt{a_{n+1}}+\sqrt{a_n})<0.5\cdot(0.6(n+1)+0.6n)<0.7n$. Since $(d(a_n))$ is a strictly increasing sequence of integers, $d(a_n)-1>0.9n$ for all large enough $n$. But then $0.9n<d(a_n)-1=a_{n+1}-a_n<0.7n$ for all large enough $n$, so contradiction.

very nice problem and solution