Детерминированный алгоритм поиска некоторых простых чисел

[Cantata]

Здравствуйте.
Надеюсь, что правильно раздел выбрала.

Пытаюсь понять - есть ли польза от детерминированного алгоритма, который точечно находит достаточно большой величины простое число (проверено с помощью Дипсика на числах размера 10в100 и, возможно, даже больше), но не любое, а то число, что соответствует его правилу поиска?

Это не решето, ему не нужен массив данных, так как другой принцип работы и как решето он будет совершенно не эффективен. Зато скорость нахождения удивляет и в сравнении с линейным поиском в 3-8 раз быстрее может быть. Это зависит от нахождения числа в заданном по правилам интервале.

Если взять n кандидатов, которые влияют на размер интервала, где будет искаться простое число, то почти гарантированно найдёт n простых чисел.

Но, повторюсь, детерминированно находит только "каплю в море", так как интервалы огромные. Понимаю, что продвинутым методам этот алгоритм сильно проигрывает, поэтому и думаю, что может он больше как учебный интерес вызовет, и то не факт. Или даже не тянет?

Мои сомнения в том числе и из-за того, что может код ошибочно работать и я не разобралась с его логикой)

[wrest]

Ну вот например на планшете андроид следующее простое число, большее случайного длиной 200 десятичных цифр, находится за 11 миллисекунд:

? n=random(10^200)
%108 = 720262812474573980368022432413193794578805100783260770251053761547025872
458373978606021392533788524893355903428675642518648058780399995625410025038385
69536904992011762033014197803482136289576245785642
? nextprime(n)
time = 11 ms.
%109 = 720262812474573980368022432413193794578805100783260770251053761547025872
458373978606021392533788524893355903428675642518648058780399995625410025038385
69536904992011762033014197803482136289576245785791
?

Вот для 1000 цифр (сами числа не печатаю чтобы не раздувать пост) - полторы секунды

? n=random(10^1000);
time = 1 ms.
? nextprime(n);
time = 1,466 ms.
?

А какова польза от вашего алгоритма?

Ну то есть - куда его применить, для чего?

[Cantata]

wrest
Благодарю вас за ответ!
На больших числах пока не проверяла. Сегодня, скорее всего поздно вечером, проверю и покажу результат.

wrest в сообщении #1724844 писал(а):

А какова польза от вашего алгоритма?

Ну то есть - куда его применить, для чего?

У меня идея фикс - совершенные числа и, соответственно, числа Мерсенна. Уже лет шесть, если не больше, скачу вокруг них с бубном :)) каждую идею, даже нелепую, пытаюсь к ним применять, но безуспешно.

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

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

Но результат покажу, тоже стало интересно, сколько времени ему понадобится.

[wrest]

Cantata в сообщении #1724847 писал(а):

У меня идея-фикс - совершенные числа и, соответственно, числа Мерсенна.

Но простые числа Мерсенна сейчас ищут в диапазоне десятков (или сотен) миллионов десятичных цифр :)
Ваш с дипсик-ом алгоритм туда дотянется?

[Cantata]

wrest в сообщении #1724849 писал(а):

Cantata в сообщении #1724847 писал(а):

У меня идея-фикс - совершенные числа и, соответственно, числа Мерсенна.

Но простые числа Мерсенна сейчас ищут в диапазоне десятков (или сотен) миллионов десятичных цифр :)
Ваш с дипсик-ом алгоритм туда дотянется?

Не знаю, у меня такой цели нет и не было)
У меня убеждённость, что исходя из этой пирамиды можно понять какое число Мерсенна простое, а какое составное, так как я вижу некоторые смещения, понятно, что из-за появления составных, но не могу их себе объяснить, так чтобы нужную логику построить. Поэтому я кручусь среди нескольких чисел и так далеко даже не заглядывала.

Читала, конечно, что есть несколько вариантов с огромными степенями в простые числа Мерсенна, и они ещё ждут проверки. Но решила, что вопросы буду решать по мере их поступления))

И да, в этой теме предлагаю вернуться к разговору об алгоритме) надеюсь, что будет что обсудить. А нет, так нет.

[Someone]

Cantata в сообщении #1724847 писал(а):

У меня идея фикс - совершенные числа и, соответственно, числа Мерсенна. Уже лет шесть, если не больше, скачу вокруг них с бубном :)) каждую идею, даже нелепую, пытаюсь к ним применять, но безуспешно.

Простым числам вообще и конкретно поиску больших простых чисел посвящён сайт https://t5k.org/. Конкретно числам Мерсенна, в том числе и их поиску, посвящён форум https://www.mersenneforum.org/.

[Cantata]

Someone
Благодарю! Про первый сайт раньше не слышала и он сейчас у меня не открывается, к сожалению. Второй тоже уже несколько лет как недоступен.

[Someone]

Cantata
У меня месяца 2–3 назад оба открывались, но сейчас не хотят.

[Cantata]

Someone
Вот и у меня также, не открываются.

wrest в сообщении #1724844 писал(а):

Вот для 1000 цифр (сами числа не печатаю чтобы не раздувать пост) - полторы секунды

Получила результаты своего кода. Честно скажу, когда попросила добавить информацию по времени и длине, код как-то видоизменился.
Дипсик уверяет, что используется только наш метод, но я еще разбираюсь - на первый взгляд вроде он. Покажу, что получилось.

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

   ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 1.8/1.8 MB 36.2 MB/s eta 0:00:00

=== Поиск простых чисел ~10^1000 (оптимизированная версия) ===

k= 2 -> 100000000000...000000000453 (1001 цифр, 453 проверок, 570.0ms)
k= 3 -> 141421356237...229518489193 (1001 цифр, 721 проверок, 1071.6ms)
k= 4 -> 173205080756...363954959991 (1001 цифр, 610 проверок, 943.3ms)
k= 5 -> 200000000000...000000000081 (1001 цифр, 81 проверок, 143.4ms)
k= 6 -> 223606797749...407072279401 (1001 цифр, 677 проверок, 785.8ms)
k= 7 -> 244948974278...009535325943 (1001 цифр, 1217 проверок, 1056.1ms)
k= 8 -> 264575131106...698120004307 (1001 цифр, 7 проверок, 48.4ms)
k= 9 -> 282842712474...459036977057 (1001 цифр, 113 проверок, 144.5ms)
k=10 -> 300000000000...000000001513 (1001 цифр, 1513 проверок, 1151.8ms)
k=11 -> 316227766016...609357627101 (1001 цифр, 1081 проверок, 891.8ms)
k=12 -> 331662479035...457708261969 (1001 цифр, 2521 проверок, 2097.5ms)
k=13 -> 346410161513...727909919047 (1001 цифр, 285 проверок, 217.9ms)
k=14 -> 360555127546...582252162351 (1001 цифр, 4363 проверок, 3453.1ms)
k=15 -> 374165738677...509541918791 (1001 цифр, 187 проверок, 186.1ms)
k=16 -> 387298334620...332214829211 (1001 цифр, 149 проверок, 119.0ms)
k=17 -> 400000000000...000000002083 (1001 цифр, 2083 проверок, 2502.8ms)
k=18 -> 412310562561...277642561103 (1001 цифр, 1977 проверок, 1976.8ms)
k=19 -> 424264068711...688555466159 (1001 цифр, 743 проверок, 693.1ms)
k=20 -> 435889894354...920374740909 (1001 цифр, 94 проверок, 177.9ms)

-- добавлено через 22 минуты --

Похоже, что этот метод находит какой-то класс простых чисел, у которых куча нулей.

Уверена, что в этом числе в середине одни нули, так как на меньших диапазонах много аналогичных было, конечно, короче по длине:

k= 2 -> 100000000000...000000000453 (1001 цифр, 453 проверок, 570.0ms)

[Dmitriy40]

Проверять числа вида $\sqrt{x}+y$ - вообще не новость.

Cantata в сообщении #1724859 писал(а):

k= 2 -> 100000000000...000000000453 (1001 цифр, 453 проверок, 570.0ms)
k= 5 -> 200000000000...000000000081 (1001 цифр, 81 проверок, 143.4ms)
k=10 -> 300000000000...000000001513 (1001 цифр, 1513 проверок, 1151.8ms)
k=17 -> 400000000000...000000002083 (1001 цифр, 2083 проверок, 2502.8ms)

Судя по совпадению подчёркнутых чисел, зачем-то проверялись даже чётные числа, и кратные 3 и 5 и 7 и так далее.

Cantata
В чём детерминированность алгоритма и вообще новизна? Если он судя по всему тупо перебирает числа подряд пока не наткнётся на простое? И выбор чисел вида квадратного корня ничем не помогает.

[Cantata]

Dmitriy40 в сообщении #1724860 писал(а):

Судя по совпадению подчёркнутых чисел, зачем-то проверялись даже чётные числа, и кратные 3 и 5 и 7 и так далее.

Забавно, я не заметила, ведь так и не освоила программирование и мне чат бот код написал. Но есть интересный момент - получается, что можно ещё оптимизировать?))

Dmitriy40 в сообщении #1724860 писал(а):

В чём детерминированность алгоритма и вообще новизна?

Как в чем - детерминизм в том, что это не рандом и каждый раз будет именно эти числа выдавать, так как правилом привязан к началу интервала. Соответственно такой код только как игрушка.
Я же писала, что он получился не потому что я его искала, а в процессе попыток разобраться с совершенными числами.
Если у меня получится, потом нарисую их, будет понятно почему я с квадратами стала разбираться.

А про новизну - без понятия. Я и с решетом Эратосфена только теоретически знакома.
Если вы знаете именно этот метод (который мы с Дипсиком написали), то расскажите, пожалуйста.
И не ждите от меня знаний профессионала. Я никогда не говорила, что умею программировать. И рада даже, что моя логика сработала, благодаря Дипсику.

[Dmitriy40]

Cantata в сообщении #1724861 писал(а):

Если вы знаете именно этот метод (который мы с Дипсиком написали), то расскажите, пожалуйста.

Именно этот не знаю, не вижу же его, но судя по всему он очень прост:
1. Вычисляем начало интервала как $b=\lfloor 10^{1000}\sqrt{k-1} \rfloor$ (непонятно почему $k$ с 2, а не с 1, но не суть).
2. Проверяем простое ли число $b$.
3. Если простое - нашли, конец.
4. Иначе увеличиваем $b=b+1$. Тут как раз и возможна оптимизация. Хотя многого она не выигрывает.
5. Переходим к пункту 2.

Это просто чуть ли не самый банальный алгоритм поиска следующего простого числа начиная с $b$.
А выбор именно таких $b$ ничем не помогает нахождению простых чисел, вроде бы, во всяком случае не вижу никаких теоретических предпосылок для этого.

-- добавлено через 4 минуты --

Функция ispseudoprime() в PARI именно так и работает. Ну возможно с некоторыми оптимизациями, но для таких чисел на время работы они почти не влияют.

[Cantata]

Dmitriy40
В общих чертах да, только интервал у нас иначе задаётся.

Стало интересно сравнить - если вам не очень сложно, можете показать по вашему способу - сколько времени нужно на поиск такого же количества чисел 10в1000?

[Dmitriy40]

Cantata в сообщении #1724863 писал(а):

Стало интересно сравнить - если вам не очень сложно, можете показать по вашему способу - сколько времени нужно на поиск такого же количества чисел 10в1000?

Да столько же как и у Вас:

? for(k=2,20, t0=getwalltime(); x=sqrtint((k-1)*10^2000); print("k=",k,": +",nextprime(x)-x, ", ",getwalltime()-t0,"ms"); )
k=2: +453, 907ms
k=3: +721, 1432ms
k=4: +610, 1220ms
k=5: +81, 158ms
k=6: +677, 1469ms
k=7: +1217, 2570ms
k=8: +7, 55ms
k=9: +113, 282ms
k=10: +1513, 3089ms
k=11: +1081, 2215ms
k=12: +2521, 5326ms
k=13: +285, 538ms
k=14: +4363, 9272ms
k=15: +187, 462ms
k=16: +149, 319ms
k=17: +2083, 4624ms
k=18: +1977, 4232ms
k=19: +743, 1538ms
k=20: +94, 251ms

-- добавлено через 2 минуты --

Повторюсь, это самый наибанальный алгоритм поиска простого числа большего заданного.
Вся возможная "фишка" - только в выборе начального числа, с которого проверять.
Но выбор его как корня из малого целого числа домноженного на степень десятки ничего не даёт (не должен давать) для улучшения поиска простого числа.

[Cantata]

Dmitriy40 в сообщении #1724864 писал(а):

Да столько же как и у Вас:

Классно, спасибо! Очень наглядно!)

Сама идея - брать квадрат простого, конечно не нова. И всё действительно упиралось в выбор начального числа.

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

И решила проверить как стабильно это будет продолжаться И вот проверка показала, что даже с числами 10в1000 каждая строка имеет квадрат простого числа.

Дипсик мне объяснил, что есть гипотезы и мы их придерживались)

-- добавлено через 2 минуты --

Теперь вот стало интересно, можно ли вывести алгоритм, чтобы находить простые числа, где куча нулей - я о них выше написала уже.