Wstęp / Tło

W niedawnej dyskusji w tym krypto czat I została zakwestionowana, aby omówić / pomoc z Test pierwszości Fermata i numery Carmichael. Ten test opiera się na założeniu, że a^(p-1) mod p==1zawsze będzie dotyczyć liczb pierwszych p, ale nie zawsze kompozytów. Teraz liczba Carmichael jest zasadniczo Fermata Test najgorszym wrogiem: Number, dla którego trzeba wybrać asię nie współ-prime z pdostać a^(p-1) mod p!=1. Teraz, jeśli anie jest to co-prime, w zasadzie znalazłeś nietrywialny czynnikpi jak wszyscy wiemy faktoring może być dość trudny. Zwłaszcza jeśli wszystkie czynniki są wystarczająco duże. Teraz możesz sobie uświadomić, dlaczego test Fermata nie jest tak często wykorzystywany w praktyce (istnieją lepsze algorytmy), ponieważ istnieją liczby, dla których jako obrońca (pod względem bezpieczeństwa) musiałbyś wykonać podobną pracę jak atakujący (mianowicie współczynnik liczby).

Teraz, gdy wiemy, dlaczego te liczby są nieco fascynujące, wygenerujemy je w możliwie najkrótszy sposób, abyśmy mogli zapamiętać kod generujący, jeśli kiedykolwiek będziemy go potrzebować!

Numery Carmichael są również znane jako A002997 w OEIS .
Istnieje już pokrewne wyzwanie , ale stamtąd zgłoszenia nie są tutaj konkurencyjne, ponieważ są zoptymalizowane pod kątem szybkości, a nie wielkości. Ten sam argument dotyczy odwrotnego kierunku, wpisy tutaj prawdopodobnie będą kompromisowe względem prędkości na korzyść wielkości.

Specyfikacja

Wejście

To jest standard sekwencjawyzwanie, więc bierzesz dodatnią lub nieujemną liczbę całkowitą njako dane wejściowe. nmogą być indeksowane 0 lub 1 według własnego uznania (proszę wskazać).

Wynik

Twój wynik będzie albo n-tym numerem karmyela, albo pierwszymi nliczbami carmichaela, jak wolisz (proszę wskazać).

Specyfikacja

Liczba całkowita xjest liczbą Carmichaela wtedy i tylko wtedy, gdy xjest złożona i dla wszystkich liczb całkowitych yz gcd(x,y)=1nią, to ją trzyma y^(x-1) mod x==1.

Kto wygrywa?

To jest golf-golf, więc wygrywa najkrótszy kod w bajcie!
Obowiązują standardowe zasady IO i luki.

Przypadki testowe

Pierwsze kilka liczb Carmichael to:

 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

Mathematica, 71 bajtów

