Об арифметических прогрессиях из аликвотных дробей биндиман А. П., Тарасов Д. А. научный руководитель д-р физ мат наук Осипов Н. Н

УДК 511.17 ОБ АРИФМЕТИЧЕСКИХ ПРОГРЕССИЯХ ИЗ АЛИКВОТНЫХ ДРОБЕЙ Биндиман А.П., Тарасов Д.А. научный руководитель д-р физ.-мат. наук Осипов Н.Н. МБОУ СОШ №10 г. Красноярска ВВЕДЕНИЕ На XXIX Международном Турнире Городов (2007/2008 уч. год, осенний тур) ученикам старших классов была предложена следующая Задача. Найти все конечные непостоянные арифметические прогрессии, сумма которых равна единице и каждый член имеет вид , где – натуральное число. Дроби вида , где – натуральное число, принято называть египетскими (другой, более распространённый термин – аликвотные). Такие дроби широко употреблялись в Древнем Египте, где других дробей, за небольшим исключением, просто не знали. Как известно, любое рациональное число можно представить в виде суммы нескольких различных аликвотных дробей. Алгоритмы отыскания такого представления в своё время предложили Фибоначчи (1180 – 1240) и М.В. Остроградский (1801 – 1862). Целью настоящей работы является решение следующей основной задачи: найти все конечные непостоянные арифметические прогрессии из аликвотных дробей, сумма которых не менее заданного . Более точно, мы хотим получить алгоритм, при помощи которого можно было бы перечислить все такие прогрессии. Будем считать далее , где – заданное натуральное число. В первой части работы решается более простая задача: найти все конечные непостоянные арифметические прогрессии из аликвотных дробей, имеющие заданную сумму . Пусть обозначает число членов искомых прогрессий. Мы доказываем оценку , в результате чего получаем алгоритм решения задачи, сложность которого . Отметим, что слишком эффективного алгоритма здесь ожидать не приходится, поскольку уже частный случай двучленных прогрессий эквивалентен вычислительно сложной задаче об отыскании всех решений в натуральных числах уравнения . Вторая часть работы посвящена решению основной задачи. Случай двучленных прогрессий не особенно интересен, поэтому считаем . Благодаря новой идее нам удалось улучшить оценку для и доказать, что . Это является основным теоретическим результатом работы. На основе этого результата мы получили алгоритм решения основной задачи со сложностью . 1. АРИФМЕТИЧЕСКИЕ ПРОГРЕССИИ ИЗ АЛИКВОТНЫХ ДРОБЕЙ С СУММОЙ Рассмотрим случай чётного (случай нечётного рассматривается аналогично). Пусть – убывающая n-членная арифметическая прогрессия и . Тогда справедливо равенство , (1) откуда следует, что для некоторого целого неотрицательного . Можно показать, что справедливо неравенство (это – ключевая идея; доказательство неравенства см. в полной версии работы), так что . Вместе с равенством (1) это позволяет получить оценку . В свою очередь, из этой оценки вытекает оценка для числа членов прогрессии: (подробный вывод этих оценок см. в полной версии работы). Перебирая теперь все пары в указанных границах, мы находим все искомые прогрессии. Поскольку и , сложность такого алгоритма составит . Этот алгоритм был реализован в системе компьютерной алгебры MAPLE. Эксперименты с программой показали, что время её работы действительно растёт пропорционально , т.е. при увеличении в 2 раза время выполнения возрастает примерно в 16 раз. 2. АРИФМЕТИЧЕСКИЕ ПРОГРЕССИИ ИЗ АЛИКВОТНЫХ ДРОБЕЙ С СУММОЙ Назовём прогрессию невыносимой, если все знаменатели взаимно просты в совокупности. Очевидно, достаточно найти все невыносимые прогрессии с суммой . Перейдём к прогрессии , где , при этом . Имеем . Таким образом, задача сводится к оценке снизу величины . Это и есть та новая идея, о которой шла речь во введении. Как оказалось, вопрос об оценке величины достаточно хорошо изучен (см., например, работы [1], [2]). Далее мы будем опираться на оценку (2) из работы [2]. В качестве иллюстрации методов её получения докажем эту оценку в частном случае, когда . Величину можно оценить следующим образом: . Действительно, имеем , где – некоторое целое число. Отсюда следует, что делится на , а значит, не меньше, чем . Теперь уже сравнительно нетрудно получить искомую оценку . В общем случае доказательство оценки (2) технически сложнее и требует больших усилий (в полной версии работы мы приводим, следуя [2], подробное доказательство этой оценки). Используя оценку (2), мы приходим к следующему неравенству: (3) для определения параметров , и (именно в таком порядке мы их будем оценивать). Из неравенства (3) следуют оценки . Отсюда находим . Теперь, используя неравенство (доказательство этого неравенства см. в работе [2]), можно оценить параметры и . В итоге приходим к окончательной оценке сложности алгоритма в виде . Этот алгоритм также был реализован в системе компьютерной алгебры MAPLE. Так, например, при получаем следующий список искомых прогрессий:

