Арифметические прогрессии из египетских дробей

[Руст]

Можно взять любые рациональные числа из арифметической прогрессии $\frac{a_i}{b_i}$ и поделить все члены на $lcm(a_i)$ или еще на что то, то все дроби будут $\frac{1}{n_i}$.

[nnosipov]

Лучше поставить задачу в таком виде: дано положительное рациональное число $S$; предложить алгоритм, перечисляющий все арифметические прогрессии из египетских дробей с суммой $S$ (заодно доказав, что их может быть только конечное число).
Случай $S=1$ --- это задача с XXIX турнира городов (А.К. Толпыго). Решение, которое там приведено (авторское?), довольно симпатично, но мне показалось малопригодным для обобщений (впрочем, толком над этим не думал). Удалось найти другой, вполне сермяжный подход, которой предоставляет искомый алгоритм для произвольного $S$. А недавно случайно обнаружил ещё одно решение этой задачи Толпыго в "Математике в школе" (№ 6 за 2008 год, задача 4990), как раз в духе того, что мне придумалось.

[Руст]

Любое решение из n элементов сводится к выбору двух взаимно простых целых $a,h$ вычислению $m=lcm(a,a+h,...,a+(n-1)h)$. Тогда правильное (без общего делителя) решение получается в виде $n_i=\frac{m}{a+ih},i=0,1,...,m-1$.
Остальные решения получаются умножением всех $n_i$ на некоторое натуральное число. Легко вычислять $m=\frac{a(a+h)...(a+nh-h)}{Q}, Q=\prod_{p\not |n}p^{k_p}, k_p=\sum_i[\frac{n-1-b_i}{p^i}], b_i=a*n^{-1}\mod p^i$.
Легко проверяется, что $\frac{P}{S}\le Q\le P$, где $P$ произведение всех вычетов по модулю n без простых делителей n, $S$ - их НОК. Это позволяет оценить сумму.
Очевидно исключаем случаи $n=2$. когда любые два $n_i$ являются решением и случай $h=0$ (в этом случае так же сумма может быть любым рациональным числом). Отсюда можно оценить количество таких последовательностей с суммой $S>\epsilon$.

[nnosipov]

Руст, объясните, пожалуйста, Вашу идею на конкретном примере (скажем, для моего $S=1/3$). Я ничего не понял из Вашего текста. Если кто-то понял, то, может быть, напишет более понятным языком?

[Руст]

Пусть числа $\frac{1}{n_i}, i=0,1,...,n-1,n>2$ oбразует арифметическую прогрессию с положительным шагом. Пусть $m$ наименьшее общее кратное этих чисел. Тогда $a_i=\frac{m}{n_i}$ целочисленная арифметическая прогрессия и можно считать $a_i=a+ih, i=0,1,...,n-1$. При этом $gcd(a,h)=1$, иначе $m$ получилось бы больше $lcm(n_i,0\le i<n).$
Обратно, имея арифметическую прогрессию натуральных чисел $a_i=a+ih$, не имеющих общего кратного $(a,h)=1$, вычислив их наименьшее общее кратное $m=lcm(a_i)$ получаем египетские числа $n_i=\frac{m}{a_i}$ без общего кратного. Числа с общим кратным k получаются умножением всех $n_i$ на к, при этом сумма египетских дробей $S$ уменьшится в k раз. Поэтому, достаточно ограничится случаем правильных (без общего делителя для $n_i$) египетских дробей.
Соответственно вопрос сводится к оценке $lcm(a_i)=\frac{\prod_i a_i}{Q}$. Это даст оценку суммы

$$S=\sum_i \frac{1}{n_i}=\sum_i\frac{a_i}{m}=\frac{Q(2a+(n-1)h)n}{2\prod_{i=0}^{n-1}(a+ih)}.$$

Число $Q$ легко вычисляется через простые числа. Простые числа $p\ge n$ не входят в разложение $Q$, так как если одно из $a_i$ делится на некоторую степень $p$, то другие на него не делятся и при вычислении $lcm$ надо брать ту же степень $p$ и сокращать не надо, т.е. $v_p(Q)=0$. Для простых $p, p^k<n$ вычисляем количество тех $p^k|a_i$. Если $p|h$, то $p\not |a_i$, поэтому $v_p(Q)=0$. Для других $p^k<n$ находим номера $i$, что $p^k|a+ih$. Это $i=a*h^{-1}\mod p^k$. При вычислении lcm надо оставить только одно из таких степеней для чисел, остальные внести в $v_p(Q)$. Соответственно $v_p(Q)=\sum_{p^k<n,p\not |h,k\ge 1}[\frac{n-1-b(p,k)}{p^k}], b(p,k)=a*h^{-1}\mod p^k$.

