Просмотр темы

Формула Петрова для поиска простых чисел


syndicatel	#1 Опубликовано 21-06-2024 19:22:35
Почетный автор	На днях футуролог и математик Петров опубликовал очередную интересную (своей идеей) статью "Исследование формулы простых чисел f(a) = a * dr(a) + 1" в которой привел небольшой анализ эффективности использования этой формулы для поиска чисел. Особенность формулы заключается в использовании цифрового корня (dr(a)). syndicatel присоединено следующее:файл: petrovib-issledovanieformulypr.zip [43,86kB / 11 Загрузки]


syndicatel	#2 Опубликовано 21-06-2024 19:26:00
Почетный автор	По сути статья описание формулы и небольшие данные по статистике вероятности простых чисел среди результатов генерации этой формулой натуральных чисел. Есть сравнение таковой вероятности для диапазона до а = 10^6 с известными формулами для вычисления простых чисел. Но само исследование - там по факту отсутствует. Это просто обозначение и описание формулы. Тем ни менее тема интересная. Сама формула: f(a)=a * dr(a)+1, где dr(a) - числовой корень числа a. При диапазоне а от 1 до 10^6 вероятность простых числе среди результатов - 15.79% (это действительно так - не поленился сделать на С программку). Автор приводит для сравнения полином Эйлера: n^2+n+41 для n от 1 до 10^6 вероятность простых числе среди результатов - 26.11% (никогда не слышал, что эта формула "полином Эйлера", в советской литературе он идет без названия, или я чего-то не знаю? ну да ладно... формула такая реально есть). Еще там идет сравнение с формулами Ризеля, Софи Жермен, числами Ферма. На заданном диапазоне они выдают еще меньшую вероятность простых чисел среди результатов (правда для Ризеля автор использовал фиксированный n=1, что весьма сильное ограничение). В общем формула Петрова весьма интересна судя по вероятности, но я прогнал ее до а = 10^6 и там вероятность падает до ~12%, что логично (в выборке участвует больший диапазон). По мнению Петрова вероятность простых чисел среди натуральных 11.11% - "нормальное" распределение праймов в ряду натуральных. Что вообще умозрительно - вероятность будет манятся в зависимости от ограничений диапазона выборки. Если уж брать по количеству простых чисел в диапазоне охватываемой формулой с заданным а, то справедливости ради там проценты простых чисел меньше 11.11%. Прогнать "полином Эйлера" даже до 10^8 - не вышло - очень долго на моем железе, но предполагаю, что та же история, что и с формулой Петрова. Интересно тут другое. По сути если сделать выборку по нечетным натуральным: 2*a+1 - вероятность простых чисел должна возрасти до формулы Петрова (по сути в формуле Петрова нет избавления от четных, dr(a) будет фактически случайно (относительно ряда натуральных до 10) выдавать значения от 1 до 9, и самое главное - шаг значений у Петрова больше), но проверив я увидел, что формула Петрова выдает все же большую вероятность простых, чем просто древнегреческая формула нечетного числа! Почему? Тема не столь интересна самой формулой (как мне кажется), сколько как раз связью числового корня с распределением простых чисел. Я честного говоря такого подхода еще не видел. Числовой корень обычно воспринимается как баловство для занимательных задач... Но потенциал для изучения у этой идеи однозначно есть (я про связь с праймами). Да, конечно, я отдаю себе отчет, о том, что формула Петрова привязана к 10сс. Но по факту это ничего особо не меняет. Есть формулы привязанные к той или иной сс. Но одном форуме проверили результаты для праймов вида 6к+5, 6k+1 и результаты по сравнению с формулой Эйлера в 10сс вышли очень неожиданными. Для таких праймов при а (max)=10^4, 10^5, 10^6 вышло порядка 85% простых чисел, в то время как Эйлер снижается до 66%. У меня правда получилось чуть меньшее проценты для формулы Петрова: при a=10^6 порядка 71% при выборке из всего количества диапазона праймов вида 6к+5. Но это сравнительно выше чем у Эйлера (66%) при таком же кол-во результатов. Но я возможно не точно рассчитал. Сейчас проверю код. Но в общем формула Петрова испытывает какую-то любовь к праймам вида 6к+5.