Форум Академгородка, Новосибирск > Сумма n чисел натурального ряда
Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Сумма n чисел натурального ряда
Форум Академгородка, Новосибирск > Образование > Задачник
renuar911
Мы знаем что сумма всех n чисел натурального ряда выражается формулой: S=0.5n(n+1).
При каких n сумма S будет полным квадратом? То есть необходимо решить диофантово уравнение: n(n+1)=2k^2.
Составив простую программу на любом языке программирования, легко найти численно эти редкие значения n, а именно:
n=1, 8, 49, 288, 1681, 9800, 57121, 332928,1940449,...
Но можно ли вывести явную зависимость, позволяющую находить все эти числа?
ХиПси
Хорошая задачка:-)
Надо разложить в цепную дробь sqrt(2)=1.4142.....
К счастью, она (как и для всякой квадратичной иррациональности) периодическая, да еще и с периодом 1 !!!
А потом взять подходящие дроби. И, о чудо, это в точности
3/2 => 2*2^2+1 = 3^2
7/5 => 2*5^2-1 = 7^2
17/12 => 2*12^2+1 = 17^2
...
А уж подходящие дроби подчиняются рекуррентному соотношению 2-го порядка.
Так что все в порядке.
renuar911
Прекрасный анализ! Теперь найти эти реккурентные соотношения не представит труда. Пойду выводить и если что - буду к Вам обращаться за помощью. Спасибо огромное!
Serge&
Интересно отметить, что в этом ряду удовлетворяющих условию значений n имеются полные квадраты, расположенные исключительно на нечётных местах: 1, -, 49, -, 1681, -, 57121, -, 1940449 ...

Теорема: доказать, что такой порядок чередования сохраняется до бесконечности.
EVGен
Задачу кто-нибудь довел до конца?
Цитата(Serge& @ 07.11.2010, 11:52) *
Интересно отметить, что в этом ряду удовлетворяющие условию значения n имеются полные квадраты, расположенные исключительно на нечётных местах: 1, -, 49, -, 1681, -, 57121, -, 1940449 ...

Теорема: доказать, что такой порядок чередования сохраняется до бесконечности.

Serge&, это какая-то новая задача?
Serge&
Я не вполне понял, в каком смысле "новая".

С одной стороны мой вопрос связан с исходной задачей, он и формулируется на основе её частичного решения, изложенного в первом сообщении.

С другой стороны, моя часть этой задачи лишь тогда и пришла мне в голову, т.е. в этом отношении она новая. Хотя возможно, кто-то ставил такой вопрос и ранее.
Crazy Diamond
Цитата(Serge& @ 07.11.2010, 11:52) *
Интересно отметить, что в этом ряду удовлетворяющих условию значений n имеются полные квадраты, расположенные исключительно на нечётных местах: 1, -, 49, -, 1681, -, 57121, -, 1940449 ...

Теорема: доказать, что такой порядок чередования сохраняется до бесконечности.

Интересно отметить, что в этом ряду удовлетворяющих условию значений n имеются удвоенные полные квадраты, расположенные исключительно на чётных местах: -, 8, -, 288, -, 9800, -, 332998...

Теорема: доказать, что такой порядок чередования сохраняется до бесконечности.
Crazy Diamond
Гм... исследуем-ка ряд наших чисел:
1
8 = 2 * 2^2
49 = 7^2
288 = 2*12^2 = 2 * (2^2 * 3)^2 = 2^5 * 3^2
1681 = 41^2
9800 = 2 * 70^2 = 2 * (2*5*7)^2 = 2^3 * 5^2 * 7^2
57121 = 239^2
332928 = 2 * 408^2 = 2 * (2^3 * 3 * 17)^2 = 2^7 * 3^2 * 17^2
1940449 = 1393^2 = (7*199)^2 - первый квадрат составного числа в этом ряду

и так далее... Ну что скажете?
ХиПси
Ну что ж, пора выложить решение.
Прежде всего, n и (n+1) взаимно просты, значит одно из них точный квадрат, а другое удвоенный.
Отсюда возникает пара уравнений.
Либо
x^2 +1 =2*y^2
либо
x^2 - 1 =2*y^2
В любом случае, дробь x/y должна "хорошо" аппроксимировать sqrt(2).
Причем, легко оценить ошибку. Эта ошибка порядка 1/(2*x*y).
А вот здесь мы попадаем в область "наилучшей аппроксимации чисел рациональными дробями".
Всем интересующимся настоятельно советую прочитать замечательную брошюру (сравнительно небольшую)
Хинчин "Цепные дроби".
Не вдаваясь в детали, аппарат цепных дробей позволяет конструктивно получать "наилучшие"
рациональные приближения для данного числа. Причем попеременно, то СВЕРХУ, то СНИЗУ.
Можно показать, что в нашем случае только эти приближения и могут гарантировать требуемую ошибку.
Какие дроби при этом получаются? Обозначим их p/q. Тогда ряд для p и q таков
p: 1 3 7 17 41 ...
q: 1 2 5 12 29 ...
Закон образования этих чисел весьма прост:
x(n+1) = 2*x(n) + x(n-1)
Используя теорию цепных дробей, можно показать что это действительно решения наших уравнений.
А можно и по индукции (несколько утомительно).
При этом ПОПЕРЕМЕННО n=p^2 или n=p^2-1 (так что квадраты в ряду для n действительно чередуются)
Используя рекуррентное соотношение, можно предъявить и ЯВНЫЕ формулы для p и q. Вывод несложный,
как и для чисел Фибоначчи. Эта формула суть сумма n-ых степеней (с некоторыми коэффициентами)
чисел : (1+sqrt(2)) и (1-sqrt(2)).
Вот так.

Crazy Diamond
Всё гениальное просто)
EVGен
Лично мне не хватило знаний цепных дробей..

P.s. В глубине я подозревал, что удовлетворяющих дробей аппроксимирующих 2 бесконечно много))
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Русская версия IP.Board © 2001-2024 IPS, Inc.