Maths Olympiad Prep

Library / /164 of 520

Number theory Difficulty 6.6 National olympiad Find the answer

Define a function ff as follows. For any positive integer ii, let f(i)f(i) be the smallest positive integer jj such that there exist pairwise distinct positive integers a,b,c,a,b,c, and dd such that gcd(a,b)\gcd(a,b), gcd(a,c)\gcd(a,c), gcd(a,d)\gcd(a,d), gcd(b,c)\gcd(b,c), gcd(b,d)\gcd(b,d), and gcd(c,d)\gcd(c,d) are pairwise distinct and equal to i,i+1,i+2,i+3,i+4,i, i+1, i+2, i+3, i+4, and jj in some order, if any such jj exists; let f(i)=0f(i)=0 if no such jj exists. Compute f(1)+f(2)++f(2019)f(1)+f(2)+\dots +f(2019).

Proposed by Edward Wan

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

Solution

1. Understanding the Problem:
We need to define a function f(i) f(i) for any positive integer i i . The function f(i) f(i) is the smallest positive integer j j such that there exist pairwise distinct positive integers a,b,c, a, b, c, and d d with the greatest common divisors (gcd) of each pair being pairwise distinct and equal to i,i+1,i+2,i+3,i+4, i, i+1, i+2, i+3, i+4, and j j in some order. If no such j j exists, then f(i)=0 f(i) = 0 .

2. Key Observation:
For any integers a,b,c, a, b, c, and d d , the gcds of the pairs must satisfy the condition that they are pairwise distinct and equal to i,i+1,i+2,i+3,i+4, i, i+1, i+2, i+3, i+4, and j j . This implies that the gcds must be distinct and cover a range of six consecutive integers.

3. Using Modulo 12:
We observe that the gcds must be distinct and cover a range of six consecutive integers. This suggests that the function f(i) f(i) might have a periodic behavior modulo 12. We will compute f(i) f(i) for i i from 1 to 12 and then use this periodicity to find the sum f(1)+f(2)++f(2019) f(1) + f(2) + \dots + f(2019) .

4. **Computing f(i) f(i) for i i from 1 to 12:**
- f(1)=14 f(1) = 14
- f(2)=9 f(2) = 9
- f(3)=0 f(3) = 0
- f(4)=0 f(4) = 0
- f(5)=0 f(5) = 0
- f(6)=3 f(6) = 3
- f(7)=2 f(7) = 2
- f(8)=0 f(8) = 0
- f(9)=0 f(9) = 0
- f(10)=1 f(10) = 1
- f(11)=0 f(11) = 0
- f(12)=0 f(12) = 0

5. Periodic Behavior:
From the above computations, we observe that f(i+12)=f(i) f(i+12) = f(i) for i>2 i > 2 . This periodicity allows us to extend the values of f(i) f(i) for i i up to 2019.

6. **Summing f(i) f(i) from 1 to 2019:**
- The sequence f(i) f(i) repeats every 12 numbers.
- We need to sum f(i) f(i) for 2019 terms.
- There are 201912=168 \left\lfloor \frac{2019}{12} \right\rfloor = 168 complete cycles of 12 terms.
- The sum of one cycle (from f(1) f(1) to f(12) f(12) ) is 14+9+0+0+0+3+2+0+0+1+0+0=29 14 + 9 + 0 + 0 + 0 + 3 + 2 + 0 + 0 + 1 + 0 + 0 = 29 .
- The total sum for 168 cycles is 168×29=4872 168 \times 29 = 4872 .

7. Handling the Remaining Terms:
- There are 2019mod12=3 2019 \mod 12 = 3 remaining terms.
- These terms are f(1)+f(2)+f(3)=14+9+0=23 f(1) + f(2) + f(3) = 14 + 9 + 0 = 23 .

8. Final Sum:
- The total sum is 4872+23=4895 4872 + 23 = 4895 .

The final answer is 4895\boxed{4895}

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.