Гольф псевдопраймы!

9

Введение / История

В недавней дискуссии в крипто-чате мне было предложено обсудить / помочь с тестом примитивности Ферма и числами Кармайкла. Этот тест основан на предпосылке, 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
SEJPM
источник

Ответы:

6

Python 2 , 92 байта

f=lambda j,n=1:j and f(j-([(k/n)**~-n%n for k in range(n*n)if k/n*k%n==1]<[1]*~-n),n+1)or~-n

Попробуйте онлайн!

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-1totatives! Так что сравнение нравится [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ому числу Кармайкла.

Линн
источник
5

Желе ,  12  11 байт

-1 байт благодаря милям и г-ну Xcoder (использование атома функции Кармайкла и его игры в гольф)

%Æc’=ÆP
⁹Ç#

Монадическая ссылка, получающая nи возвращающая список первых nчисел Кармайкла.

Попробуйте онлайн!

Как?

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

%Æc’⁼ÆP - isCarmichael: number, n (any integer)
 Æc     - Carmicael function of n
%       - n modulo that
   ’    - decremented (0 for Carmichael numbers and primes)
     ÆP - is n prime? (1 for primes 0 otherwise)
    ⁼   - equal?

⁹Ç# - Main link: number, n
  # - count up finding the first n values satisfying:
 Ç  - ...condition: call the last link as a monad
⁹   - ...starting with a value of: literal 256

Предыдущие 12 байтов :

Ṗ*%⁼Ṗ_ÆP
⁹Ç#

Попробуйте онлайн! (Да, это время ожидания n=3).

Как?

Число c- это число Кармайкла, если оно составное, и верно, что любое целое число x, возведенное в c, конгруэнтно по xмодулю c.

Нам нужно только , чтобы проверить это для положительного xдо x=cсебя.

Также обратите внимание, что при x=cпроверке выясняется, соответствует ли xвозведенное в степень xпо xмодулю x, что верно, поэтому нам не нужно проверять это (это делает для более короткого кода).

Ṗ*%⁼Ṗ_ÆP - Link 1, isCarmichaelNumber: integer c (greater than 1)
Ṗ        - pop c (uses the implicit range(c)) = [1, 2, 3, ..., c-1]
 *       - raise to the power of c (vectorises) = [1^c, 2^c, 3^c, ..., (c-1)^c]
  %      - modulo by c (vectorises) = [1^c%c, 2^c%c, 3^c%c, ..., (c-1)^c%c]
    Ṗ    - pop c = [1, 2, 3, ..., c-1]
   ⁼     - equal? (non-vectorising) = 1 if so, 0 if not
      ÆP - isPrime?(c) = 1 if so, 0 if not
     _   - subtract = 1 if Carmichael 0 if not
         -     (Note the caveat that c must be an integer greater than 1, this is because
         -      popping 1 yields [] thus the equality check will hold; same for 0,-1,...)

⁹Ç# - Main link: number, n
  # - count up finding the first n values satisfying:
 Ç  - ...condition: call the last link as a monad
⁹   - ...starting with a value of: literal 256
Джонатан Аллан
источник
Также 12 байтов, но вычисляет первые 33 за минуту, используя атом Кармайкла.
мили
11 байт с помощью встроенной функции Carmichael.
г-н Xcoder
@ Mr.Xcoder Я собирался предложить мили, размещенные отдельно, потом увидел ваши, потом увидел ваш комментарий и удалил. Это может быть связано с тем, что кто-то считает, что он слишком похож на комментарий, который комментирует мили, а не на этот, но я думаю, что даже это странная причина, поскольку нет оснований думать, что вы не нашли то же самое независимо (я знаю, что мы делали такие вещи много раз). Я выложу ваши 11, если хотите, но я придерживаюсь мнения, что вы или мили должны взять на себя ответственность
Джонатан Аллан
@ тоже миль ... ^
Джонатан Аллан
@JonathanAllan Просто отправь это сам. Упомяните мили »и мой вклад, и я тоже не думаю, что мили миль :-) (Кстати, я даже не видел комментарий миль: - / до публикации своего ответа)
Мистер Xcoder
2

