Pseudopierwsze gry w golfa!

9

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 wyzwanie, 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 , 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
SEJPM
źródło

Odpowiedzi:

8

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!

J42161217
źródło
4
Mathematica jest teraz na TiO, więc jeśli ktoś jest zainteresowany, możesz spróbować online!
Pan Xcoder,
@ Mr.Xcoder Hej! To świetnie! Dodałem (moją pierwszą) matematykę TIO
J42161217
6

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.

Lynn
źródło
5

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
Jonathan Allan
źródło
Również 12 bajtów, ale oblicza pierwsze 33 w niecałą minutę za pomocą atomu Carmichaela.
mile
11 bajtów za pomocą wbudowanej funkcji Carmichael.
Pan Xcoder,
@ Mr.Xcoder Miałem zasugerować mile opublikowane osobno, potem zobaczyłem twój, potem zobaczyłem twój komentarz i usunąłem. DV może być dlatego, że ktoś uważa, że ​​jest zbyt podobny do komentowanego przez mile, a nie ten, ale myślę, że nawet to jest dziwny powód, ponieważ nie ma powodu, aby sądzić, że nie znalazłeś tego samego niezależnie (wiem, że ja) robiliśmy takie rzeczy wiele razy). Wyślę twoje 11, jeśli chcesz, ale jestem zdania, że ​​ty lub mile powinieneś wziąć kredyt.
Jonathan Allan
@miles too ... ^
Jonathan Allan
@JonathanAllan Po prostu opublikuj to sam. Wspomnij o milach i moim wkładzie, i nie sądzę, żeby mile też miały na myśli :-) (BTW, nawet nie widziałem komentarza mil: - / przed opublikowaniem mojej odpowiedzi)
Pan Xcoder,
2

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
 

Deadcode
źródło
2
(Ściśle mówiąc, to jest decision-problemodpowiedź, ale wyzwanie jest sequencewyzwaniem.) Prawdopodobnie w bardziej wydajnym wariancie wyrażenia regularnego dostępny byłby bardziej bezpośredni test na dzielniki kwadratowe?
Neil
@Neil Masz rację, mogę zagrać w golfa, bezpośrednio testując dzielniki kwadratowe. W ECMA nie są wymagane żadne dodatkowe funkcje. Ale to sprawi, że będzie o wiele wolniejszy (i chcę też ukryć go pod tagiem spoilera). Myślę, że chcę uwzględnić obie wersje.
Deadcode
Tak, bardzo denerwujące jest znajdowanie pytań o wyrażenia regularne, które już napisałem, które nie są właściwym rodzajem wyzwania. Czy powinienem usunąć swoją odpowiedź?
Deadcode
@Neil Proszę bardzo. Zaimplementowałem algorytm używając twojego pomysłu. Prawdopodobnie właśnie dlatego nie pomyślałem o tym, żeby to zrobić sam; w rzeczywistości skutkuje dłuższym wyrażeniem regularnym, ponieważ potrzebny jest test is-composite.
Deadcode
(Zgodnie z regułami witryny powinieneś usunąć swoją odpowiedź, tak.) Mój pomysł polegał na tym, że używając dodatkowych funkcji, powiedzmy, wyrażeń regularnych Retina, możesz zagrać w golfa do ^(?!(x(x+))(?!\2*$)\1*(?=\1$)(?!(xx+)\3+$)|((^x|xx\5){2,})\4*$)(xx+)\6+$, a może nawet mniej niż 72 bajtów.
Neil
1

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.

Neil
źródło
0

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
Max Yekhlakov
źródło