2016 AMC 12A Problem 25

Let k be a positive integer. Bernardo and Silvia take turns writing and erasing numbers on a blackboard as follows: Bernardo starts by writing the smallest perfect square with k+1 digits. Every time Bernardo writes a number, Silvia erases the last k digits of it. Bernardo then writes the next perfect square, Silvia erases the last k digits of it, and this process continues until the last two numbers that remain on the board differ by at least 2. Let f(k) be the smallest positive integer not written on the board. For example, if k = 1, then the numbers that Bernardo writes are 16, 25, 36, 49, 64, and the numbers showing on the board after Silvia erases are 1, 2, 3, 4, and 6, and thus f(1) = 5. What is the sum of the digits of f(2) + f(4)+ f(6) + ... + f(2016)?

\textbf{(A)}\ 7986\qquad\textbf{(B)}\ 8002\qquad\textbf{(C)}\ 8030\qquad\textbf{(D)}\ 8048\qquad\textbf{(E)}\ 8064

Full credit goes to MAA for authoring these problems. These problems were taken on the AOPS website.