ECMAScript Regex, 86 89 байт

Предупреждение: не читайте это, если вы не хотите, чтобы какая-то магия унарного выражения была испорчена для вас. Если вы действительно хотите сами разобраться с этой магией, я настоятельно рекомендую начать с решения некоторых проблем в регулярном выражении ECMAScript: см. Этот предыдущий пост, где приведен список последовательно рекомендованных спойлеровских проблем, решаемых по одному.

^(?!(x(x+))(?!\2*$)\1*(?=\1$)(?!(xx+)\3+$))((?=(xx+?)\5*$)(?=(x+)(\6+$))\7(?!\5*$)){2,}x$

Попробуйте онлайн!

# Match Carmichael numbers in the domain ^x*$ using Korselt's criterion
# N = input number (initial value of tail)
^
(?!
    # Iterate through factors \1, with \2 = \1-1, for which \2 does not divide into N-1
    (x(x+))
    (?!\2*$)           # Assert N-1 is not divisible by \2
    \1*(?=\1$)         # Assert N is divisible by \1; tail = \1
    # If the factor \1, which already passed the aboved tests, is prime, then fail the
    # outside negative lookahead, because N is not a Carmichael number.
    (?!(xx+)\3+$)
)
# Assert that N has at least 2 unique prime factors, and that all of its prime factors
# are of exactly single multiplicity (i.e. that N is square-free).
(
    (?=(xx+?)\5*$)     # \5 = smallest prime factor of tail
    (?=(x+)(\6+$))     # \6 = tail / \5 (implicitly); \7 = tool to make tail = \6
    \7                 # tail = \6
    (?!\5*$)           # Assert that tail is no longer divisible by \5, i.e. that that
                       # prime factor was of exactly single multiplicity.
){2,}
x$

Основная магия этого регулярного выражения в той части, которая утверждает, что все простые факторы N имеют ровно одну кратность. Это тот же трюк, который используется моими строками Match, длина которых равна четвертой степени и регулярным выражениям Find the Smoothest Number : повторное неявное деление на наименьший простой множитель.

Также возможно непосредственно проверить, что N не имеет факторов идеального квадрата (то есть, что N не имеет квадратов). При этом используется вариант алгоритма умножения, кратко описанного в параграфе моего регулярного выражения для чисел, чтобы проверить, является ли число идеальным квадратом. Это спойлер . Так что не читайте дальше, если вы не хотите, чтобы какая-то продвинутая магия унарных регулярных выражений была испорчена для вас . Если вы действительно хотите сами разобраться в этой магии, я настоятельно рекомендую начать с решения некоторых проблем в списке последовательно рекомендованных проблем со спойлером в этом предыдущем посте и попытаться найти математическое понимание самостоятельно.

Однако использование этого алгоритма для решения этой проблемы не дает никаких преимуществ. Это приводит к более медленному регулярному выражению, с большим размером 97 байтов. Без теста на простоту множественности (который в одном цикле утверждает, что существует как минимум 2 простых множителя и что каждый из них имеет одинарную множественность), мы должны отдельно утверждать, что N является составным.

^(?!(x(x+))(?!\2*$)\1*(?=\1$)(?!(xx+)\3+$)|((xx+)\5*(?=\5$))?(x(x*))(?=(\6*)\7+$)\6*$\8)(xx+)\9+$

