Number theoryDifficulty 7.6National olympiad, round 2Find the answer
For every positive integer n, let s(n) be the sum of the exponents of 71 and 97 in the prime factorization of n; for example, s(2021)=s(43⋅47)=0 and s(488977)=s(712⋅97)=3. If we define f(n)=(−1)s(n), prove that the limit n→+∞limnf(1)+f(2)+⋯+f(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, let s(n) be the sum of the exponents of 71 and 97 in the prime factorization of n. For example, s(2021)=s(43⋅47)=0 and s(488977)=s(712⋅97)=3. Define f(n)=(−1)s(n).
2. **Sum function S(n):** Let S(n) denote the sum ∑x=1nf(x).
3. Subsets and their properties: Consider the set [n]={1,2,…,n}. Define subsets: - A={x∈[n]:71∣x} - B={x∈[n]:97∣x} - A∩B={x∈[n]:71⋅97∣x}
We have: - [n]∖(A∪B)={x∈[n]:gcd(x,71⋅97)=1}, which implies f(x)=1 for all x∈[n]∖(A∪B).
4. **Expression for S(n):** S(n)=x∈[n]∑f(x)=x∈A∑f(x)+x∈B∑f(x)−x∈A∩B∑f(x)+x∈[n]∖(A∪B)∑f(x) Since f(x)=−1 for x∈A∪B and f(x)=1 for x∈[n]∖(A∪B), we get: S(n)=x∈[⌊71n⌋]∑(−f(x))+x∈[⌊97n⌋]∑(−f(x))−x∈[⌊71⋅97n⌋]∑f(x)+(n−⌊71n⌋−⌊97n⌋+⌊71⋅97n⌋) Simplifying, we get: S(n)=n−⌊71n⌋−⌊97n⌋+⌊71⋅97n⌋−S(⌊71n⌋)−S(⌊97n⌋)−S(⌊71⋅97n⌋)
5. **Define λ and D(n):** Let λ=(71+1)(97+1)(71−1)(97−1) and D(n)=S(n)−λn.
6. Transform the identity: The above identity translates to: D(n)+D(⌊71n⌋)+D(⌊97n⌋)+D(⌊71⋅97n⌋)=(1+λ)({71n}+{97n})−(1−λ){71⋅97n} where {x}=x−⌊x⌋ denotes the fractional part of x.
7. **Bound ∣D(n)∣:** It follows that: ∣D(n)∣≤∣D(⌊71n⌋)∣+∣D(⌊97n⌋)∣+∣D(⌊71⋅97n⌋)∣+4
8. **Choose r and bound D(n):** Choose any positive real number r<1 such that ϵ=1−(71r1+97r1+(71⋅97)r1) is positive (e.g., r=21). Let M denote the number max(ϵ4,max{n−r∣D(n)∣:1≤n<71⋅97}).
9. **Induction on n:** Prove by induction on n that n−r∣D(n)∣≤M for any n≥1. The claim is true for 1≤n<71⋅97. Suppose it is true for all positive integers less than n. Then for n, we have: ∣D(n)∣≤⌊71n⌋rM+⌊97n⌋rM+⌊71⋅97n⌋rM+ϵM≤nrM Thus, the claim is true for all n≥1.
10. Conclusion: We have shown that ∣S(n)−λn∣≤nrM for some constants M>0 and r<1. It follows that: n→∞limnS(n)=λ=(71+1)(97+1)(71−1)(97−1)=2120
The final answer is 2120
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.