Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 3 |
[ Сообщений: 25 ] | На страницу 1, 2, 3 След. |
|
Автор | Сообщение | |
---|---|---|
s_e_r_g |
|
|
https://ru.wikipedia.org/wiki/%D0%9F%D1 ... 0%B3%D0%B0 Любое натуральное число можно представить в виде суммы квадратов, кубов, биквадратов и т.д. Причем для числа таких квадратов, кубов и т.д. известно минимальное количество. Так, любое натуральное число можно представить в виде суммы 4 квадратов Например: 12345=1+4+676+11664 12345=7056+3844+484+961 12345=1444+8100+2401+400 12345=2304+5776+169+4096 123456=16+144+55696+67600 1234567=1+9+301+401+933156 12345678=1+16+656100+11689561 123456789=1+16+34644996+88811776 1234567890=1+4+63696361+1170871524 Одно число можно разложить несколькими способами Понятно, что число можно разложить и на три квадрата, но это справедливо не для всех чисел Для кубов минимальное количество слагаемых равно 9 У меня возникли проблемы при реализации алгоритма, по которому я нахожу подобное разложение Для маленьких чисел все работает, но начиная где-то с 10 разрядов эффективность начинает стремительно падать Я реализовал два простых алгоритма, и оба одинаково неэффективны. Сначала я создаю таблицу квадратов, которая может быть достаточно большой, но не может быть бесконечной, поскольку у персоналок всегда существуют ограничения по доступной памяти И чем большего размера такая таблица, тем медленнее работает поиск Далее я использую один из двух вариантов: первый - это тупой вложенный цикл по этой таблице и перебор всех возможных комбинаций из квадратов второй - случайный выбор из таблицы трех квадратов с последующим одним проходом по всей таблице. добавлением 4-го квадрата и проверкой Оба варианта слепые и теряют эффективность при увеличении разрядности числа Мне пока не приходят в голову никаких идеи по поводу оптимизации этих вариантов Существует ли какая-то связь между разложением числа на квадраты и, допустим, каноническим разложением самого числа ? |
||
Вернуться к началу | ||
swan |
|
|
Вы хотите найти все представления или хотя бы одно?
|
||
Вернуться к началу | ||
s_e_r_g |
|
|
Достаточно найти хотя бы одно
|
||
Вернуться к началу | ||
swan |
|
|
Проблема разложения на сумму 4 квадратов сводится к проблеме факторизации, благодаря тождеству Эйлера: произведение двух сумм четырех квадратов - также сумма 4 квадратов.
Далее, если число не содержит простых делителей вида 4k-1 в нечетной степени, то разложимо на 2 квадрата, причем также сводится к поиску [math]p=x^2+y^2[/math] для простого p вида 4k+1. Если число вида [math]4^m(8k+7)[/math], то четыре квадрата, в остальных случаях - 3. Эти соображения уже помогут вам значительно ускорить процесс. Как поваритесь - накидаю еще. |
||
Вернуться к началу | ||
s_e_r_g |
|
|
Понял, спасибо !
PS: Что касается 355-й проблемы, то у меня есть свое решение, но статус у нее неопределенный. Я нашел решение для Co(100) = 1356. Потом я нашел свое решение для Co(1000), Co(10000) и т.д., но у меня нет 100-процентной уверенности , что я нашел максимум. Например, Co(1000) у меня получился = 85225, но не факт ... |
||
Вернуться к началу | ||
За это сообщение пользователю s_e_r_g "Спасибо" сказали: swan |
||
s_e_r_g |
|
|
Немного оптимизировал код и добрался до 15-го разряда
12345678901 = 1+64+3462616336+8883062500 123456789012 = 1+9+2407766761+121049022241 1234567890123 = 1+25+22067399601+1212500490496 12345678901234 = 1+64+71075560000+12274603341169 123456789012345 = 1+324+224321587876+123232467424144 Вроде, алгоритм можно еще оптимизировать: первые два квадрата, как правило, маленькие, а вторые - большие |
||
Вернуться к началу | ||
swan |
|
|
У вас есть библиотеки быстрого разложения числа на множители?
|
||
Вернуться к началу | ||
s_e_r_g |
|
|
Есть как минимум два алгоритма разложения на множители:
1 Каноническое разложение числа 2 Получение всех делителей числа Например, для n=12 первое дает [2,2,3] Второе дает [1,2,3,4,6,12] Какое вы имеете ввиду ? |
||
Вернуться к началу | ||
swan |
|
|
Первое.
До какого порядка числа разлагаете? |
||
Вернуться к началу | ||
s_e_r_g |
|
|
Нет ограничений
В разумных пределах, разумеется |
||
Вернуться к началу | ||
На страницу 1, 2, 3 След. | [ Сообщений: 25 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Проблема
в форуме Алгебра |
4 |
393 |
27 дек 2015, 17:32 |
|
Проблема с ну | 1 |
427 |
18 янв 2016, 23:11 |
|
Проблема с размерностью
в форуме Механика |
2 |
251 |
16 май 2018, 20:37 |
|
Проблема с заданием
в форуме Дифференциальное исчисление |
8 |
329 |
28 ноя 2017, 19:00 |
|
Проблема с форматом wav
в форуме MATLAB |
0 |
353 |
23 апр 2017, 10:27 |
|
Ряд Лорана проблема | 1 |
384 |
05 дек 2014, 20:38 |
|
Проблема с доказательством
в форуме Геометрия |
1 |
345 |
05 окт 2015, 11:24 |
|
Проблема Гольдбаха | 6 |
939 |
09 мар 2015, 11:34 |
|
Проблема с интегрированием
в форуме Интегральное исчисление |
14 |
782 |
07 фев 2015, 17:53 |
|
Хьюстон. У нас Проблема
в форуме Алгебра |
7 |
234 |
17 дек 2021, 18:15 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 11 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |