Problem:
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, and 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)?
Answer Choices:
A. 7986
B. 8002
C. 8030
D. 8048
E. 8064 Solution:
Assume that k=2j≥2 is even. The smallest perfect square with k+1 digits is 10k=(10j)2. Thus the sequence of numbers written on the board after Silvia erases the last k digits of each number is the sequence
1=⌊10k(10j)2⌋,⌊10k(10j+1)2⌋,…,⌊10kn2⌋,…
The sequence ends the first time that
⌊10k(n+1)2⌋−⌊10kn2⌋≥2
before that, every two consecutive terms are either equal or they differ by 1 . Suppose that
⌊10kn2⌋=a and ⌊10k(n+1)2⌋≥a+2
Then n2<(a+1)10k and (a+2)10k≤(n+1)2. Thus
10k=(a+2)10k−(a+1)10k<(n+1)2−n2=2n+1
It follows that n=210k+m for some positive integer m. Note that