Prove that the sequence $(a_n/n)$ converges

Clearly $\limsup_{k \to \infty} \frac{a_k}{k} \le \sup_n \frac{a_n}{n}$. Fix $n \ge 1$. For $k \ge 1$, write $k = nq+r$ for $0 \le r \le n-1$. Then $\frac{a_k}{k} = \frac{a_{nq+r}}{nq+r} \ge \frac{a_{nq}}{nq+r} \ge \frac{qa_n}{qn+r}$. So, $\liminf_{k \to \infty} \frac{a_k}{k} \ge \frac{a_n}{n}$. It follows that $\liminf_{k \to \infty} \frac{a_k}{k} \ge \sup_n \frac{a_n}{n}$.

Here is an approach I think will lead to a solution:

As per the counterexample in the comment, trying to prove monotonicity will fail. But part of the counterexample is that in order to create the break in monotonicity, we had to increase the constant greatly, impacting the rest of the sequence. Also we have that $a_n$'s growth is at most linear, otherwise the $a_n/n$ sequence isn't bounded.

So assume we have infinitely many breaks in monotonicity. Each break in monotonicity will impact the later terms by forcing the linear constant up. If there are infinitely many breaks then (I think) one can show that this lower bound for the linear constant is unbounded.