OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Четверг, 16 Август, 2018 00:01

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 292 ]  На страницу Пред.  1 ... 11, 12, 13, 14, 15  След.
Автор Сообщение
 Заголовок сообщения: Re: Разбиение на простые множители
СообщениеДобавлено: Вторник, 19 Октябрь, 2010 13:05 

Зарегистрирован: Четверг, 08 Май, 2008 19:13
Сообщения: 680
Откуда: Киев
Madzi писал(а):
Я вывел признаки делимости на любое число, через комбинацию разрядов этого числа. Правда пока не знаю как это правильно оформить (теорема/доказательство). Но гарантировано работает.

И как, похоже на признак Паскаля?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Разбиение на простые множители
СообщениеДобавлено: Вторник, 19 Октябрь, 2010 16:10 
Аватара пользователя

Зарегистрирован: Пятница, 11 Май, 2007 21:57
Сообщения: 975
Откуда: Украина, Киев
А я нашёл закономерность, позволяющую указать диапазоны чисел натурального ряда где гарантированно нету простых чисел. Не знаю, известно-ли это сейчас кому-либо ещё... Правда, для проверки на простоту это применимо мало, поскольку нужно анализировать остаток от деления на некоторе заданное число. Но и такая проверка отвечает лишь на вопрос может-ли потенциально число быть простым или не может :roll:


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Разбиение на простые множители
СообщениеДобавлено: Вторник, 19 Октябрь, 2010 19:34 
Аватара пользователя

Зарегистрирован: Суббота, 12 Июль, 2008 22:49
Сообщения: 567
Откуда: Россия, Санкт-Петербург
Comdiv писал(а):
Madzi писал(а):
Я вывел признаки делимости на любое число, через комбинацию разрядов этого числа. Правда пока не знаю как это правильно оформить (теорема/доказательство). Но гарантировано работает.

И как, похоже на признак Паскаля?

Похоже, но более общий случай.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Разбиение на простые множители
СообщениеДобавлено: Пятница, 22 Октябрь, 2010 16:22 
Аватара пользователя

Зарегистрирован: Суббота, 10 Ноябрь, 2007 21:28
Сообщения: 584
Откуда: Хабаровск
мысль о быстродействии факторизации Математики 6.0

Где-то выше Сергей Губанов представил результаты работы пакета. И где-то там же набор чисел сгенерированных, как я понял этим же пакетом. Я разложил некоторые из них (до 24 разряда). Все они состоят из двух простых, очень близко находящихся друг от друга. Пример ручного разложения я приводил чуть выше

9851133791271859=99252983*99252773

Множители почти не отличаются. Дальше картина похожая. Может быть Математика 6.0 хорошо раскладывает, то что сама и создала? И хорошо раскладывает исходя из какого-то предположения, которое обязательно верно, если она и создала число. Такие предположения вполне возможны. Например, мне удавалось за ноль секунд методом подбора цифр в множителях факторизовать 20 значное при условии, что множители имеют одинаковую длину. Без этого предположения программа работала заметно долго.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Разбиение на простые множители
СообщениеДобавлено: Пятница, 22 Октябрь, 2010 16:27 
Аватара пользователя

Зарегистрирован: Суббота, 10 Ноябрь, 2007 21:28
Сообщения: 584
Откуда: Хабаровск
Правда числа от Математики 6.0 начиная с 22 разряда просто имеют одинаковую длину. Впрочем это то же довольно сильный факт.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Разбиение на простые множители
СообщениеДобавлено: Суббота, 23 Октябрь, 2010 04:32 
Аватара пользователя

Зарегистрирован: Суббота, 10 Ноябрь, 2007 21:28
Сообщения: 584
Откуда: Хабаровск
Не закончил мысль. Так вот мой ручной пример, на который я потратил все-таки несколько часов, методом Ферма можно факторизовать ну максимум за час. Я так думаю, что пример который факторизовал сам Ферма конечно посложнее, но в силу небольшого числа разрядов, я бы его факторизовал методом Ферма ну наверное за день работы. Вряд ли дольше. Так может быть в основе Математики 6.0 обычный метод Ферма?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Разбиение на простые множители
СообщениеДобавлено: Воскресенье, 21 Ноябрь, 2010 13:41 
Аватара пользователя

