Математический форум Math Help Planet http://mathhelpplanet.com/ |
|
Разбиение числа на сумму произвольного числа квадратов http://mathhelpplanet.com/viewtopic.php?f=48&t=57632 |
Страница 1 из 1 |
Автор: | chimikus [ 02 янв 2018, 16:59 ] |
Заголовок сообщения: | Разбиение числа на сумму произвольного числа квадратов |
Дано натуральное число N. Вопрос: сколькими способами можно его разбить на сумму произвольного числа квадратов натуральных чисел? Пример: N = 10 Варианты разбиений: 10 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 10 = 4 + 1 + 1 + 1 + 1 + 1 + 1 10 = 4 + 4 + 1 + 1 10 = 9 + 1 Ответ: число разбиений равно 4. Можно ли решить эту задачу в общем виде? Может быть, существует хотя бы аппроксимационная формула, которая будет работать при больших N? |
Автор: | Zatamon [ 13 фев 2018, 09:50 ] |
Заголовок сообщения: | Re: Разбиение числа на сумму произвольного числа квадратов |
Если не ошибаюсь, год назад в другом месте доказывал, что прога для этого вычисления занимает 10 строчек и считает очень быстро. Для 2017 тогда считал так: Если кратко: формулы скорее всего нету, но есть последовательность http://oeis.org/A001156 А считать на компе проще всего так: Введем функцию [math]f(a,b)[/math] - чссло разбиений числа a на квадраты из квадратов не более чем [math]b^2[/math] на нее можно наложить очевидное рекуррентное соотношение вот по этому соотношению и считать до [math]f(n, \sqrt{n})[/math] |
Страница 1 из 1 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |