Новая формула для поиска простых чисел... (авторская статья)

[Dytr0^1]

Наткнулась на довольно интересную статью: https://fermat-lambert.github.io - необычный подход аналитического представления простых чисел, в котором они выражаются через функцию Ламберта. Это такое как бы "умное" решето, позволявшее приближенно искать простые числа в диапазоне кандидатов. То есть находить числа, в определенном приближении с которыми с высокой вероятностью есть простые числа.

Формула Петрова (приближённо)

[tex]p \approx \frac{\ln(K)}{\ln 2} + \frac{\ln(\ln K)}{\ln 2} + C[/tex]


* Пусть [tex]C \approx 2[/tex] для примера (подгонка, как в статье)
* Берём K = 10, 50, 100, 200, 500, 900

| K | p прибл. | Поиск ±5 | Найденные простые |
| --- | -------- | -------- | ----------------- |
| 10 | 8.7 | 4–13 | 5,7,11,13 |
| 50 | 19.2 | 14–24 | 17,19,23 |
| 100 | 24.8 | 20–29 | 23,29 |
| 200 | 30.3 | 25–35 | 29,31 |
| 500 | 40.5 | 35–45 | 37,41,43 |
| 900 | 49.1 | 44–54 | 47,53 |

* Видно, что **окрестность приближённого p** уже содержит простые числа.
* Мы не проверяем все числа до N, а только небольшой диапазон вокруг p — экономия проверок.

---
Сравнение с решетом

| Метод | Точность | Количество проверок | Примечание |
| ----------------- | ----------- | ------------------- | --------------------------------------------------------- |
| Решето Эратосфена | Все простые | \~N | Полное покрытие, но большие N → много операций |
| Формула Петрова | Ориентир | \~10–20 на K | Не гарантирует точное число, но быстро находит кандидатов |

Конечно, статья очень сыровата и сам подход требует серьезной доработки и дальнейших исследований, но мне показалось некое интересное зерно в этом есть... Тем более такое использование функции Ламберта по отношению к простым числам (я конкретно про формулу) не припоминаю...

[Dytr0^1]

Немного продолжу...

Сложность для классического решета Эратосфена, равна:

[tex]O(n \log \log n)[/tex], где [tex]n[/tex] — верхняя граница диапазона.

Допустим мы хотим найти все простые числа в диапазоне до [tex]N = 10^{10}[/tex]. Если тупо перебирать все числа по формуле из статьи - это еще хуже чем решето, так как сложность будет, примерно равна: [tex]\sim \sum_{k=2}^{10^{10}} O(\sqrt{k}) \approx O(n^{3/2})[/tex]

НО!

Суть метода из примера

* Есть аналитическая формула, которая даёт приближённое значение [tex]p[/tex] для [tex]k[/tex]-го простого числа (например, по формуле Петрова или другой аппроксимации).
* Вместо перебора всех чисел до [tex]N[/tex] мы берём небольшой интервал вокруг приближённого [tex]p[/tex], например [tex][p-5, p+5][/tex] или другой диапазон, и проверяем простоту только там.
* На практике окрестность около 10–20 чисел почти всегда содержит простое число, как видно из таблицы.

Пример из твоей таблицы:

| K | p прибл. | Диапазон ±5 | Найденные простые |
| -- | -------- | ----------- | ----------------- |
| 10 | 8.7 | 4–13 | 5,7,11,13 |
| 50 | 19.2 | 14–24 | 17,19,23 |
| … | … | … | … |

То есть не нужно проверять 50 чисел подряд — достаточно 10–15 вокруг [tex]p[/tex].

Почему это быстрее решета

* Решето проверяет все числа до [tex]N[/tex], затрачивая [tex]O(N \log \log N)[/tex] операций.
* Метод с приближённым [tex]p[/tex] делает проверку только для маленького диапазона вокруг каждой аппроксимации, например 10–20 чисел.
* Если нужно [tex]M[/tex] простых чисел до [tex]N[/tex], то общее число проверок ≈ [tex]M \cdot 20[/tex].

Для [tex]N = 10^{10}[/tex]:

* Количество простых ≈ 434 млн
* Проверок с окрестностью [tex]±5 → ≈ 434 \text{ млн} \cdot 10 \approx 4.3 \text{ млрд}[/tex] проверок
* Это меньше, чем [tex]10^{10}[/tex] проверок решета (не учитывая оптимизацию битовых массивов, но по числу операций всё равно существенно меньше).

Важные моменты

1. Метод подходит, если нам нужны все простые числа до [tex]N[/tex] в порядке их появления, потому что мы идём по порядку K и генерируем окрестности.
2. Нужна точная аппроксимация [tex]p_k[/tex]. Если приближение сильно уходит от настоящего простого, придётся расширять диапазон.
3. Экономия памяти огромная, потому что не нужно держать массив длиной [tex]10^{10}[/tex].

[Гость]

Вы правы, сама по себе идея использования аналитической аппроксимации для локализации простых чисел не является новой. Однако изящное применение в данной статье W-функции Ламберта для вывода формулы выглядит вполне новым и творческим. Ключевая особенность — это использование параметра K, порождённого не статистической теоремой о распределении, а алгебраическим соотношением из малой теоремы Ферма, что задаёт совершенно иной исходный контекст.

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

[Гость]

Почитал... Коллеги,

главный порок работы, как мне видится, — это её профанский пафос и незнакомство автора с литературой . Заявки на «новую формулу простых чисел» звучат громко и несерьёзно. Реальная ее ценность лежит не в генерации простых, а в потенциально новой аппроксимационной схеме для их локализации. Но и здесь всё упирается в старые, как мир, проблемы: выбор ветвей W-функции для отрицательных аргументов, неуниверсальность константы C и, что критично, неучёт псевдопростых чисел, засоряющих последовательность K(p).

Резюмирую: как строгое научное достижение — статья несостоятельна. Но как любопытный частный результат, демонстрирующий небанальную связь между дискретными объектами и спецфункциями, — да, это определённо имеет право на существование и может быть дидактически полезно. Развивать её стоит не в русле «поиска формул», а в рамках анализа точности асимптотик и построения гибридных алгоритмов поиска.

З.Ы.: Но надо отдать должное: изящное применение W-функции Ламберта для явного обращения соотношения, следующего из малой теоремы Ферма, — это, чёрт возьми, занятный ход. Пусть это и не фундаментальное прорывное знание, но как упражнение в математическом творчестве — вполне себе остроумно.

[Гость]

На самом деле статья довольно интересная. На редкость неплохо и грамотно оформленная.

[Гость]

Статья на самом деле интересная своим потенциалом (я про изложенную теорию). Можно применить для алгоритмов поиска простых чисел, как улучшение. Но думаю это нужно размещать на профильных форумах, посвященных теме.