Biorąc pod uwagę nieujemną liczbę całkowitą N, wyprowadza najmniejszą nieparzystą liczbę całkowitą dodatnią, która jest silnym pseudopierwszym znakiem dla wszystkich pierwszychN liczb .

Jest to sekwencja OEIS A014233 .

Przypadki testowe (z jednym indeksem)

1       2047
2       1373653
3       25326001
4       3215031751
5       2152302898747
6       3474749660383
7       341550071728321
8       341550071728321
9       3825123056546413051
10      3825123056546413051
11      3825123056546413051
12      318665857834031151167461
13      3317044064679887385961981

Przypadki testowe dla N > 13nie są dostępne, ponieważ te wartości nie zostały jeszcze znalezione. Jeśli uda Ci się znaleźć kolejne terminy w sekwencji, koniecznie prześlij je do OEIS!

Zasady

• Możesz wybrać Nwartość zerową lub jedną indeksowaną.
• Dopuszczalne jest, aby twoje rozwiązanie działało tylko dla wartości reprezentatywnych w zakresie liczb całkowitych twojego języka (tak więc N = 12dla niepodpisanych liczb całkowitych 64-bitowych), ale twoje rozwiązanie musi teoretycznie działać dla każdego wejścia, przy założeniu, że twój język obsługuje liczby całkowite o dowolnej długości.

tło

Każda dodatnia parzysta liczba całkowita xmoże być zapisana w postaci, w x = d*2^sktórej djest nieparzysta. di smożna go obliczyć przez wielokrotne dzielenie nprzez 2, aż iloraz nie będzie już podzielny przez 2. dto ostateczny iloraz i sjest to liczba razy 2 dzielenian .

Jeśli liczba całkowita dodatnia njest liczbą pierwszą, to małe twierdzenie Fermata głosi:

W dowolnym polu skończonym Z/pZ (gdzie pjest liczba pierwsza) jedynymi pierwiastkami kwadratowymi 1są 1i -1(lub równoważnie 1i p-1).

Możemy użyć tych trzech faktów, aby udowodnić, że jedno z dwóch poniższych stwierdzeń musi być prawdziwe dla liczby pierwszej n(gdzie d*2^s = n-1i gdzie rjest liczba całkowita [0, s)):

Test pierwszeństwa Millera-Rabina działa na zasadzie przeciwstawności powyższego twierdzenia: jeśli istnieje podstawa ataka, że ​​oba powyższe warunki są fałszywe, nto nie jest pierwsza. Ta baza anazywa się świadkiem .

Teraz testowanie każdej bazy [1, n)byłoby zbyt drogie w obliczeniach dla dużych n. Istnieje probabilistyczny wariant testu Millera-Rabina, który testuje tylko niektóre losowo wybrane zasady w polu skończonym. Okazało się jednak, że awystarczające jest testowanie tylko podstawowych zasad, dlatego test można przeprowadzić w sposób skuteczny i deterministyczny. W rzeczywistości nie wszystkie podstawowe zasady muszą zostać przetestowane - wymagana jest tylko pewna liczba, a liczba ta zależy od wielkości testowanej wartości pierwotności.

Jeśli przetestowana zostanie niewystarczająca liczba zasad podstawowych, test może dać fałszywie dodatnie - nieparzyste liczby całkowite, w których test nie udowodni ich złożoności. W szczególności, jeśli baza anie udowodni złożoności nieparzystej liczby złożonej, liczba ta nazywana jest silnym pseudopierwszym znakiem bazy a. Wyzwanie polega na znalezieniu nieparzystych liczb zespolonych, które są silnymi pseudopierwszymi dla wszystkich zasad mniejszych lub równych Nth pierwszej liczbie podstawowej (co jest równoważne z twierdzeniem, że są one silnymi pseudopierwszymi dla wszystkich baz pierwszych mniejszych lub równych Nth pierwszej liczbie pierwszej) .

C, 349 295 277 267 255 bajtów

N,i;__int128 n=2,b,o,l[999];P(m){i<N&&P(m<2?l[i++]=n:n%m?m-1:n++);}main(r){for(P(scanf("%d",&N));r|!b;)for(++n,b=i=N;i--&&b;){for(b=n-1,r=0;~b&1;b/=2)++r;for(o=1;b--;o=o*l[i]%n);for(b=o==1;r--;o=o*o%n)b|=o>n-2;for(o=r=1;++o<n;r&=n%o>0);}printf("%llu",n);}

