La pregunta adicional acerca de cómo agregar la condición de que la sucesión está acotada llamó mi atención. (Es en el de Daniel comentario bajo la dirección de Brian de respuesta.)
Primero yo era capaz de obtener sólo un ejemplo para $k=2$:
$a_{2^x+y}=\frac y{2^x}$ $0\le y<2^x$.
Cuando se intenta encontrar un ejemplo de trabajo para todos los $k$'s me quedé atrapado por algún tiempo, así que traté de modificar Brian ejemplo:
$a_n=\sin\left(\frac\pi2 \lg\lg n\right)$.
Para demostrar que cumple con los requisitos, podemos usar $|\sin x-\sin y|\le |x-y|$ y el mismo razonamiento que Brian hizo. (En detalle: $|a_{kn}-a_n| = |\sin(\frac\pi2\lg\lg kn)-\sin(\frac\pi2\lg\lg n)| \le \frac\pi2(\lg\lg kn - \lg\lg n)$, una de los RHS converge a 0, como se muestra en Brian respuesta. Por lo tanto $|a_{kn}-a_n|\to 0$.)
Pero esta secuencia tiene una larga convergente a cero (0 $n=2^{2^{2k}}$) y una larga convergente a 1 (por $n=2^{2^{4k+1}}$). Por eso no es convergente y, por consiguiente, no es de Cauchy.
Espero que no me pierda algún error ahí.