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

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

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

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




Начать новую тему Ответить на тему  [ Сообщений: 25 ]  На страницу 1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения: Проблема Варинга
СообщениеДобавлено: 08 мар 2016, 10:27 
Не в сети
Мастер
Зарегистрирован:
08 янв 2016, 15:28
Сообщений: 225
Cпасибо сказано: 2
Спасибо получено:
26 раз в 24 сообщениях
Очков репутации: 2

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

Оба варианта слепые и теряют эффективность при увеличении разрядности числа

Мне пока не приходят в голову никаких идеи по поводу оптимизации этих вариантов

Существует ли какая-то связь между разложением числа на квадраты и, допустим, каноническим разложением самого числа ?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Проблема Варинга
СообщениеДобавлено: 08 мар 2016, 14:45 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Вы хотите найти все представления или хотя бы одно?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Проблема Варинга
СообщениеДобавлено: 08 мар 2016, 14:52 
Не в сети
Мастер
Зарегистрирован:
08 янв 2016, 15:28
Сообщений: 225
Cпасибо сказано: 2
Спасибо получено:
26 раз в 24 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
Достаточно найти хотя бы одно

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Проблема Варинга
СообщениеДобавлено: 08 мар 2016, 15:18 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Проблема разложения на сумму 4 квадратов сводится к проблеме факторизации, благодаря тождеству Эйлера: произведение двух сумм четырех квадратов - также сумма 4 квадратов.
Далее, если число не содержит простых делителей вида 4k-1 в нечетной степени, то разложимо на 2 квадрата, причем также сводится к поиску [math]p=x^2+y^2[/math] для простого p вида 4k+1.
Если число вида [math]4^m(8k+7)[/math], то четыре квадрата, в остальных случаях - 3.

Эти соображения уже помогут вам значительно ускорить процесс.
Как поваритесь - накидаю еще.

Решили 355 проблему Эйлера?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Проблема Варинга
СообщениеДобавлено: 08 мар 2016, 16:05 
Не в сети
Мастер
Зарегистрирован:
08 янв 2016, 15:28
Сообщений: 225
Cпасибо сказано: 2
Спасибо получено:
26 раз в 24 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
Понял, спасибо !

PS: Что касается 355-й проблемы, то у меня есть свое решение, но статус у нее неопределенный.
Я нашел решение для Co(100) = 1356.
Потом я нашел свое решение для Co(1000), Co(10000) и т.д., но у меня нет 100-процентной уверенности , что я нашел максимум.
Например, Co(1000) у меня получился = 85225, но не факт ...

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю s_e_r_g "Спасибо" сказали:
swan
 Заголовок сообщения: Re: Проблема Варинга
СообщениеДобавлено: 08 мар 2016, 19:03 
Не в сети
Мастер
Зарегистрирован:
08 янв 2016, 15:28
Сообщений: 225
Cпасибо сказано: 2
Спасибо получено:
26 раз в 24 сообщениях
Очков репутации: 2

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

Вроде, алгоритм можно еще оптимизировать: первые два квадрата, как правило, маленькие, а вторые - большие

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Проблема Варинга
СообщениеДобавлено: 08 мар 2016, 19:35 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
У вас есть библиотеки быстрого разложения числа на множители?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Проблема Варинга
СообщениеДобавлено: 08 мар 2016, 19:49 
Не в сети
Мастер
Зарегистрирован:
08 янв 2016, 15:28
Сообщений: 225
Cпасибо сказано: 2
Спасибо получено:
26 раз в 24 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
Есть как минимум два алгоритма разложения на множители:
1 Каноническое разложение числа
2 Получение всех делителей числа

Например, для n=12 первое дает [2,2,3]
Второе дает [1,2,3,4,6,12]

Какое вы имеете ввиду ?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Проблема Варинга
СообщениеДобавлено: 08 мар 2016, 19:57 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Первое.
До какого порядка числа разлагаете?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Проблема Варинга
СообщениеДобавлено: 08 мар 2016, 20:00 
Не в сети
Мастер
Зарегистрирован:
08 янв 2016, 15:28
Сообщений: 225
Cпасибо сказано: 2
Спасибо получено:
26 раз в 24 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
Нет ограничений
В разумных пределах, разумеется

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

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

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

Dengi

4

393

27 дек 2015, 17:32

Проблема с ну

в форуме Дифференциальные и Интегральные уравнения

ExtreMaLLlka

1

427

18 янв 2016, 23:11

Проблема с размерностью

в форуме Механика

crazymadman18

2

251

16 май 2018, 20:37

Проблема с заданием

в форуме Дифференциальное исчисление

dastreba

8

329

28 ноя 2017, 19:00

Проблема с форматом wav

в форуме MATLAB

Apelcin_Espada

0

353

23 апр 2017, 10:27

Ряд Лорана проблема

в форуме Комплексный анализ и Операционное исчисление

danek130995

1

384

05 дек 2014, 20:38

Проблема с доказательством

в форуме Геометрия

Kristinadefa

1

345

05 окт 2015, 11:24

Проблема Гольдбаха

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

maxleskoff

6

939

09 мар 2015, 11:34

Проблема с интегрированием

в форуме Интегральное исчисление

Nurbz

14

782

07 фев 2015, 17:53

Хьюстон. У нас Проблема

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

Kolob

7

234

17 дек 2021, 18:15


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



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

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


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

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

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

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