Зарегистрирован: Суббота, 10 Ноябрь, 2007 21:28
Сообщения: 584
Откуда: Хабаровск
Хочу рассказать о двух методах, так сказать снятых с вооружения. Добится хорошей эффективности от них не удалось, но осталось ощущение, что что-то существенное упущено.

Метод1. Довольно простой. Насчитаем несколько последовательных простых начиная с 2. Разобъем их на две группы и группы перемножим. Сложим полученные произведения. Полученная сумма скорее всего будет составным числом с делителями отличными от исходных. Таким образом можно упаковать, как показал эксперимент довольно много простых не вычисляя их непосредственно. Программа работала так: ей задавалось два параметра: допустимая длина произведения и количество произведений. Затем она насчитывала простые и перемножала их до тех пор, пока не будет получено заданное количество произведений заданной длины.
Далее, на множестве произведений строились все возможные сочетания, для каждого сочетания находилась сумма и алгоритмом Евклида считался НОД этой суммы с факторизуемым числом. Метод довольно хорошо работал до 16 разрядных чисел. С некоторыми муками преодолел 18 разрядное, но дальше не пошел. То есть эффективность на уровне простого перебора делителей с учетом признаков делимости.
Второй метод сложнее, о нем чуть позже.

Тестовые примеры брались из списка Сергея Губанова.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Разбиение на простые множители
СообщениеДобавлено: Воскресенье, 28 Ноябрь, 2010 05:27 
Аватара пользователя

Зарегистрирован: Суббота, 10 Ноябрь, 2007 21:28
Сообщения: 584
Откуда: Хабаровск
Второй снятый с вооружения метод основан на исследовании последовательности остатков от деления. Этот метод позволил нам продвинутся в тестах Сергея Губанова (тесты в ветке выше) до числа в 24 разряда. Есть основания полагать, что если возможно больше то немного, но в основе метода лежит интересное явление, которое я так думаю интересно и само по себе. Я нигде в литературе не нашел упоминание о этом, хотя вполне допускаю, что проблема в моем математическом кругозоре.

Рассказываю закономерность. Возьмем большое нечетное число. Мы брали миллион с копейками. Построим ряд последовательных остатков от деления этого числа на 2, 3, 4... и т.д.
В этом ряду будут встречаться последовательности остатков убывающие или возрастающие, при этом если такая последовательность состоит более чем из 2 чисел, то появляется интересная вещь. Построим ряд разностей между соседними остатками, назовем этот ряд рядом В и на ряде В построим ряд С являющийся рядом разностей элементов ряда И. Исходный ряд остатков назовем рядом А Оказывается, что монотонные последовательности ряда А это возвратные последовательности, а точнее их элементы есть суммы арифметических прогрессий, таких что каждая прогрессия отличается от другой лишь количеством элментов. Соответственные участки ряда В это и есть сами прогрессии суммы которых образуют элементы ряда А, и элементы ряда С это разности соответствующих прогрессий ряда В.

Эмпирически замечено следующее.
При приближении к корню квадратному от исходного числа (у нас миллион с копейками) разности прогрессий стремятся к 2, причем все они четные числа. Если смотреть от конца, то разности 2, 4, 6 и т.д.
Длины прогрессий увеличиваются. Между прогрессиями есть периоды хаоса, эти периоды уменьшаются и когда они достигают длины 2, то между двумя соседними прогрессиями появляется простой переход выражаемый формулой первого порядка. Я сейчас её не помню, но кому станет интересно легко получит её сам.
При переходе к новому элементу ряда С длины прогрессий становятся очень короткими, и постепенно увеличиваются. С увеличением исходного числа длины также подрастают. Это позволяет двигаться по ряду делителей большими скачками. Проблема только в том, что длины периодов хаоса также растут. Если же предположить, что делители факторизуемого числа находятся рядом, то они наверняка попадают в зону полной регулярности, то есть туда, где между прогрессиями появляется простой переход, тогда их поиск значительно упрощается, но во-первых, это не более чем частный случай и во-вторых, количество прогрессий велико, а прокочить весь пакет (множество прогрессий одной разности) нельзя, надо на ноль проверять конец каждой. А количество прогрессий в пакете также растет с ростом исходного числа.
В общем если кому интересно дарю. Ниже пример ряда:
А В С
3857 392 2
3467 390 2
3079 388 2
2693 386 2
2309 384 2
1927 382 2
1547 380 2
1169 378 2
793 376 2
419 374 2
47 372 2
4402 -4355 4727
4035 376 -4722
3670 365 2
3307 363 2
Отрезок взят из полностью регулярной области. Еще заметьте, переход между двумя последовательностями с разностью 2 выполняется числом 4.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Разбиение на простые множители
СообщениеДобавлено: Воскресенье, 28 Ноябрь, 2010 12:12 

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 7834
Откуда: Троицк, Москва
vvp писал(а):
А В С
Полезно бы повозиться на предмет аналитических выражений для этих последовательностей (или я пропустил).

