, 2015

An integer is divisible by $30$ iff it is divisible by $2$, $3$ and $5$.

Note that $2 \mid k^k + 1$ iff $k$ is odd. Thus we may assume that $k$ is odd. Write $k = 2t + 1$.

If $k \equiv 0$ or $1 \pmod{3}$, then $3 \nmid k^k + 1$. If $k \equiv 2 \equiv -1 \pmod{3}$, then $3 \mid k^k + 1$ iff $k$ is odd, i.e. iff $k = 6t + 5$.

If $k \equiv 0$ or $1 \pmod{5}$, $5 \nmid k^k + 1$.
If $k \equiv 2$ or $3 \pmod{5}$, then $k \equiv \pm 2 \pmod{5}$. Therefore
$$k^k + 1 \equiv (\pm 2)^k + 1 \equiv (\pm 2)^{2t+1} + 1 \equiv (\pm 2)4^t + 1 \\ \equiv (\pm 2)(-1)^t + 1 \not\equiv 0 \pmod{5}.$$
If $k \equiv 4 \equiv -1 \pmod{5}$, then $5 \mid k^k + 1$ iff $k$ is odd.

Thus $30 \mid k^k + 1$ iff $k$ is odd and $k \equiv 5 \pmod{6}$ and $k \equiv 9 \pmod{10}$.

Thus $k = 30n + 29$, $n = 0, 1, 2, \ldots$