Find k

Suppose that $1 \le k \le 9999$ is an at most $4$ -digit number, so that $k = \overline{abcd}$ for some $0 \le a,b,c,d \le 9$ . Then $s(k) = a+b+c+d$ and $1001k \; = \; \overline{abcd000} + \overline{abcd} \;= \; \overline{a000bcd} + \overline{bcd000} + \overline{a000}$ There are various cases to consider:

• If $\overline{bcd} + a < \overline{uvw} < 1000$ , then $1001k = \overline{auvwbcd}$ , so that $s(1001k) = s(k) + u+v+w > s(k)$ . Note that since $\overline{uvw} > 0$ , $u+v+w > 0$ .
• If $\overline{bcd} + a = \overline{100u} \ge 1000$ and $a \le 8$ , then $1001k = \overline{(a+1)00ubcd}$ , and so $s(1001k) = s(k) + 1 + u > s(k)$ .
• If $\overline{bcd} + a = \overline{100u} \ge 1000$ and $a=9$ , then $1001k = \overline{1000ubcd}$ and so $s(1001k) = s(k) + u - 8$ . Since $\overline{1000u} \le 999 + 9 = 1008$ , we deduce that $u \le 8$ , and hence that $s(1001k) < s(k)$ unless $u=8$ , which can only happen when $a=b=c=d=9$ .

Thus we have shown that $s(1001k) \neq s(k)$ for all $1 \le k \le 9998$ .

If $1 \le j \le 9999$ we can write $j = \overline{pqrs}$ for some integers $0 \le p,q,r,s \le 9$ . But then $9999j \; = \; 10000j - j \; = \; \overline{pqrs0000} - \overline{pqrs} \; = \; \left\{ \begin{array}{lll} \overline{pqr(s-1)(9-p)(9-q)(9-r)(10-s)} & \hspace{1cm} & s > 0 \\ \overline{pq(r-1)9(9-p)(9-q)(10-r)0} & & r > 0, s = 0 \\ \overline{p(q-1)99(9-p)(10-q)00} & & q > 0, r = s = 0 \\ \overline{(p-1)999(10-p)000} & & p > 0, q = r = s = 0 \end{array} \right.$ which shows that $s(9999j) = 36 = s(9999)$ for all $1 \le j \le 9999$ , and so certainly for $1 \le j \le 2014$ . The answer is $\boxed{9999}$ .

Since a fully mathematical proof has already been presented by @Mark Hennings ,I present a computer program In C which solves the problem.