(t=s=1;While[t<=#,If[++s~Mod~CarmichaelLambda@s==1&&!PrimeQ@s,t++]];s)&  

Wypróbuj online!

50->1461241 Wypróbuj online!

Python 2 , 92 bajty

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

Wypróbuj online!

1-indeksowany i wolny jak melasa.

W interpretacji listy używam metody Dennisa do generowania wszystkich liczb całkowitych don ( sumy n ), a następnie obliczam x**~-n%ndla nich wszystkich. Nazwijmy tę listę L.

Aby wykryć liczbę Carmichaela, porównuję leksykograficznie tę listę z listą składającą się zn-1 nich. Dlaczego to działa?

Każdy element Ljest dodatnią liczbą całkowitą: (k/n)jest chroniony prawem autorskim n, więc (k/n)**~-nrównież jest (k/n)**~-n%n > 0. Zatem jedynymi możliwymi wartościami, Lktóre są leksykograficznie mniejsze niż [1]*(n-1) te składające się całkowicie z mniej niż n-1 jedności. ( Lnie może zawierać więcej niż n-1wartości, ponieważ nnie może zawierać więcej niż n-1sumy! Tak więc podobne porównania [1,1,1,1,3] < [1,1,1,1]są niedostępne).

Sprawdzanie, czy jest mniej niż n-1wpisów, Lzapewnia, że njest złożony. (Posiadanie n-1sumy jest równoznaczne z pierwotnością.) A zatem warunkiem bycia liczbą Carmichaela jest dokładnie to, że każdy element Ljest równy 1. To porównanie leksykograficzne wykrywa dokładnie te, Lktórymi jesteśmy zainteresowani.

Pan Xcoder uratował bajt, przechodząc na rekurencyjną formę lambda: jodlicza za każdym razem, gdy trafimy na liczbę Carmichaela, i nodlicza za każdym razem, gdy się powtarzamy. Kiedy raz josiągnie zero, n-1równa się original_value_of_jliczbie Carmichaela.

Galaretka ,  12  11 bajtów

-1 bajt dzięki mile i Mr. Xcoder (użycie atomu Carmichaela i jego golfa)

%Æc’=ÆP
⁹Ç#

Monadyczny link pobierający ni zwracający listę pierwszych nliczb Carmichaela.

Wypróbuj online!

W jaki sposób?

Podobnie jak poprzedni (poniżej), z wyjątkiem tego, że jest wbudowana funkcja Carmichaela - która daje najmniejszą moc, tak że dane wejściowe podniesione do tej mocy są zgodne z jednym modułem tej mocy dla wszystkich liczb całkowitych pierwotnych do tej liczby całkowitej. Dlatego możemy wykluczyć fałszywe alarmy (liczby pierwsze) w mniejszej liczbie bajtów i mieć szybszy kod!

%Æ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

Poprzednie 12 bajtów :

Ṗ*%⁼Ṗ_ÆP
⁹Ç#

Wypróbuj online! (Tak, kończy się czas n=3).

W jaki sposób?

Liczba, cjest liczbą Carmichaela, jeśli jest złożona i prawdą jest, że każda liczba całkowita x, podniesiona do, cjest zgodna z xmodulo c.

Musimy tylko sprawdzić to na pozytywne xprzygotowań do x=csiebie.

Zauważ też, że przy x=csprawdzaniu jest sprawdzane, czy xpodniesione do potęgi xjest zgodne z xmodulo x, co jest prawdą - więc nie musimy tego sprawdzać (powoduje to krótszy kod).

Ṗ*%⁼Ṗ_Æ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

ECMAScript Regex, 86 89 bajtów

Ostrzeżenie: Nie czytaj tego, jeśli nie chcesz, aby zepsuta została dla ciebie jedna magia wyrażeń regularnych. Jeśli chcesz spróbować samodzielnie odkryć tę magię, zdecydowanie polecam zacząć od rozwiązania niektórych problemów w wyrażeniu regularnym ECMAScript: zapoznaj się z tym wcześniejszym postem, aby uzyskać listę zalecanych problemów oznaczonych spoilerem do rozwiązania jeden po drugim.

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

Wypróbuj online!

# 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$

Główna magia tego wyrażenia regularnego polega na tym, że wszystkie czynniki pierwsze N ​​mają dokładnie jedną wielokrotność. Jest to ta sama sztuczka, której używa moja ciągi dopasowania, których długość jest czwartą potęgą, i odnajdujemy wyrażenia regularne o naj płynniejszej liczbie : powtarzane niejawne dzielenie przez najmniejszy czynnik pierwszy.

Możliwe jest również bezpośrednie sprawdzenie, czy N nie ma czynników idealnie kwadratowych (tzn. Że N nie zawiera kwadratów). Wykorzystuje to wariant algorytmu mnożenia, krótko opisany w akapicie mojego obfitego wyrażenia regularnego, aby sprawdzić, czy liczba jest kwadratem idealnym. To jest spoiler . Więc nie czytaj dalej, jeśli nie chcesz, aby zepsuta Ci była jakaś zaawansowana magia wyrażeń regularnych . Jeśli chcesz spróbować samemu odkryć tę magię, zdecydowanie polecam zacząć od rozwiązania niektórych problemów z listy zalecanych problemów oznaczonych spoilerem w tym wcześniejszym poście i samodzielnego wymyślenia matematycznych spostrzeżeń.

Zastosowanie tego algorytmu w przypadku tego problemu nie zapewnia jednak żadnych korzyści. Powoduje to wolniejsze wyrażenie regularne o większym rozmiarze 97 bajtów. Bez testu pierwotnej wielokrotności (który w jednej pętli stwierdza oba, że ​​istnieją co najmniej 2 czynniki pierwsze i że każdy z nich ma pojedynczą wielokrotność), musimy osobno stwierdzić, że N jest złożona.

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

Wypróbuj online!

 ^
 (?!
     # 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
 

J , 72 59 51 bajtów

1{(((0>.-)0&p:*~:@q:-:0=q:|&<:])([,(+*)~)])/^:_@,&2

Wypróbuj online!

Siatkówka , 94 bajty

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

Wypróbuj online! 1-indeksowany. Nie szybko, więc upłynie czas n>5na TIO. Wyjaśnienie:

\d*$
x

Zwiększ bieżącą wartość. Przy pierwszym przejściu powoduje to również usunięcie nbufora wyjściowego (ale $+nadal można uzyskać do niego dostęp).

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

Sprawdź, czy bieżącą wartością jest liczba Carmichaela. Wykorzystuje alternatywny algorytm @ Deadcode, ponieważ wykrywanie kwadratu jest krótsze, gdy jest napisane przy użyciu wyrażenia regularnego .NET / Perl / PCRE.

^+`

Powtarzaj, aż bieżącą wartością będzie liczba Carmichael.

$
x

Zwiększ bieżącą wartość.

"$+"}

Powtórz początkowy przyrost i powyższe nczasy pętli .

x

Konwertuj wynik na dziesiętny.

Haskell , 95 bajtów

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

Wypróbuj online!

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