Число 113
- это первое простое число, длина 3
которого проста, цифровая сумма 5 = 1 + 1 + 3
проста, а цифровое произведение 3 = 1 * 1 * 3
простое.
Простое число, которое имеет эти 3 свойства, будет называться в высшей степени простым . Простые числа 11117
и 1111151
другие примеры.
Цель
Напишите программу, которая может найти наибольшее простое число, меньшее возможного, менее чем за час на приличном современном персональном компьютере (например, предпочтительная спецификация здесь ).
Вы не должны просто дать нам большое высшее премьер. Вы должны показать нам свой процесс поиска с кодом, который действительно работает. Вы можете опираться на свои или чужие решения, но обязательно им следует отдать должное. Мы как бы пытаемся совместно найти самый большой главный реализм на обычном компьютере за час.
счет
Представление, которое находит самый большой верхний премьер выигрывает. Если окажется, что конечных простых чисел конечное число, то первое подчинение, которое порождает высшие простые первичные выигрыши, выигрывает.
(Если вы можете математически доказать, что существует или не существует бесконечно много высших простых чисел, я дам вам 200 повторений за награду только потому, что. :))
Детали
- Вы можете использовать любой источник для генерации ваших простых чисел (например, интернет).
- Вы можете использовать вероятностные простые методы тестирования.
- Все в базе 10.
- Ноль и единица НЕ считаются простыми.
- Простые числа, которые содержат,
0
имеют цифровой продукт0
так очевидно, что они не могут быть высшими. Чтобы страница была менее загроможденной, поместите большие (более 100 цифр) верхние простые числа в форму:
{[number of 1's before the prime digit]}[prime digit]{[number of 1's after the prime digit]}
Так
1111151
можно выразить как{5}5{1}
.
источник
Ответы:
Perl, 15101 цифр, {83} 7 {15017}, 8 минут. Макс найдено: 72227 цифр
Используя мой модуль Math :: Prime :: Util и его GMP-сервер . Он имеет ряд тестов на композитность, в том числе is_prob_prime () с тестом ES BPSW (немного более строгим, чем ispseudoprime Пари), is_prime (), который добавляет одну случайную базу MR, и is_provable_prime (), которая будет запускать BLS75 T5 или ECPP. При таких размерах и типах доказательство займет много времени. Я бросил еще один тест MR в сабвуфере верификатора. Время от времени на Core2 E7500, который определенно не самый быстрый мой компьютер (на моем i7-4770K это занимает 2,5 минуты).
Как указывает Тим С., мы можем продолжать поиск больших значений, вплоть до момента, когда один тест занимает час. При значении ~ 15000 цифр на этом E7500 требуется около 26 с для теста MR и 2 минуты для полного is_prime (пробное деление плюс базовое 2 MR плюс ES Lucas плюс одно случайное базовое MR). Мой i7-4770K более чем в 3 раза быстрее. Я попробовал несколько размеров, в основном, видя, как это было на результаты других людей. Я пробовал 8k, 20k и 16k, убивая каждого через ~ 5 минут. Затем я пробовал 15к в прогрессии по ~ 10м каждый и мне повезло на 4-м.
PRP-тесты OpenPFGW, безусловно, быстрее, чем после 4000 или около того цифр, и намного быстрее, действительно, в диапазоне 50k +. Однако его тест содержит значительное количество ложных срабатываний, что делает его хорошим предварительным тестом, но все же хотелось бы проверить результаты с помощью чего-то еще.
Это может быть распараллелено с потоками Perl или с использованием MCE, аналогично параллельным примерам первичного поиска Фибоначчи в модуле.
Время и результаты на холостом ходу i7-4770K с использованием одного ядра:
Для результата с 32-значным числом я запустил 6 сценариев, запущенных одновременно, каждый с последовательными аргументами, начинающимися с 32000. Через 26,5 минут один закончил с показанным результатом с 32063-значным результатом. Для 57k я позволял последовательным сценариям запускаться по 6 раз в течение часа с шагом ввода 500, пока результат 57k не вернется через 57 минут. Результат из 72 тыс. Цифр был найден путем выполнения последовательных простых чисел от 70 тыс., Поэтому определенно не найден через час (хотя, как только вы знаете, с чего начать, это так).
Сценарий:
источник
gmpy2
и PyPy сmy_math
): codepad.org/aSzc0esTforprimes { ...do stuff... } 1e7;
10-кратный или более быстрый (спасибо Pari / GP за множество отличных идей). Я всегда ценю обратную связь, поэтому дайте мне знать, если что-то работает не так, как вам хотелось бы.Python 2.7 на PyPy, {2404} 3 {1596} (~ 10 ^ 4000)
Нашел это примерно через 50 минут после начала с 4000. Поэтому я бы оценил, что это верхний предел этого подхода кода.
Изменение: я заметил, что некоторые длины кажутся более плодотворными для генерации такого простого числа, чем другие, поэтому я решил проверить только 50 случайных положений цифры, которые не равны 1, вместо всех возможных положений перед перемещением на. Я не совсем уверен, что это улучшит производительность, или что 50 - это правильно, но посмотрим.
Список возможностей формируется на основе того факта, что для выполнения требования к продукту число должно быть все, кроме простого. Кроме того, простое число не может быть 2 из-за отношения суммы и длины, а цифровая сумма не должна делиться на три, что соответствует требованиям% 3.
is_prime взято с http://codepad.org/KtXsydxK , написано @primo
Примечание: эта функция is_prime на самом деле является тестом псевдопростоты Baillie-PSW, но нет известных контрпримеров, поэтому я не буду беспокоиться о различии.
источник
is_very_very_very_very_very_very_very_probably_prime()
...PARI / GP, 4127 цифр
(10 4127 -1) / 9 + 2 * 10 515
Это довольно простой поиск: проверяйте только длину простых чисел, затем вычисляйте возможные простые числа для использования, а затем просматривайте все возможные варианты. Я специально рассмотрел общие случаи, когда есть 0 или 1 подходящих простых цифр для использования.
Это заняло 36 минут, чтобы вычислить на одном ядре довольно старой машины. Я уверен, что найти такое простое число из 5000 цифр в час не составит труда, но я также нетерпелив.
Лучшим решением было бы использовать любой разумный язык для выполнения всего, кроме самого внутреннего цикла, а затем создать файл abc для простой формы, оптимизированный для этого конкретного вида вычислений. Это должно быть в состоянии подтолкнуть расчет по крайней мере до 10000 цифр.
Изменить : я реализовал гибридное решение, описанное выше, но на моей старой машине я не могу найти первый термин с> = 10000 цифр менее чем за час. Если я не запускаю его на чем-то более быстром, мне придется перейти на менее высокую цель.
источник
Mathematica 3181 цифр
Обновление: были некоторые серьезные ошибки в моем первом представлении. Я смог посвятить некоторое время проверке результатов для этого. Вывод форматируется в виде списка цифр. Это облегчает проверку каждого из условий.
пример
Это был мой первый тест, поиск решения с 3181 цифрами. Он обнаружил первый случай за 26 секунд.
Давайте рассмотрим рассуждения. Тогда мы перейдем к самой программе.
Давайте начнем, как я сделал, "Что такое 450-е простое число?" Можем ли мы найти решение с таким количеством цифр (3181)?
Номер определяется путем соединения цифр.
Но вместо того, чтобы отображать это, мы можем спросить, что это за цифры и где они лежат.
Это означает, что было 3180 экземпляров цифры 1 и один экземпляр цифры 7.
В каком положении находится цифра 7?
Таким образом, цифра 7 является 142-й цифрой. Все остальные 1.
Конечно, произведение цифр должно быть простым, а именно 7.
И сумма цифр тоже простое число.
И мы знаем, что число цифр простое. Помните, мы выбрали 450-е простое число, а именно 3118.
Так что все условия были выполнены.
источник
4002 * 1 + 7 = 4009
а не 4003 в соответствии со спецификацией.Python 2.7, 6217 цифр: {23} 5 {6193} 6 минут 51 секунда
Я работал над своей собственной версией и был разочарован, увидев, что @issacg избил меня до отказа с помощью очень похожего подхода, хотя и с is_ (very_probbly) _prime (). Тем не менее, я вижу, что у меня есть некоторые существенные различия, которые приводят к лучшему ответу за меньшее время (когда я также использую is_prime). Чтобы прояснить это, когда я также начинаю с 4000, я получаю лучший 4001-значный ответ ({393} 7 {3607}) всего за 26 минут, 37 секунд, используя стандартный интерпретатор Python (также в версии 2.7), а не PyPy версия. Кроме того, я не проверяю номера на месте. Все кандидаты проверены.
Вот основные улучшения:
Используйте генератор простых чисел ( https://stackoverflow.com/questions/567222/simple-prime-generator-in-python/568618#568618 ), чтобы создать список простых чисел для проверки и (его версия «маленьких простых чисел») и для генерации приемлемых длин номеров.
Мы хотим потратить наше время на поиск наибольшего высшего простого числа заданной длины, а не наименьшего, поэтому сначала я проверяю самые большие возможные числа для проверки, а не самые маленькие. Затем, как только кто-то найден, мы можем сразу перейти к следующей длине.
РЕДАКТИРОВАТЬ: теперь с многопроцессорной
Это значительное изменение по сравнению с предыдущими версиями. Раньше я заметил, что моя 8-ядерная машина почти не работает, поэтому я решил попробовать свои силы в многопроцессорной обработке на Python (впервые). Результаты очень хорошие!
В этой версии создаются 7 дочерних процессов, которые отбирают «задачу» из очереди потенциальных возможностей (num_length + допустимые цифры). Они пытаются пробовать разные [7,5,3] позиции, пока не найдут одну. Если это так, информирует основной процесс о новой самой длинной длине, которая была найдена. Если дети работают с более короткой длиной num_length, они просто освобождают под залог и получают следующую длину.
Я начал этот пробег с 6000, и он все еще работает, но пока я очень доволен результатами.
Программа еще не остановилась правильно, но для меня это не очень важно.
Теперь код:
источник
my_math
также может быть использован для создания списка простых чисел, а ляwhile prime < 20006: prime = next_prime(prime)
. Кажется, примерно в 3 раза быстрееgen_primes
, и гораздо более эффективно использовать память.C, GMP - {7224} 5 {564} = 7789
Престижность @issacg и всем вам, ребята, за вдохновение и трюки.
А также мастерский вопрос задающий @ Calvin's Hobbies для этого вопроса.
Обобщение:
gcc -I/usr/local/include -o p_out p.c -pthread -L/usr/local/lib -lgmp
Если вы чувствуете, что жертвуете своими вычислительными возможностями или вам интересна производительность, не стесняйтесь копировать код и компилировать. ;) Вам нужно установить GMP.
источник
PFGW, 6067 цифр, {5956} 7 {110}
Запустите PFGW со следующим входным файлом и
-f100
введите числа. Примерно через 2-3 минуты процессора на моем компьютере (i5 Haswell) он находит PRP (10 ^ (6073-6) -1) / 9 + 6 * 10 ^ 110 или {5956} 7 {110} . Я выбрал 6000 цифр в качестве отправной точки в качестве номера «ничего-до-моего-рукава», который немного выше, чем во всех предыдущих представлениях.Основываясь на том, как быстро я смог найти этот, я мог легко увеличить количество цифр и все еще найти PRP в течение часа. С помощью написания правил я мог бы даже найти размер, в котором мой ЦП, работающий на всех 4 ядрах, может завершить один тест PRP за час, занять много времени, чтобы найти PRP, и мой поиск будет состоять исключительно одного PRP.
PS В некотором смысле это не «кодовое» решение, потому что я ничего не написал, кроме входного файла ... но тогда многие однострочные решения математических задач Mathematica можно было бы описать так же, как и используя библиотеку, которая делает тяжелую работу за вас. На самом деле, я думаю, что трудно провести хорошую черту между ними. Если хотите, я мог бы написать скрипт, который создает входной файл PFGW и вызывает PFGW. Скрипт может даже выполнять поиск параллельно, использовать все 4 ядра и ускорить поиск в ~ 4 раза (на моем процессоре).
PPS Я думаю, что LLR может выполнить тесты PRP для этих чисел, и я ожидаю, что это будет намного быстрее, чем PFGW . Специальная программа просеивания могла бы также лучше учитывать эти цифры, чем PFGW по одному. Если бы вы объединили их, я уверен, что вы могли бы раздвинуть границы намного выше, чем существующие решения.
источник
Python 2.7, 17-19 цифр
Найдено 5111111111111 (13 цифр) за 3 секунды и это 17-значный высший штрих за 3 минуты. Я предполагаю, что целевая машина может запустить это и получить 19-значное простое число за менее чем час. Этот подход плохо масштабируется, потому что он сохраняет простые числа до половины количества целевых цифр в памяти. 17-значный поиск требует хранения массива 100M логических. Для 19 цифр потребуется массив элементов 1B, и память будет исчерпана до получения 23 цифр. Runtime, вероятно, тоже будет.
Подходы теста простоты, которые не включают в себя смехотворно большой массив простых делителей, будут намного лучше.
источник
Mathematica
42114259 цифрС номером:
{1042} 7 {3168}{388} 3 {3870}Который был сгенерирован следующим кодом:
Броски заставляют это прекратить проверять другие числа с теми же самыми цифрами как найденный в настоящее время. поскольку он начинает тестирование с самой значимой цифры, это будет означать, что он всегда возвращает наибольшее число, если только число цифр не является членом простого триплета.
Просто начал тестирование чуть ниже значения одного из предыдущих ответов :)
По окончании число сохраняется в переменной curlargest
источник
JavaScript, 3019 цифр, {2,273} 5 {745}
Для этого используется тест MillerRabin, включенный в BigInteger.js Томом Ву.
Начиная с 0 => 2 046 цифр = {1799} 7 {263} за один час .
Начиная с 3000 => 3,019 цифр = {2,273} 5 {745} за один час, менее 3 секунд .
Когда он начался с 0, программа пропустила его и снова начала поиск на длине 1,5Х длины последнего найденного s-простого числа. Затем, когда я увидел, насколько быстро он работает, я догадался, что он найдет один, начинающий с 3000 за один час - что он сделал за 3 секунды.
Вы можете попробовать это здесь: http://goo.gl/t3TmTk
(Установите для вычисления всех s-простых чисел или пропустите.)
Программа работает путем построения строк всех "1", но с одной "3", "5" или "7". Я добавил быструю проверку в функцию IsStrPrime, чтобы отклонить числа, оканчивающиеся на «5».
Это было довольно весело. Напоминает мне загадку, которую я сделал много лет назад, чтобы вычислить то, что называется цифрой с удаленным простым числом . Это простое число, которое, если вы удалите любую цифру, то оставшееся число все еще будет простым. Например, 1037 - простое число с удаленной цифрой, потому что 1037, 037, 137, 107 и 103 - простые. Я нашел один из 84 цифр в длину, и самый длинный, который я знаю, это 332 цифры в длину. Я уверен, что мы могли бы найти один гораздо дольше с методами, используемыми для этой головоломки. (Но выбор пробных номеров немного сложнее, может быть?)
источник
Аксиома, 3019 цифр {318} 5 {2700}
результат от начального значения 3000 за 529 с
источник