Попробуйте онлайн!


 ^
 (?!
     # Iterate through factors \1, with \2 = \1-1, for which \2 does not divide into N-1
     (x(x+))
     (?!\2*$)           # Assert N-1 is not divisible by \2
     \1*(?=\1$)         # Assert N is divisible by \1; tail = \1
     # If the factor \1, which already passed the aboved tests, is prime, then fail the
     # outside negative lookahead, because N is not a Carmichael number.
     (?!(xx+)\3+$)
 |
 # Assert that N is square-free, i.e. has no divisor >1 that is a perfect square.
     ((xx+)\5*(?=\5$))?  # cycle tail through all of the divisors of N, including N itself
     # Match iff tail is a perfect square
     (x(x*))             # \6 = potential square root; \7 = \6 - 1
     (?=
         (\6*)\7+$       # iff \6 * \6 == our number, then the first match here must result in \8 == 0
     )
     \6*$\8              # test for divisibility by \6 and for \8 == 0 simultaneously
 )
 (xx+)\9+$               # Assert that N is composite
 

Deadcode
источник
2
(Строго говоря, это decision-problemответ, но задача - это sequenceвызов.) Предположительно, в более мощном варианте регулярных выражений будет более прямой тест на наличие квадратных делителей?
Нил
@Neil Вы правы, я могу сыграть в гольф, напрямую проверяя квадратные делители. В ECMA никаких дополнительных функций не требуется. Но это сделает его намного медленнее (и я также хочу скрыть его под тегом спойлера). Я хочу включить обе версии, я думаю.
Deadcode
Да, очень раздражает нахождение вопросов для регулярных выражений, которые я уже написал, которые не являются правильным выбором. Должен ли я удалить свой ответ?
Deadcode
@Neil Вот, пожалуйста. Я реализовал алгоритм, используя вашу идею. Вероятно, поэтому я и не думал заниматься этим самостоятельно; на самом деле это приводит к более длинному регулярному выражению, потому что необходим is-составной тест.
Deadcode
(В соответствии с правилами сайта вы должны удалить свой ответ, да.) Моя идея заключалась в том, что, используя дополнительные функции, скажем, регулярных выражений Retina, вы можете уменьшить его до ^(?!(x(x+))(?!\2*$)\1*(?=\1$)(?!(xx+)\3+$)|((^x|xx\5){2,})\4*$)(xx+)\6+$или, возможно, даже до 72 байтов.
Нил
1

Сетчатка , 94 байта

\d*$
x
"$+"}/^(?!(x(x+))(?!\2*$)\1*(?=\1$)(?!(xx+)\3+$)|((^x|xx\5){2,})\4*$)(xx+)\6+$/^+`$
x
x

Попробуйте онлайн! 1-индексироваться. Не быстро, поэтому будет время ожидания n>5на TIO. Объяснение:

\d*$
x

Увеличить текущее значение. При первом проходе это также удаляет nиз буфера вывода (но $+все еще может получить к нему доступ).

/^(?!(x(x+))(?!\2*$)\1*(?=\1$)(?!(xx+)\3+$)|((^x|xx\5){2,})\4*$)(xx+)\6+$/

Проверьте, является ли текущее значение числом Кармайкла. При этом используется альтернативный алгоритм @ Deadcode, так как определение квадрата короче при написании с использованием регулярных выражений .NET / Perl / PCRE.

^+`

Повторяйте, пока текущее значение не станет числом Кармайкла.

$
x

Увеличить текущее значение.

"$+"}

Повторите начальный шаг и выше времени цикла n.

x

Преобразовать результат в десятичную.

Нил
источник
0

Haskell , 95 байт

s=filter
c n=s(\x->let l=s((1==).gcd x)f;f=[1..x-1]in l/=f&&all(\y->y^(x-1)`mod`x==1)l)[1..]!!n

Попробуйте онлайн!

Degolfed:

-- function to filter out Carmichael numbers
filterFunction x = 
    let coprimes = filter ((1 ==) . gcd x) lesserNumbers
        lesserNumbers = [1 .. x - 1]
    in
        -- the number x is Carmichael if it is not prime
        lesserNumbers /= coprimes && 
            -- and all of its coprimes satisfy the equation
            all (\y -> y ^ (x - 1) `mod` x == 1) coprimes

-- get n'th Carmichael number (zero-based)
c n = filter filterFunction [1..] !! n
Макс ехлаков
источник