Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 2 ] 
Автор Сообщение
 Заголовок сообщения: Разбиение числа на сумму произвольного числа квадратов
СообщениеДобавлено: 02 янв 2018, 16:59 
Не в сети
Начинающий
Зарегистрирован:
02 янв 2018, 16:48
Сообщений: 1
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Дано натуральное число 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?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Разбиение числа на сумму произвольного числа квадратов
СообщениеДобавлено: 13 фев 2018, 09:50 
Не в сети
Одарённый
Зарегистрирован:
01 дек 2015, 04:09
Сообщений: 124
Cпасибо сказано: 2
Спасибо получено:
25 раз в 21 сообщениях
Очков репутации: 4

Добавить очки репутацииУменьшить очки репутации
Если не ошибаюсь, год назад в другом месте доказывал, что прога для этого вычисления занимает 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]

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Разбиение без квадратов

в форуме Задачи со школьных и студенческих олимпиад

Xenia1996

5

311

03 авг 2017, 15:03

Задача про сумму углов произвольного тетраэдра

в форуме Интересные задачи участников форума MHP

andrei

0

390

05 мар 2012, 23:06

Найти сумму квадратов и сумму кубов корней уравнения

в форуме Теория чисел

Olenka_S

2

386

13 фев 2016, 13:40

Разбиение числа

в форуме Дискретная математика, Теория множеств и Логика

Stasya7

0

211

05 мар 2015, 21:51

Найти сумму квадратов

в форуме Тригонометрия

FastFires

2

124

21 дек 2016, 22:07

Собрать выражение в сумму квадратов

в форуме Алгебра

metal_666_

7

256

16 окт 2011, 21:06

Найдите сумму квадратов всех действительных корней уравнения

в форуме Задачи со школьных и студенческих олимпиад

AntonLord

12

1806

31 окт 2011, 21:33

Натуральные числа с разностью квадратов 2025

в форуме Теория чисел

student-it-116

8

1835

20 авг 2010, 17:05

Квадрат числа равен сумме трех квадратов

в форуме Теория чисел

Ferma

4

604

15 фев 2014, 08:58

Метод наименьших квадратов; почему именно квадратов?

в форуме Численные методы

tushkan

17

1193

04 апр 2015, 15:19


Часовой пояс: UTC + 3 часа [ Летнее время ]



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 5


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

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2018 MathHelpPlanet.com. All rights reserved