2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Арифметические прогрессии из египетских дробей
Сообщение02.09.2011, 20:39 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Арифметические прогрессии из египетских дробей
Сообщение03.09.2011, 18:29 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Арифметические прогрессии из египетских дробей
Сообщение03.09.2011, 22:01 
Заслуженный участник


09/02/06
4401
Москва
Любое решение из 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$.

 Профиль  
                  
 
 Re: Арифметические прогрессии из египетских дробей
Сообщение04.09.2011, 07:27 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Арифметические прогрессии из египетских дробей
Сообщение04.09.2011, 10:41 
Заслуженный участник


09/02/06
4401
Москва
Пусть числа $\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$.

 Профиль  
                  
 
 Re: Арифметические прогрессии из египетских дробей
Сообщение04.09.2011, 11:33 
Заслуженный участник


20/12/10
9111
Руст, у меня такое впечатление, что Вы решаете какую-то другую задачу. Возможно, такую: для данного $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$ сверху.

 Профиль  
                  
 
 Re: Арифметические прогрессии из египетских дробей
Сообщение04.09.2011, 15:00 
Заслуженный участник


09/02/06
4401
Москва
Я выясняю в принципе какие суммы бывают. Желательно найти все с суммой больше 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).$

 Профиль  
                  
 
 Re: Арифметические прогрессии из египетских дробей
Сообщение04.09.2011, 15:07 
Заслуженный участник


20/12/10
9111
Руст в сообщении #480220 писал(а):
Желательно найти все с суммой больше 0.1
Да, это интересная задача. Но полного решения у Вас пока нет? Или есть?

 Профиль  
                  
 
 Re: Арифметические прогрессии из египетских дробей
Сообщение04.09.2011, 16:28 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Арифметические прогрессии из египетских дробей
Сообщение04.09.2011, 16:52 
Заслуженный участник


20/12/10
9111
Руст в сообщении #480257 писал(а):
На самом деле еще только 5-6 новых решений
Может быть, и так, но как это доказать? Как, например, оценить $n$ сверху?

 Профиль  
                  
 
 Re: Арифметические прогрессии из египетских дробей
Сообщение04.09.2011, 17:35 
Заслуженный участник


09/02/06
4401
Москва
Я раньше указал оценки для $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$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 26 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: nnosipov


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group