Pobiera 1-wejściowe dane wejściowe na standardowe wejście, np .:

echo "1" | ./millerRabin

Na pewno w najbliższym czasie nie odkryje żadnych nowych wartości w sekwencji, ale wykonuje zadanie. AKTUALIZACJA: teraz jeszcze wolniej!

• Nieco szybszy i krótszy, inspirowany odpowiedzią Neila A. ( a^(d*2^r) == (a^d)^(2^r))
• Ponownie znacznie wolniej po uświadomieniu sobie, że wszystkie rozwiązania tego wyzwania będą nieparzyste, więc nie ma potrzeby wyraźnego egzekwowania, abyśmy sprawdzali tylko liczby nieparzyste.
• Teraz używa GCC __int128, który jest krótszy niż unsigned long longpodczas pracy z większymi liczbami! Również na maszynach little-endian printf z %llunadal działa dobrze.

Mniej zminimalizowane

N,i;
__int128 n=2,b,o,l[999];
P(m){i<N&&P(m<2?l[i++]=n:n%m?m-1:n++);}
main(r){
    for(P(scanf("%d",&N));r|!b;)
        for(++n,b=i=N;i--&&b;){
            for(b=n-1,r=0;~b&1;b/=2)++r;
            for(o=1;b--;o=o*l[i]%n);
            for(b=o==1;r--;o=o*o%n)b|=o>n-2;
            for(o=r=1;++o<n;r&=n%o>0);
        }
    printf("%llu",n);
}

(Nieaktualne) Podział

unsigned long long                  // Use the longest type available
n=2,N,b,i,d,p,o,                    // Globals (mostly share names with question)
l[999];                             // Primes to check (limited to 999, but if you
                                    // want it to be "unlimited", change to -1u)
m(){for(o=1;p--;o=o*l[i]%n);}       // Inefficiently calculates (l[i]^p) mod n

// I cannot possibly take credit for this amazing prime finder;
// See /codegolf//a/5818/8927
P(m){i<N&&P(m<2?l[i++]=n:n%m?m-1:n++);}

main(r){
    for(
        P(scanf("%llu",&N));        // Read & calculate desired number of primes
        r|!b;){                     // While we haven't got an answer:
        n=n+1|1;                    // Advance to next odd number
        for(b=1,i=N;i--&&b;){       // For each prime...
            for(d=n-1,r=0;~d&1;d/=2)++r; // Calculate d and r: d*2^r = n-1
            // Check if there exists any r such that a^(d*2^r) == -1 mod n
            // OR a^d == 1 mod n
            m(p=d);
            for(b=o==1;r--;b|=o==n-1)m(p=d<<r);
            // If neither of these exist, we have proven n is not prime,
            // and the outer loop will keep going (!b)
        }
        // Check if n is actually prime;
        // if it is, the outer loop will keep going (r)
        for(i=r=1;++i<n;r&=n%i!=0);
    }
    printf("%llu",n);               // We found a non-prime; print it & stop.
}

Jak wspomniano, wykorzystuje to dane wejściowe oparte na 1. Ale dla n = 0 daje wartość 9, która następuje po pokrewnej sekwencji https://oeis.org/A006945 . Nigdy więcej; teraz wisi na 0.

Powinien działać dla wszystkich n (przynajmniej dopóki wynik nie osiągnie 2 ^ 64), ale jest niewiarygodnie wolny. Sprawdziłem to na n = 0, n = 1 i (po długim oczekiwaniu), n = 2.

Python 2, 633 465 435 292 282 275 256 247 bajtów

0-indeksowane

Zapytaj o wdrożenie i wypróbuj coś nowego

Konwersja funkcji na program pozwala jakoś zaoszczędzić niektóre bajty ...

Jeśli Python 2 daje mi krótszy sposób na zrobienie tego samego, użyję Python 2. Podział jest domyślnie liczbą całkowitą, więc łatwiejszy sposób dzielenia przez 2 i printnie wymaga nawiasów.

n=input()
f=i=3
z={2}
a=lambda:min([i%k for k in range(2,i)])
while n:
 if a():z|={i};n-=1
 i+=2
while f:
 i+=2;d,s,f=~-i,0,a()
 while~d&1:d/=2;s+=1
 for y in z:
  x=y**d%i
  if x-1:
   for _ in[]*s:
    x*=x
    if~x%i<1:break
   else:f=1