Похожие:

	Удк 377. 131. 11 Индивидуальный образовательный проект в процессах... Москва		Расчет деформации рабочей поверхности роликоподшипника иванов В.... Определение функции податливости для случая контакта ролика конечной длины с упругим слоем конечной толщины является целью данной...
	Об однонаправленном движении трёх вязких теплопроводных жидкостей... «Квалификационные методы испытаний и мониторинг смазочных материалов»«производство и применение технических жидкостей и специальных...		Неклассические логические элементы и квантовые компьютеры керп А.... Сильно коррелированные низкоразмерные электронные системы. Теория ферми-жидкости Ландау. Латинжеровская жидкость
	Э лектронный образовательный ресурс «алгоритмы быстрых вычислений»... Закон РФ «Об образовании» №122-фз в последней редакции от 22 августа 2004 года с изменениями, внесенными Федеральным законом от 17...		Интегральное представление для композиции адамара кратных рядов лорана... Цветоведение: Программа для студентов очного и заочного отделений специальностей 35. 14. 00. «Прикладная информатика» и 06. 11. 00...
	Учебно-методический комплекс дисциплины Рецензенты: Локоть Вадим Владимирович, кандидат физ мат наук, доцент кафедры математики и мом, Беляев Владимир Яковлевич кандидат...		Анализа иерархий бескорсый Н. С. научный руководитель д-р физ мат... Правительства Калужской области от 10. 10. 2011 №552 «О разработке и утверждении административных регламентов предоставления государственных...
	Реферат Отчета по проекту №1812 Отчета по проекту №1812 «Управляемая спиновая динамика квантово размерных полупроводниковых наноструктур». Руководитель проекта:...		В. Н. Ракова канд физ мат наук, доцент А. А. Меленцов Письменный Д. Т. Конспект лекций по высшей математике: полный курс. –М.: Айрис-пресс, 2006г
	Программа учебной дисциплины математика для специальностей технического... Фгу «Федеральный институт развития образования» авторы: Башмаков М. И., академик рао, доктор физ-мат педагогических наук, профессор;...		Учебно-методический комплекс дисциплины сд. 14. История математики... Автор программы: кандидат физ мат наук, доцент кафедры математики и мом локоть Наталья Васильевна
	Учебно-методический комплекс гсэ. В 1 история математической науки... Автор программы: кандидат физ мат наук, доцент кафедры математики и мом локоть Наталья Васильевна		Учебно-методический комплекс фтд: универсальная алгебра основная... ...
	Мгпу учебно-методичекий комплекс дисциплины Рецензенты: Иванчук Н. В., к п н., доцент кафедры математики и мом мгпу, Беляев Владимир Яковлевич кандидат физ мат наук, доцент...		А. А. Фет стихотворение «Бабочка» Цель урок Физ-мат класс. Глава 11 Взаимные превращения жидкостей и газов § 72, 73, 74 (коспект), упр. 14 6,7)