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

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

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: 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
Сообщений: 245
Cпасибо сказано: 9
Спасибо получено:
41 раз в 36 сообщениях
Очков репутации: 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пасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 2 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Однозначность разложения квадрата числа в сумму 3 квадратов

в форуме Размышления по поводу и без

ivashenko

2

295

06 июл 2019, 19:05

Разбиение без квадратов

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

Xenia1996

5

601

03 авг 2017, 15:03

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

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

Olenka_S

2

934

13 фев 2016, 13:40

Получение произвольного числа из геометрической прогрессии

в форуме Начала анализа и Другие разделы школьной математики

qwertik

1

199

17 дек 2019, 07:14

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

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

Stasya7

0

364

05 мар 2015, 21:51

Определение числа простых чисел для произвольного интервала

в форуме Размышления по поводу и без

_Aleksandr_

5

342

26 авг 2020, 16:18

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

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

FastFires

2

268

21 дек 2016, 22:07

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

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

TsaAst

8

206

20 июн 2022, 10:43

23 числа и делимость разности квадратов на 100

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

Xenia1996

1

54

20 фев 2024, 01:03

Числа, представимые в виде суммы двух точных квадратов

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

Xenia1996

1

109

19 фев 2024, 00:21


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



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

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


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

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

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

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