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=12007​b(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,