Maths Olympiad Prep

Library / /155 of 520

Number theory Difficulty 6.6 National olympiad Find the answer

For each positive integer pp, let b(p)b(p) denote the unique positive integer kk such that kp<12|k-\sqrt{p}|<\frac{1}{2}. For example, b(6)=2b(6) = 2 and b(23)=5b(23)=5. If S=p=12007b(p)S = \textstyle\sum_{p=1}^{2007}b(p), find the remainder when S is divided by 1000.

A number or a short expression. Spacing and $ signs are ignored.

Solution

1. **Understanding the function b(p) b(p) **:
- The function b(p) b(p) is defined such that b(p)=k b(p) = k where k k is the unique positive integer satisfying kp<12 |k - \sqrt{p}| < \frac{1}{2} .
- This implies k12<p<k+12 k - \frac{1}{2} < \sqrt{p} < k + \frac{1}{2} .
- Squaring all parts of the inequality, we get:
(k12)2<p<(k+12)2 (k - \frac{1}{2})^2 < p < (k + \frac{1}{2})^2
- Simplifying the squared terms:
k2k+14<p<k2+k+14 k^2 - k + \frac{1}{4} < p < k^2 + k + \frac{1}{4}
- Since p p is an integer, we can ignore the fractional parts:
k2k+1pk2+k k^2 - k + 1 \leq p \leq k^2 + k

2. **Counting the number of p p values for each k k **:
- For each k k , the number of integers p p in the range k2k+1pk2+k k^2 - k + 1 \leq p \leq k^2 + k is:
(k2+k)(k2k+1)+1=2k (k^2 + k) - (k^2 - k + 1) + 1 = 2k
- Therefore, there are 2k 2k values of p p for which b(p)=k b(p) = k .

3. **Summing b(p) b(p) for p p from 1 to 2007**:
- We need to find the sum S=p=12007b(p) S = \sum_{p=1}^{2007} b(p) .
- We observe that b(p)=k b(p) = k for 2k 2k values of p p .
- We need to determine the largest k k such that k2+k2007 k^2 + k \leq 2007 :
k2+k20070 k^2 + k - 2007 \leq 0
- Solving the quadratic equation k2+k2007=0 k^2 + k - 2007 = 0 using the quadratic formula:
k=1±1+420072=1±80292 k = \frac{-1 \pm \sqrt{1 + 4 \cdot 2007}}{2} = \frac{-1 \pm \sqrt{8029}}{2}
- Approximating 802989.6 \sqrt{8029} \approx 89.6 :
k1+89.6244.3 k \approx \frac{-1 + 89.6}{2} \approx 44.3
- Thus, the largest integer k k is 44.

4. **Calculating the sum S S **:
- For k=1 k = 1 to 44 44 , each k k contributes 2kk=2k2 2k \cdot k = 2k^2 to the sum.
- The sum of squares of the first 44 integers is:
k=1442k2=2k=144k2=24445896=229370=58740 \sum_{k=1}^{44} 2k^2 = 2 \sum_{k=1}^{44} k^2 = 2 \cdot \frac{44 \cdot 45 \cdot 89}{6} = 2 \cdot 29370 = 58740
- For p p from 1981 to 2007 (27 values), b(p)=45 b(p) = 45 :
2745=1215 27 \cdot 45 = 1215
- Adding these contributions:
S=58740+1215=59955 S = 58740 + 1215 = 59955

5. **Finding the remainder when S S is divided by 1000**:
- Calculating 59955mod1000 59955 \mod 1000 :
59955955(mod1000) 59955 \equiv 955 \pmod{1000}

The final answer is 955 \boxed{955} .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.