Maths Olympiad Prep

Library / /482 of 520

Number theory Difficulty 7.6 National olympiad, round 2 Find the answer

For every positive integer nn, let s(n)s(n) be the sum of the exponents of 7171 and 9797 in the prime factorization of nn; for example, s(2021)=s(4347)=0s(2021) = s(43 \cdot 47) = 0 and s(488977)=s(71297)=3s(488977) = s(71^2 \cdot 97) = 3. If we define f(n)=(1)s(n)f(n)=(-1)^{s(n)}, prove that the limit
limn+f(1)+f(2)++f(n)n \lim_{n \to +\infty} \frac{f(1) + f(2) + \cdots+ f(n)}{n}
exists and determine its value.

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

Solution

1. Define the function and initial setup:
For every positive integer n n , let s(n) s(n) be the sum of the exponents of 71 71 and 97 97 in the prime factorization of n n . For example, s(2021)=s(4347)=0 s(2021) = s(43 \cdot 47) = 0 and s(488977)=s(71297)=3 s(488977) = s(71^2 \cdot 97) = 3 . Define f(n)=(1)s(n) f(n) = (-1)^{s(n)} .

2. **Sum function S(n) S(n) :**
Let S(n) S(n) denote the sum x=1nf(x) \sum_{x = 1}^n f(x) .

3. Subsets and their properties:
Consider the set [n]={1,2,,n} [n] = \{1, 2, \ldots, n\} . Define subsets:
- A={x[n]:71x} A = \{x \in [n] : 71 \mid x\}
- B={x[n]:97x} B = \{x \in [n] : 97 \mid x\}
- AB={x[n]:7197x} A \cap B = \{x \in [n] : 71 \cdot 97 \mid x\}

We have:
- [n](AB)={x[n]:gcd(x,7197)=1} [n] \setminus (A \cup B) = \{x \in [n] : \gcd(x, 71 \cdot 97) = 1\} , which implies f(x)=1 f(x) = 1 for all x[n](AB) x \in [n] \setminus (A \cup B) .

4. **Expression for S(n) S(n) :**
S(n)=x[n]f(x)=(xAf(x)+xBf(x)xABf(x)+x[n](AB)f(x)) S(n) = \sum_{x \in [n]} f(x) = \left( \sum_{x \in A} f(x) + \sum_{x \in B} f(x) - \sum_{x \in A \cap B} f(x) + \sum_{x \in [n] \setminus (A \cup B)} f(x) \right)
Since f(x)=1 f(x) = -1 for xAB x \in A \cup B and f(x)=1 f(x) = 1 for x[n](AB) x \in [n] \setminus (A \cup B) , we get:
S(n)=x[n71](f(x))+x[n97](f(x))x[n7197]f(x)+(nn71n97+n7197) S(n) = \sum_{x \in [\lfloor \frac{n}{71} \rfloor]} (-f(x)) + \sum_{x \in [\lfloor \frac{n}{97} \rfloor]} (-f(x)) - \sum_{x \in [\lfloor \frac{n}{71 \cdot 97} \rfloor]} f(x) + (n - \lfloor \frac{n}{71} \rfloor - \lfloor \frac{n}{97} \rfloor + \lfloor \frac{n}{71 \cdot 97} \rfloor)
Simplifying, we get:
S(n)=nn71n97+n7197S(n71)S(n97)S(n7197) S(n) = n - \lfloor \frac{n}{71} \rfloor - \lfloor \frac{n}{97} \rfloor + \lfloor \frac{n}{71 \cdot 97} \rfloor - S(\lfloor \frac{n}{71} \rfloor) - S(\lfloor \frac{n}{97} \rfloor) - S(\lfloor \frac{n}{71 \cdot 97} \rfloor)

5. **Define λ \lambda and D(n) D(n) :**
Let λ=(711)(971)(71+1)(97+1) \lambda = \frac{(71 - 1)(97 - 1)}{(71 + 1)(97 + 1)} and D(n)=S(n)λn D(n) = S(n) - \lambda n .

6. Transform the identity:
The above identity translates to:
D(n)+D(n71)+D(n97)+D(n7197)=(1+λ)({n71}+{n97})(1λ){n7197} D(n) + D(\lfloor \frac{n}{71} \rfloor) + D(\lfloor \frac{n}{97} \rfloor) + D(\lfloor \frac{n}{71 \cdot 97} \rfloor) = (1 + \lambda) \left( \left\{ \frac{n}{71} \right\} + \left\{ \frac{n}{97} \right\} \right) - (1 - \lambda) \left\{ \frac{n}{71 \cdot 97} \right\}
where {x}=xx \{x\} = x - \lfloor x \rfloor denotes the fractional part of x x .

7. **Bound D(n) |D(n)| :**
It follows that:
D(n)D(n71)+D(n97)+D(n7197)+4 |D(n)| \leq |D(\lfloor \frac{n}{71} \rfloor)| + |D(\lfloor \frac{n}{97} \rfloor)| + |D(\lfloor \frac{n}{71 \cdot 97} \rfloor)| + 4

8. **Choose r r and bound D(n) D(n) :**
Choose any positive real number r<1 r < 1 such that ϵ=1(171r+197r+1(7197)r) \epsilon = 1 - \left( \frac{1}{71^r} + \frac{1}{97^r} + \frac{1}{(71 \cdot 97)^r} \right) is positive (e.g., r=12 r = \frac{1}{2} ). Let M M denote the number max(4ϵ,max{nrD(n):1n<7197}) \max \left( \frac{4}{\epsilon}, \max \{ n^{-r} |D(n)| : 1 \leq n < 71 \cdot 97 \} \right) .

9. **Induction on n n :**
Prove by induction on n n that nrD(n)M n^{-r} |D(n)| \leq M for any n1 n \geq 1 . The claim is true for 1n<7197 1 \leq n < 71 \cdot 97 . Suppose it is true for all positive integers less than n n . Then for n n , we have:
D(n)n71rM+n97rM+n7197rM+ϵMnrM |D(n)| \leq \lfloor \frac{n}{71} \rfloor^r M + \lfloor \frac{n}{97} \rfloor^r M + \lfloor \frac{n}{71 \cdot 97} \rfloor^r M + \epsilon M \leq n^r M
Thus, the claim is true for all n1 n \geq 1 .

10. Conclusion:
We have shown that S(n)λnnrM |S(n) - \lambda n| \leq n^r M for some constants M>0 M > 0 and r<1 r < 1 . It follows that:
limnS(n)n=λ=(711)(971)(71+1)(97+1)=2021 \lim_{n \to \infty} \frac{S(n)}{n} = \lambda = \frac{(71 - 1)(97 - 1)}{(71 + 1)(97 + 1)} = \frac{20}{21}

The final answer is 2021 \boxed{ \frac{20}{21} }

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.