Конкретные примеры. Случай $n=3$. В этом случае $Q=1$ в случае $a-odd$, или $Q=2$ в случае $a- even$. Соответственно $S=\frac{3Q}{a(a+2h)}$. Легко находятся все правильные египетские дроби с $S>0.1$. Это $a=1, h=1,...14$, $a=2, h=1,3,5,..,13$, $a=3,h=1,2$, $a=4,h=1,3,5$, $a=6,h=1$. Неправильные с учетом множителя 2- $a=1,h\le 6$, $a=2,h=1,3,5$, $a=4,h=1$, с множителем 3 $a=1,h=1,2,3,4$, $a=2,h=1,3$, c множителем 4 $a=1,h=1,2,3, a=2,h=1$, с множителем 5 $h=1,a=1,2$, $a=1,h=2$ и дроби $h=1,a=1, n_0=6,n_1=3,n_2=2,S=1$ c множителями меньше 10 и дроби $a=2,h=1, n_0=6,n_1=4,n_2=3,S=\frac 34$ c множителями меньше 8.

Еще пример $h=1$ с произвольным $n>2$. Тогда $Q\le (n-1)!$ так же легко перечислить все $a$ для которых $S>0.1$.
При $h>1$ убывание пропорционально $h^{2-n}$ по h и легко перечислить все $S>0.1$.

[nnosipov]

Руст, у меня такое впечатление, что Вы решаете какую-то другую задачу. Возможно, такую: для данного $n>1$ найти все $n$-членные арифметические прогрессии из египетских дробей, суммы $S$ которых больше $1/10$. Во всяком случае, из Ваших конкретных примеров я понял именно так.

Меня же интересует вопрос о том, как найти, например, все арифметические прогрессии из египетских дробей с суммой $S=1/3$ (число членов $n$ таких прогрессий a priori не фиксировано и, в принципе, может быть произвольным). Оказывается, для $S=1/3$ существуют 1 двучленная, 2 трёхчленных и 1 пятичленная такие прогрессии, и других прогрессий с суммой $S=1/3$ нет, каково бы ни было $n$. Хотелось бы увидеть доказательство этого факта.

Кажется, начал понимать, что имеется в виду. Нужно оценивать $\mathrm{lcm}{(a,a+h,\dots,a+(n-1)h)}$ снизу и затем сравнивать с $\sum_{i=0}^{n-1} (a+ih)$. Для этого, видимо, нужно как-то оценить $n$ сверху.

[Руст]

Я выясняю в принципе какие суммы бывают. Желательно найти все с суммой больше 0.1 А ваша конкретная задача будет следовать отсюда непосредственно. К тому же так получаются откуда берутся соответствующие решения и доказательство того, что других нет. Вот реультаты выраженные через $a,h,n,c$ (последнее общий множитель) и $n_i$:
1) $S=1, (1,1,3,1), n_i=6,3,2$,
2)$S=\frac{5}{6}, (1,1,4,1), n_i=12,6,4,3$
3)$S=\frac 34, (2,1,3,1), n_i=6,4,3$
4)$S=\frac{3}{5},(1,2,3,1),n_i=(15,5,3),$
5)$S=\frac 12, (1,1,3,2), n_i=12,6,4$,
6)$S=\frac{5}{12},(1,1,4,2),n_i=(24,12,9,6$,
7)$S=\frac{11}{28}, (1,3,3,1),n_i=(28,7,4),$
8)$S=\frac{3}{8}, (2,1,3,2),n_i=(12,8,6$,
9)$S=\frac{3}{8}, (2,3,3,1),n_i=(20,8,5),$
10)$S=\frac{21}{60},(1,1,6,1)n_i=(60,30,20,15,12,10),$
11)$S=\frac 13, (1,1,3,3), n_i=(18,9,6),$
12)$S=\frac 13, (1,4,3,1),n_i=(45,9,5),$
13)$S=\frac{1}{3},(2,1,5,1),n_i=(30,20,15,12,10).$
Здесь двучленные не включены. Для $S=\frac 13$ это $n_i=(12,4).$

[nnosipov]

Руст в сообщении #480220 писал(а):

Желательно найти все с суммой больше 0.1

Да, это интересная задача. Но полного решения у Вас пока нет? Или есть?

[Руст]

На самом деле еще только 5-6 новых решений без множителей с $S>0.1$, остальные с множителями к новым и старым решениям.

[nnosipov]

Руст в сообщении #480257 писал(а):

На самом деле еще только 5-6 новых решений

Может быть, и так, но как это доказать? Как, например, оценить $n$ сверху?

[Руст]

Я раньше указал оценки для $Q$. При $h\ge 2$ можно пользоваться грубой оценкой $Q\le (n-1)!$.
Тогда

$$S\le \frac{n!(2a+(n-1)h)}{2\prod_{i=0}^{n-1}(a+ih)}$$

даст $n\le\log_h(\frac{e}{2\epsilon})$ для $S\ge \epsilon$.
При $h=1$ надо более аккуратно оценить $S=\frac{n(n-1+a)}{2 lcm(a,a+1,....,a+n-1)}\le \frac{n(a+n-1)}{a*2^{n-1}}$.
Это даст так же логарифмическую оценку.
Для $S\ge 0.1$ всегда $n\le 6$, причем $n=6$ только для $h=1,a=1$, $n=5\to h=1,a\le 2$.