Введение / История
В недавней дискуссии в крипто-чате мне было предложено обсудить / помочь с тестом примитивности Ферма и числами Кармайкла. Этот тест основан на предпосылке, a^(p-1) mod p==1
которая всегда будет выполняться для простых чисел p
, но не всегда для композитов. В настоящее время ряд Кармайкл, по существу тест злейший враг Ферма: Номер , для которого вы должны выбрать , a
чтобы быть не совместно с премьер p
получить a^(p-1) mod p!=1
. Теперь, если a
не взаимно простое число, вы, по существу, нашли нетривиальный факторp
и как мы все знаем, факторинг может быть довольно сложным. Особенно если все факторы достаточно велики. Теперь вы можете понять, почему тест Ферма не используется на практике так часто (ну, есть лучшие алгоритмы), потому что есть числа, для которых вам, как защитнику (с точки зрения безопасности), придется выполнить такой же объем работы, как атакующий (а именно фактор числа).
Итак, теперь, когда мы знаем, почему эти числа несколько интересны, мы сгенерируем их как можно быстрее, поэтому мы можем просто запомнить генерирующий код, если он нам понадобится!
Числа Кармайкла также известны как A002997 в OEIS .
Уже есть связанная проблема , но записи оттуда не конкурентоспособны, потому что они оптимизированы для скорости, а не для размера. Тот же аргумент верен и в обратном направлении: записи здесь, скорее всего, сделают компромисс против скорости в пользу размера.
Спецификация
вход
Это стандарт последовательностьвызов, поэтому вы берете положительное или неотрицательное целое число в n
качестве входных данных. n
может быть 0- или 1-индексирован, как вы предпочитаете (пожалуйста, укажите).
Вывод
По вашему выбору вы получите либо n
число с номером 1, либо число с n
номером 1, которое вы предпочитаете (укажите).
Спецификация
Целое число x
является числом Кармайкл тогда и только тогда x
является составным и для всех целых чисел y
с gcd(x,y)=1
, он считает , что y^(x-1) mod x==1
.
Кто выигрывает?
Это Код-гольфтак что самый короткий код в байтах побеждает!
Применяются стандартные правила ввода-вывода и лазейки.
Тестовые случаи
Первые несколько чисел Кармайкла:
561,1105,1729,2465,2821,6601,8911,10585,15841,
29341,41041,46657,52633,62745,63973,75361,101101,
115921,126217,162401,172081,188461,252601,278545,
294409,314821,334153,340561,399001,410041,449065,
488881,512461
источник
Python 2 , 92 байта
Попробуйте онлайн!
1-индексированный и медленный, как патока.
В понимании списка я использую метод Денниса для генерации всех целых чисел, взаимно простых с
n
(n- тативами ), а затем вычисляюx**~-n%n
все из них. Давайте назовем этот списокL
.Чтобы определить число Кармайкла, я сравниваю этот список лексикографически со списком, состоящим из
n-1
единиц. Почему это работает?Каждый элемент
L
является положительным целым числом:(k/n)
взаимно простn
, так(k/n)**~-n
же, как и так(k/n)**~-n%n > 0
. Таким образом, единственно возможные значенияL
этого лексикографически меньше, чем[1]*(n-1)
те, которые полностью состоят из меньшихn-1
единиц. (L
Не может содержать более чемn-1
значения, так какn
не может быть больше , чемn-1
totatives! Так что сравнение нравится[1,1,1,1,3] < [1,1,1,1]
вне.)Проверка того, что в
n-1
записи меньше записей,L
гарантирует, чтоn
она составная. (Наличиеn-1
атрибутов эквивалентно условию первичности.) И затем, условием для того, чтобы быть числом Кармайкла, является то, что каждый элементL
равен1
. Так что это лексикографическое сравнение обнаруживает именно то,L
что нас интересует.Мистер Xcoder сохранил байт, переключившись на рекурсивную лямбда-форму:
j
отсчитывает каждый раз, когда мы нажимаем число Кармайкла, иn
подсчитывает каждый раз, когда мы повторяем. Так что, как толькоj
достигнет нуля, будетn-1
равенoriginal_value_of_j
ому числу Кармайкла.источник
Желе ,
1211 байт-1 байт благодаря милям и г-ну Xcoder (использование атома функции Кармайкла и его игры в гольф)
Монадическая ссылка, получающая
n
и возвращающая список первыхn
чисел Кармайкла.Попробуйте онлайн!
Как?
Как и предыдущий (ниже), за исключением того, что есть встроенная функция Кармайкла - которая дает наименьшую мощность, такую, что входной сигнал, поднятый в эту степень, конгруэнтен одному модулю этой степени для всех целых чисел, взаимно простых с этим целым числом. Таким образом, мы можем исключить ложноположительные значения (простые числа) в меньшем количестве байтов и иметь более быстрый код!
Предыдущие 12 байтов :
Попробуйте онлайн! (Да, это время ожидания
n=3
).Как?
Число
c
- это число Кармайкла, если оно составное, и верно, что любое целое числоx
, возведенное вc
, конгруэнтно поx
модулюc
.Нам нужно только , чтобы проверить это для положительного
x
доx=c
себя.Также обратите внимание, что при
x=c
проверке выясняется, соответствует лиx
возведенное в степеньx
поx
модулюx
, что верно, поэтому нам не нужно проверять это (это делает для более короткого кода).источник
ECMAScript Regex,
8689 байтПредупреждение: не читайте это, если вы не хотите, чтобы какая-то магия унарного выражения была испорчена для вас. Если вы действительно хотите сами разобраться с этой магией, я настоятельно рекомендую начать с решения некоторых проблем в регулярном выражении ECMAScript: см. Этот предыдущий пост, где приведен список последовательно рекомендованных спойлеровских проблем, решаемых по одному.
^(?!(x(x+))(?!\2*$)\1*(?=\1$)(?!(xx+)\3+$))((?=(xx+?)\5*$)(?=(x+)(\6+$))\7(?!\5*$)){2,}x$
Попробуйте онлайн!
Основная магия этого регулярного выражения в той части, которая утверждает, что все простые факторы N имеют ровно одну кратность. Это тот же трюк, который используется моими строками Match, длина которых равна четвертой степени и регулярным выражениям Find the Smoothest Number : повторное неявное деление на наименьший простой множитель.
Также возможно непосредственно проверить, что N не имеет факторов идеального квадрата (то есть, что N не имеет квадратов). При этом используется вариант алгоритма умножения, кратко описанного в параграфе моего регулярного выражения для чисел, чтобы проверить, является ли число идеальным квадратом. Это спойлер . Так что не читайте дальше, если вы не хотите, чтобы какая-то продвинутая магия унарных регулярных выражений была испорчена для вас . Если вы действительно хотите сами разобраться в этой магии, я настоятельно рекомендую начать с решения некоторых проблем в списке последовательно рекомендованных проблем со спойлером в этом предыдущем посте и попытаться найти математическое понимание самостоятельно.
Однако использование этого алгоритма для решения этой проблемы не дает никаких преимуществ. Это приводит к более медленному регулярному выражению, с большим размером 97 байтов. Без теста на простоту множественности (который в одном цикле утверждает, что существует как минимум 2 простых множителя и что каждый из них имеет одинарную множественность), мы должны отдельно утверждать, что N является составным.
Попробуйте онлайн!
источник
decision-problem
ответ, но задача - этоsequence
вызов.) Предположительно, в более мощном варианте регулярных выражений будет более прямой тест на наличие квадратных делителей?^(?!(x(x+))(?!\2*$)\1*(?=\1$)(?!(xx+)\3+$)|((^x|xx\5){2,})\4*$)(xx+)\6+$
или, возможно, даже до 72 байтов.J ,
725951 байтПопробуйте онлайн!
источник
Сетчатка , 94 байта
Попробуйте онлайн! 1-индексироваться. Не быстро, поэтому будет время ожидания
n>5
на TIO. Объяснение:Увеличить текущее значение. При первом проходе это также удаляет
n
из буфера вывода (но$+
все еще может получить к нему доступ).Проверьте, является ли текущее значение числом Кармайкла. При этом используется альтернативный алгоритм @ Deadcode, так как определение квадрата короче при написании с использованием регулярных выражений .NET / Perl / PCRE.
Повторяйте, пока текущее значение не станет числом Кармайкла.
Увеличить текущее значение.
Повторите начальный шаг и выше времени цикла
n
.Преобразовать результат в десятичную.
источник
Haskell , 95 байт
Попробуйте онлайн!
Degolfed:
источник