Математический форум 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 тогда считал так:
long[][] massiv=new long[2018][45];
for (int i=0; i<=2017; i++)
massiv[i][1]=1;

for (int kvadrat=2; kvadrat<=44; kvadrat++) {
for (int year=0; year<=2017; year++) {
massiv[year][kvadrat]=0;
for (int sk=0; year-sk*kvadrat*kvadrat>=0; sk++)
massiv[year][kvadrat]+=massiv[year-sk*kvadrat*kvadrat][kvadrat-1];
}
}

System.out.println(massiv[2017][44]);

Если кратко: формулы скорее всего нету, но есть последовательность 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/