print i

Wypróbuj online!

Python jest notorycznie wolny w porównaniu do innych języków.

Definiuje test podziału próby dla absolutnej poprawności, a następnie wielokrotnie stosuje test Millera-Rabina, dopóki nie zostanie znaleziony pseudopierwszy.

Wypróbuj online!

EDYCJA : W końcu grał w golfa odpowiedź

EDYCJA : Używany mindo testu pierwszeństwa podziału próby i zmienił go na a lambda. Mniej wydajny, ale krótszy. Również nie mogłem się powstrzymać i użyłem kilku bitowych operatorów (bez różnicy długości). Teoretycznie powinien działać (nieco) szybciej.

EDYCJA : Dzięki @Dave. Mój redaktor mnie trollował. Myślałem, że używam tabulatorów, ale zamiast tego konwertowałem je na 4 spacje. Przeanalizowałem też prawie każdą wskazówkę Pythona i zastosowałem ją.

EDYCJA : Przełączony na indeksowanie 0, pozwala mi zaoszczędzić kilka bajtów z generowaniem liczb pierwszych. Zastanowiłem się także nad kilkoma porównaniami

EDYCJA : Użyła zmiennej do przechowywania wyniku testów zamiast for/elseinstrukcji.

EDYCJA : Przeniesiono lambdawewnątrz funkcji, aby wyeliminować potrzebę parametru.

EDYCJA : Konwersja do programu do zapisywania bajtów

EDYCJA : Python 2 oszczędza mi bajtów! Nie muszę też konwertować danych wejściowychint

Perl + Math :: Prime :: Util, 81 + 27 = 108 bajtów

1 until!is_provable_prime(++$\)&&is_strong_pseudoprime($\,2..nth_prime($_));$_=""

Uruchom z -lpMMath::Prime::Util=:all(kara 27 bajtów, ouch).

Wyjaśnienie

To nie tylko Mathematica ma wbudowane praktycznie wszystko. Perl ma CPAN, jedno z pierwszych dużych repozytoriów bibliotek, i które ma ogromną kolekcję gotowych rozwiązań dla zadań takich jak ten. Niestety nie są one domyślnie importowane (ani nawet instalowane), co oznacza, że ​​w zasadzie nigdy nie jest to dobra opcja ich użycia golfa , ale gdy jedno z nich idealnie pasuje do problemu…

Przeszukujemy kolejne liczby całkowite, dopóki nie znajdziemy jednej, która nie jest liczbą pierwszą, a jednak silnym pseudopierwszym znakiem dla wszystkich liczb całkowitych od 2 do n- tej liczby pierwszej. Opcja wiersza polecenia importuje bibliotekę zawierającą dane wbudowane narzędzie, a także ustawia niejawne dane wejściowe (do wiersza na raz; Math::Prime::Utilma własną wbudowaną bibliotekę bignum, która nie lubi znaków nowej linii w liczbach całkowitych). Wykorzystuje standardową sztuczkę Perla polegającą na użyciu $\(separatora linii wyjściowej) jako zmiennej w celu ograniczenia niezręcznych analiz i umożliwienia generowania danych wyjściowych w sposób niejawny.

Pamiętaj, że musimy użyć is_provable_prime tutaj , aby zażądać deterministycznego, a nie probabilistycznego testu podstawowego. (Zwłaszcza biorąc pod uwagę, że probabilistyczny test główny najprawdopodobniej użyje Millera-Rabina, czego nie możemy oczekiwać w tym przypadku, aby dać wiarygodne wyniki!)

Perl + Math :: Prime :: Util, 71 + 17 = 88 bajtów, we współpracy z @Dada

1until!is_provable_prime(++$\)&is_strong_pseudoprime$\,2..n‌​th_prime$_}{

Biegnij z -lpMntheory=:all (kara 17 bajtów).

Wykorzystuje kilka sztuczek golfowych Perla, których albo nie znałem (najwyraźniej Math :: Prime :: Util ma skrót!), O których wiedziałem, ale nie pomyślałem o użyciu ( }{do $\jednoznacznego wygenerowania danych zamiast "$_$\"domyślnie każdej linii) lub wiedział o, ale jakoś udało się go niewłaściwie zastosować (usuwając nawiasy z wywołań funkcji). Dzięki @Dada za wskazanie mi tego. Poza tym jest identyczny.