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==1
zawsze 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ć a
się nie współ-prime z p
dostać a^(p-1) mod p!=1
. Teraz, jeśli a
nie jest to co-prime, w zasadzie znalazłeś nietrywialny czynnikp
i 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ą n
jako dane wejściowe. n
mogą 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 n
liczbami carmichaela, jak wolisz (proszę wskazać).
Specyfikacja
Liczba całkowita x
jest liczbą Carmichaela wtedy i tylko wtedy, gdy x
jest złożona i dla wszystkich liczb całkowitych y
z gcd(x,y)=1
nią, 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
źródło
Python 2 , 92 bajty
Wypróbuj online!
1-indeksowany i wolny jak melasa.
W interpretacji listy używam metody Dennisa do generowania wszystkich liczb całkowitych do
n
( sumy n ), a następnie obliczamx**~-n%n
dla nich wszystkich. Nazwijmy tę listęL
.Aby wykryć liczbę Carmichaela, porównuję leksykograficznie tę listę z listą składającą się z
n-1
nich. Dlaczego to działa?Każdy element
L
jest dodatnią liczbą całkowitą:(k/n)
jest chroniony prawem autorskimn
, więc(k/n)**~-n
również jest(k/n)**~-n%n > 0
. Zatem jedynymi możliwymi wartościami,L
które są leksykograficznie mniejsze niż[1]*(n-1)
te składające się całkowicie z mniej niżn-1
jedności. (L
nie może zawierać więcej niżn-1
wartości, ponieważn
nie może zawierać więcej niżn-1
sumy! Tak więc podobne porównania[1,1,1,1,3] < [1,1,1,1]
są niedostępne).Sprawdzanie, czy jest mniej niż
n-1
wpisów,L
zapewnia, żen
jest złożony. (Posiadanien-1
sumy jest równoznaczne z pierwotnością.) A zatem warunkiem bycia liczbą Carmichaela jest dokładnie to, że każdy elementL
jest równy1
. To porównanie leksykograficzne wykrywa dokładnie te,L
którymi jesteśmy zainteresowani.Pan Xcoder uratował bajt, przechodząc na rekurencyjną formę lambda:
j
odlicza za każdym razem, gdy trafimy na liczbę Carmichaela, in
odlicza za każdym razem, gdy się powtarzamy. Kiedy razj
osiągnie zero,n-1
równa sięoriginal_value_of_j
liczbie Carmichaela.źródło
Galaretka ,
1211 bajtów-1 bajt dzięki mile i Mr. Xcoder (użycie atomu Carmichaela i jego golfa)
Monadyczny link pobierający
n
i zwracający listę pierwszychn
liczb 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!
Poprzednie 12 bajtów :
Wypróbuj online! (Tak, kończy się czas
n=3
).W jaki sposób?
Liczba,
c
jest liczbą Carmichaela, jeśli jest złożona i prawdą jest, że każda liczba całkowitax
, podniesiona do,c
jest zgodna zx
moduloc
.Musimy tylko sprawdzić to na pozytywne
x
przygotowań dox=c
siebie.Zauważ też, że przy
x=c
sprawdzaniu jest sprawdzane, czyx
podniesione do potęgix
jest zgodne zx
modulox
, co jest prawdą - więc nie musimy tego sprawdzać (powoduje to krótszy kod).źródło
ECMAScript Regex,
8689 bajtówOstrzeż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!
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.
Wypróbuj online!
źródło
decision-problem
odpowiedź, ale wyzwanie jestsequence
wyzwaniem.) Prawdopodobnie w bardziej wydajnym wariancie wyrażenia regularnego dostępny byłby bardziej bezpośredni test na dzielniki kwadratowe?^(?!(x(x+))(?!\2*$)\1*(?=\1$)(?!(xx+)\3+$)|((^x|xx\5){2,})\4*$)(xx+)\6+$
, a może nawet mniej niż 72 bajtów.J ,
725951 bajtówWypróbuj online!
źródło
Siatkówka , 94 bajty
Wypróbuj online! 1-indeksowany. Nie szybko, więc upłynie czas
n>5
na TIO. Wyjaśnienie:Zwiększ bieżącą wartość. Przy pierwszym przejściu powoduje to również usunięcie
n
bufora wyjściowego (ale$+
nadal można uzyskać do niego dostęp).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.
Zwiększ bieżącą wartość.
Powtórz początkowy przyrost i powyższe
n
czasy pętli .Konwertuj wynik na dziesiętny.
źródło
Haskell , 95 bajtów
Wypróbuj online!
Degolfed:
źródło