Let $n$ be a positive integer, and let $a_1,a_2,..,a_n$ be pairwise distinct positive integers. Show that $$\sum_{k=1}^{n}{\frac{1}{[a_1,a_2,…,a_k]}} <4,$$where $[a_1,a_2,…,a_k]$ is the least common multiple of the integers $a_1,a_2,…,a_k$.
Problem
Source: Romania TST 2016 Day 1 P3
Tags: number theory, number divisors
01.11.2017 22:53
02.11.2017 03:53
If we use the better bound $\tau(n) \le \sqrt{3n}$, then we can prove a bound of $< 3$. I have proved a bound of $< \sqrt{3} + \frac{\sqrt{6}}{2}$, can anyone do better?
19.07.2018 03:56
GGPiku said Since any number $n$ has maximum $2\sqrt{n}$, and $a_1,a_2,...,a_k$ are distinct positive divisors of the number $[a_1,a_2,…,a_k]$, it follows that $[a_1,a_2,…,a_k]\geq \frac{k^2}{4}$. So: $\sum_{k=1}^{n}{\frac{1}{[a_1,a_2,…,a_k]}}=\frac{1}{a_1}+\sum_{k=2}^{n}{\frac{1}{[a_1,a_2,…,a_k]}}\leq 1+\sum_{k=2}^{n}{\frac{4}{k^2}}<1+\sum_{k=2}^{n}{\frac{4}{k^2-\frac{1}{4}}}$, which can be telescoped into $1+\frac{8}{3}-\frac{8}{2n+1}<\frac{11}{3}<4$. How did you get that the lcm of $a_i$ for i=1 to k is $\geq \frac{k^2}{4}$ ?
19.07.2018 06:54
Plops wrote: GGPiku said Since any number $n$ has maximum $2\sqrt{n}$, and $a_1,a_2,...,a_k$ are distinct positive divisors of the number $[a_1,a_2,…,a_k]$, it follows that $[a_1,a_2,…,a_k]\geq \frac{k^2}{4}$. So: $\sum_{k=1}^{n}{\frac{1}{[a_1,a_2,…,a_k]}}=\frac{1}{a_1}+\sum_{k=2}^{n}{\frac{1}{[a_1,a_2,…,a_k]}}\leq 1+\sum_{k=2}^{n}{\frac{4}{k^2}}<1+\sum_{k=2}^{n}{\frac{4}{k^2-\frac{1}{4}}}$, which can be telescoped into $1+\frac{8}{3}-\frac{8}{2n+1}<\frac{11}{3}<4$. How did you get that the lcm of $a_i$ for i=1 to k is $\geq \frac{k^2}{4}$ ? Set M = $[a_1,a_2,…,a_k]$. M has at least k positive divisors. So $ k \le \tau(M) \le 2\sqrt{M}$. Hence you get $M \ge \frac{k^2}{4}$.
19.07.2018 08:39
bobthesmartypants wrote: If we use the better bound $\tau(n) \le \sqrt{3n}$, then we can prove a bound of $< 3$. I have proved a bound of $< \sqrt{3} + \frac{\sqrt{6}}{2}$, can anyone do better? $\sum_{k=1}^{n}{\frac{1}{[a_1,a_2,…,a_k]}} <2.34$
19.07.2018 10:55
Nice problem.Thanks
08.08.2019 18:48
Is it possible to improve the bound to $2$?
08.08.2019 19:45
UK2019Project wrote: Is it possible to improve the bound to $2$? Note that any $x<2$ cannot be a lower bound, since taking $a_k = 2^{k-1}$ gives a sum of $2 - 2^{1-n} \to 2.$ Oddly enough, when we speak of lower or upper bounds, we are really speaking about bounds on the maximum value of the sum so that the actual question becomes a $\max \max$ or $\min \max$ problem.
25.12.2021 00:48
$$\tau(n) \le 2 \sqrt{n} $$$$ A=[a_1,a_2,…,a_k] $$A has at least k divisors. $$ k\le\tau(A) \le 2 \sqrt{A} $$$$\frac{1}{[a_1,a_2,…,a_k]}=\frac{1}{A}\le \frac{4}{k^2}$$$$\sum_{k=1}^{n}{\frac{1}{[a_1,a_2,…,a_k]}} \le \frac{1}{a_1}+ \sum_{k=2}^{n}{\frac{4}{k^2}}<4 $$