Сам подъезд к проблеме выглядит как-то, по-моему, очень нехарактерно для стандартной теории чисел. Вполне возможно, что и что-то тут новенькое зацеплено, забавное само по себе, безотносительно к исходной задаче.

К проблеме Гольдбаха добавится проблема Потопахина -- почему нет.
Примеров, когда люди всматривались необычным образом в истоптанные места и обнаруживали брульянты, -- вагон.

Успехов!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Разбиение на простые множители
СообщениеДобавлено: Воскресенье, 28 Ноябрь, 2010 12:23 
Аватара пользователя

Зарегистрирован: Суббота, 10 Ноябрь, 2007 21:28
Сообщения: 584
Откуда: Хабаровск
Info21 писал(а):
vvp писал(а):
А В С
Полезно бы повозиться на предмет аналитических выражений для этих последовательностей (или я пропустил).

Сам подъезд к проблеме выглядит как-то, по-моему, очень нехарактерно для стандартной теории чисел. Вполне возможно, что и что-то тут новенькое зацеплено, забавное само по себе, безотносительно к исходной задаче.

К проблеме Гольдбаха добавится проблема Потопахина -- почему нет.
Примеров, когда люди всматривались необычным образом в истоптанные места и обнаруживали брульянты, -- вагон.

Успехов!


Я эти последовательности нашел год назад. Конечно я занимался их аналитическим выражением. Заметных успехов не достиг, не успел (успел только понять источник, откуда они появляются), наткнулся на другую интересную вещь имеющую прямое отношение к проблеме факторизации. А мне раскидываться не хочется, ничего не успею. Я же математик - любитель, у меня все очень медленно и тяжко, поэтому приходится выбирать.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Разбиение на простые множители
СообщениеДобавлено: Воскресенье, 28 Ноябрь, 2010 12:52 

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 7834
Откуда: Троицк, Москва
vvp писал(а):
А мне раскидываться не хочется, ничего не успею. Я же математик - любитель, у меня все очень медленно и тяжко, поэтому приходится выбирать.
А кто знает, *где* Вы что-нибудь успеете? Вам же не за грант отчитываться.

Но тут всё строго по самочувствию.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Разбиение на простые множители
СообщениеДобавлено: Воскресенье, 28 Ноябрь, 2010 16:35 
Аватара пользователя

Зарегистрирован: Суббота, 10 Ноябрь, 2007 21:28
Сообщения: 584
Откуда: Хабаровск
Info21 писал(а):
vvp писал(а):
А мне раскидываться не хочется, ничего не успею. Я же математик - любитель, у меня все очень медленно и тяжко, поэтому приходится выбирать.
А кто знает, *где* Вы что-нибудь успеете? Вам же не за грант отчитываться.

Но тут всё строго по самочувствию.


