Problem:
For each positive integer p, let b(p) denote the unique positive integer k such that ∣k−p∣<21. For example, b(6)=2 and b(23)=5. If S=∑p=12007b(p), find the remainder when S is divided by 1000.
Solution:
First, if k is a nonnegative integer, and n is a positive integer then n2+k<n+21⟺n2+k<n2+n+41⟺k<n+41⟺k=0,1,2,…,n. Similarly, n−21<n2−k⟺n2−n+41<n2−k⟺k<n−41. So if k is a positive integer, the second inequality is satisfied when k=1,2,3,…,n−1. Thus a positive integer n is the value of b(p) precisely when p is one of the (n+1)+(n−1)=2n integers n2−(n−1),n2−(n−2),…,n2−1,n2,n2+1, ..., n2+n.
Next, observe that 442=1936<1936+44=1980<2007<452=2025. Therefore each integer n=1,2,3,…,44 contributes n⋅2n=2n2 to the sum. Consequently,