Find the largest n so that the number of integers less than or equal to n and divisible by 3 equals the number divisible by 5 or 7 (or both).
Solution
Answer: 65.
Let f(n) = [n/3] - [n/5] - [n/7] + [n/35]. We are looking for the largest n with f(n) = 0. Now [n/5] + [n/7} <= [n/5 + n/7] = [12n/35] = [n/3 + n/105]. So for [n/5] + [n/7] to exceed [n/3] we certainly require n/105 ≥ 1/3 or n ≥ 35. Hence f(n) ≥ 0 for n ≤ 35. But f(n+35) = [n/3 + 11 + 2/3] - [n/5 + 7] - [n/7 + 5] + [n/35 + 1] = [n/3 + 2/3] - [n/5] - [n/7] + [n/35] ≥ f(n) (*). Hence f(n) ≥ 0 for all n. But f(n+105) = [n/3 + 35] - [n/5 + 21] - [n/7 + 15] + [n/35 + 3] = f(n) + 2. Hence f(n) ≥ 2 for all n ≥ 105.
Referring back to (*) we see that f(n+35) > f(n), and hence f(n+35) > 0, unless n is a multiple of 3. But if n is a multiple of 3, then n + 35 is not and hence f(n+70) > f(n+35) > 0. So f(n) > 0 for all n ≥ 70.
f(70) = 1. So f(69) = 2 (we have lost 70, a multiple of 7). So f(68) = f(67) = f(66) = 1 (we have lost 69, a multiple of 3). Hence f(65) = 0 (we have lost 66, a multiple of 3).
© John Scholes
jscholes@kalva.demon.co.uk
11 Apr 2002