Дело в том, что я во всех смыслах прикладник. Мне не особенно интересны закономерности если я не знаю куда их положить, даже если вижу, что вижу, что-то не вполне тривиальное. Хотя если найти порядок в периодах хаоса между моими последовательностями, то наверное это нашлось бы куда положить.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Разбиение на простые множители
СообщениеДобавлено: Воскресенье, 28 Ноябрь, 2010 18:42 

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 7834
Откуда: Троицк, Москва
vvp писал(а):
... Хотя если найти порядок в периодах хаоса между моими последовательностями, то наверное это нашлось бы куда положить.
"Было бы корыто, а свинья найдётся." (С) Народ
:)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Разбиение на простые множители
СообщениеДобавлено: Вторник, 18 Январь, 2011 17:06 

Зарегистрирован: Пятница, 05 Декабрь, 2008 11:42
Сообщения: 18
А посчитать что-нибудь получилось?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Разбиение на простые множители
СообщениеДобавлено: Воскресенье, 30 Январь, 2011 09:12 
Аватара пользователя

Зарегистрирован: Суббота, 10 Ноябрь, 2007 21:28
Сообщения: 584
Откуда: Хабаровск
OneDecibel писал(а):
А посчитать что-нибудь получилось?


Ну да. Вот например из списка Сергея Губанова. Полный список см. выше по ветке

Число
1 0 0 1 6 8 4 7 0 4 7 3 9

Результат:
---------------------------------------
1 0 0 0 9 0 7
1 0 0 0 7 7 7
---------------------------------------

Число
1 0 0 0 3 0 4 0 2 1 8 7 9

Результат:
---------------------------------------
1 0 0 0 1 1 7
1 0 0 0 1 8 7
---------------------------------------

Число
9 9 9 3 1 2 9 1 7 8 5 0 7 1

Результат:
---------------------------------------
9 9 9 6 4 1 9
9 9 9 6 7 0 9
---------------------------------------

Число
9 8 5 1 1 3 3 7 9 1 2 7 1 8 5 9

Результат:
---------------------------------------
9 9 2 5 2 9 8 3
9 9 2 5 2 7 7 3
---------------------------------------

Число
8 2 6 3 4 2 4 9 4 9 9 4 1 3 0 5 6 1

Результат:
---------------------------------------
9 0 9 0 3 3 8 1 7
9 0 9 0 3 3 8 3 3
---------------------------------------

Число
2 1 3 0 4 3 1 7 0 3 1 7 9 2 1 1 6 8 0 9

Результат:
---------------------------------------
5 0 2 0 5 0 3 6 8 9
4 2 4 3 4 6 2 0 8 1
---------------------------------------

Число
3 8 0 7 5 6 4 5 0 8 5 2 8 5 0 7 7 0 8 1
2 9

Результат:
---------------------------------------
9 0 3 7 2 7 5 6 4 2 1
4 2 1 3 1 7 7 3 5 4 9
---------------------------------------

Число
8 1 9 1 9 8 7 7 5 6 6 7 3 4 6 8 5 9 6 7
4 4 9 9

Результат:
---------------------------------------
8 6 7 2 3 0 8 7 7 9 1 1
9 4 4 6 1 4 4 0 0 3 0 9
---------------------------------------


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Разбиение на простые множители
СообщениеДобавлено: Воскресенье, 27 Февраль, 2011 15:33 
Аватара пользователя

Зарегистрирован: Суббота, 10 Ноябрь, 2007 21:28
Сообщения: 584
Откуда: Хабаровск
Добрый день всем. У меня есть неплохой результат. В научное сообщество я не вхож, а рассказать кому-то надо, поэтому расскажу здесь. Думаю, что свободные уши найдутся. Сразу предупреждаю результат тщательно проверен. Пару лет назад я тут крепко лопухнулся, того раза мне хватило. Итак если вкраце.

Во-первых, я свел задачу факторизации к задаче решения неопределенного уравнения второго порядка. Решать его я правда могу только перебором. Объем вычислительной работы зависит от коэффициентов. К сожалению коэффициенты малы, а свободный член примерно в 16 раз меньше факторизуемого числа. Поэтому в принципе задача эквивалентна исходной.

Но во-вторых, удалось найти преобразование выравнивающее коэффициенты со свободным членом. За одну итерацию, разница уменьшается на 3-4 разряда. Таким образом при 50-значном числе для выравнивания потребуется чуть меньше 20 итераций. Уравнение с примерно одинаковыми коэффицентами простым перебором берется меньше чем за секунду.

