Сумма делителей

[Leeb]

Возникли странные трудности в решении казалось бы простой задачи. Вот ее условие:
Рассматриваются тройки натуральных чисел $1\leqslant a < b < c \leqslant 21000$. Известно, что ни одно из данных чисел не делится на другое. Найти наибольшее значение $s = \gcd(a,b)+\gcd(b,c)+\gcd(c,a)$.

Прежде всего замечу, что если бы условия неделимости одного числа на другое не было, то задача решалась бы сравнительно просто: есть очевидные оценки $\gcd(a,b)\leqslant b-a, \gcd(b,c)\leqslant c-b,\gcd(c,a)\leqslant a,\, s \leqslant c \leqslant 21000$, таким образом, есть оценка сверху через конкретное число, а не переменные, и пример с суммой $21000$ легко привести - $7000,14000,21000$ (если бы максимальное число не делилось на 3, то пришлось бы рассматривать ближайшее меньшее кратное 3 и разбирать оставшиеся варианты на предмет возможной суммы, но пока давайте оставим максимальное число таким).

Но наш случай сложнее. Можно написать схожую числовую оценку и в этом случае, но для нее не будет простого примера, где они достигаются (потому что тривиальная оценка 21000 в принципе достигнута быть не может), а если писать оценки с переменными типа $s \leqslant a + b/2, s \leqslant c-a/2$ и кучу им подобных, то там не будет очевидной максимальность, поэтому нужно что-то другое.
Обозначим $\gcd(a,b)=k,\gcd(b,c)=l,\gcd(c,a) = m$. Пусть $a = pk = qm, b = uk = vl, c = xl = ym$. Тогда $p\geqslant 2, q\geqslant 2, v\geqslant 2, u \geqslant p+1,x\geqslant v+1,y\geqslant q+1$, а также держим в уме, что вторые числа не делятся на соответствующие первые. Попробуем выразить все через $c$, что даст нам оценку уже через числа, пытаясь оставить как можно меньше новых переменных типа $x$:
$k = a/p = b/u=cv/(xu),\, l = b/v = c/x,\, m = c/x\cdot v/u \cdot p/q$, откуда $s = c\left( \dfrac{v}{xu}+\dfrac{1}{x}+\dfrac{vp}{xuq} \right)$, где $c$ будем устремлять к $21000$ или около него, это пока не столь важно. Важнее то, что нужно максимизировать выражение в скобках с условиями $u\geqslant p+1,x\geqslant v+1$ ($q$ при этом более-менее любое). Без этой максимизации я не вижу способа решать дальше. Можно записать $v = \alpha x, 0 < \alpha \leqslant D/(D+1) < 1, p = \beta u, 0 < \beta \leqslant T/(T+1) < 1$ и максимизировать $\dfrac{\alpha}{u}+\dfrac{1}{x}+\dfrac{\alpha\beta}{q}$ еще и имея в виду, что $x$ или получающийся в итоге $y$ где-то не может быть меньше пяти на самом деле, либо т.к. $c > b$.
Хочется сказать, что максимум при $p = q = 2$, что соответствует случаю когда все ноды равны друг другу (тогда пример это $2-3-5$, т.е. $a = 8400, b = 12600, c = 21000$ или $3-4-5$, т.е. $a = 12600, b = 16800, c = 21000$), но это как-то заведомо не очевидно и не факт, что правда.
Здесь я остановился. Что делать дальше не очень понятно, а возможно есть и в принципе другой путь.

[schmetterling]

Можно сразу написать $b = \frac{m}{n} c$; $a = \frac{p}{q} c$, тогда максимизировать нужно $\frac1n + \frac1q + \frac{\gcd(m,p)}{\operatorname{lcm}(n,q)}$.

По "жадному алгоритму" $b = \frac23 c$, $a = \frac25 c$, $\gcd(a,b) + \gcd(b,c) + \gcd(a,c) = \frac23 c$

[Leeb]

Да, действительно, хоть и это по сути та же идея, но гораздо более экономичная и простая, и данное выражение проще максимизировать. Условие неделимости эквивалентно тому, что $q/p, n/m,\dfrac{mq}{np}$ все являются нецелыми, откуда $n,q$ не должны быть меньше $3,5$. Увеличение $n,q$ ведет к слишком быстрому уменьшению первого слагаемого, т.к. $\gcd(p,m)$ будет расти сильно медленнее $\lcm(n,q)$, откуда остаются лишь варианты $p=m=2, n=3, q= 5$ (с учетом того, что $a<b$). И действительно получаются $2/3c$, и пример тоже есть - $8400,14000,21000$. Спасибо.