Проблема. Каждая итерация удваивает количество уравнений, а решение имеет только одно, поэтому придется решать их все. Для числа в 50 знаков получаем временную оценку примерно сутки.

Оценка грубая, по максимуму. На самом деле непонятно, что значит быстрее секунды. Кроме того уравнения я решаю пока самым примитивным образом. Думаю возможны улучшения и кроме того.

В уравнении можно выделить так называемую главную часть она второй степени и линейную. Так вот вся масса уравнений, полученная за определенное количество итераций имеет одинаковую главную часть и отличаются они только линейной частью. Это наводит на мысль о возможности счета уравнений не по одному а гуртом.

Выше было сказано, что только одно уравнение имеет решение. Если удастся найти критерии позволяющий не считая корня просто выяснять есть он или нет, то в этом случае объем вычислений по факторизации будет зависеть только от скорости работы такого критерия.

Выше я приводил ряд решенных примеров. Эти примеры были посчитаны описанным выше методом в полуавтоматическом режиме. Программы, которая делает все от и до у меня пока нет, а есть несколько программок которые выполняют вспомогательную работу, например полный перебор для уравнения с выравненными коэффициентами.

Не буду утверждать, что этот метод лучше чем то, что уже известно людям. Но по крайней мере он качественно лучше всего того, что я делал сам. Например, числа в 15-16 знаков я могу раскладывать почти вручную. Для них уравнение выравнивается очень быстро.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Разбиение на простые множители
СообщениеДобавлено: Воскресенье, 27 Февраль, 2011 21:39 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 2846
Откуда: Астрахань
Здорово! :!:


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Разбиение на простые множители
СообщениеДобавлено: Воскресенье, 06 Март, 2011 07:05 

Зарегистрирован: Пятница, 05 Декабрь, 2008 11:42
Сообщения: 18
А почему бы теперь не написать программу по этому методу?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Разбиение на простые множители
СообщениеДобавлено: Пятница, 11 Март, 2011 13:44 
Аватара пользователя

Зарегистрирован: Суббота, 10 Ноябрь, 2007 21:28
Сообщения: 584
Откуда: Хабаровск
OneDecibel писал(а):
А почему бы теперь не написать программу по этому методу?


Думаю смысла нет. Я получил нижнюю оценку сутки для 50 знаков, и я думаю, что это на самом деле и верхняя оценка. То есть быстрее метод не сможет. Тогда получается я буду тратить силы и энергию на программу, которая намного хуже существующих. Кроме того есть куда расти в смысле математики. У меня каждая итерация удваивает количество уравнений. Их получается много, но мало того что они одного вида, у них совершенно одинаковая главная часть. Я думаю, что можно их решать оптом, а если так, то метод будет улучшен большим скачком.

П.С.

А по большому счету это вообще не мое дело. Мое дело учить программированию.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Разбиение на простые множители
СообщениеДобавлено: Вторник, 22 Март, 2011 03:46 
Аватара пользователя

Зарегистрирован: Суббота, 10 Ноябрь, 2007 21:28
Сообщения: 584
Откуда: Хабаровск
Получилось свести задачу факторизации числа к задаче факторизации меньшего числа. Если точнее, то если исходное число A то порожденное число B=A div N. Где N небольшое целое. Далее все зависит простоты факторизации числа B но так как оно не является специально подобранным, то вероятность того, что оно бьется на два труднообнаруживаемых делителя очень мала. В моих примерах все числа B факторизовались влет. Конечно за все надо платить. К задаче факторизации числа B добавляется задача перебора сочетаний из делителей числа B. Но количество нужных сочетаний не 2^k (k - количество делителей B) их существенно меньше. Кроме того, во множестве перебираемых сочетаний довольно много подходящих. Причем даже очень много. В небольших примерах количество нужных сочетаний было сопоставимо с общим количеством. Не могу утверждать, что алгоритм полиномиальный. Но 50 знаков для метода не много, в отличие от предыдущего.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 292 ]  На страницу Пред.  1 ... 11, 12, 13, 14, 15  След.

Часовой пояс: UTC + 3 часа


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

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


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

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2018, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB