Formuła testowania pierwszeństwa

30

Twoim celem jest ustalenie, czy dana liczba njest liczbą pierwszą w najmniejszej liczbie bajtów. Ale twój kod musi być pojedynczym wyrażeniem Python 2 na liczbach składających się tylko z

  • operatorzy
  • zmienna wejściowa n
  • stałe całkowite
  • zdanie wtrącone

Bez pętli, bez przypisań, bez wbudowanych funkcji, tylko to, co wymieniono powyżej. Tak, to możliwe.

Operatorzy

Oto lista wszystkich operatorów w Pythonie 2 , które obejmują operatory arytmetyczne, bitowe i logiczne:

+    adddition
-    minus or unary negation
*    multiplication
**   exponentiation, only with non-negative exponent
/    floor division
%    modulo
<<   bit shift left
>>   bit shift right
&    bitwise and
|    bitwise or
^    bitwise xor
~    bitwise not
<    less than
>    greater than
<=   less than or equals
>=   greater than or equals
==   equals
!=   does not equal

Wszystkie wartości pośrednie są liczbami całkowitymi (lub False / True, które domyślnie wynoszą 0 i 1). Potęgowanie nie może być stosowane z wykładnikami ujemnymi, ponieważ może to powodować liczby zmiennoprzecinkowe. Zauważ, że dzieli /podział podłogi, w przeciwieństwie do Pythona 3, więc //nie jest potrzebny.

Nawet jeśli nie znasz języka Python, operatory powinny być dość intuicyjne. Patrz tej tabeli operatorów, i tym odcinku i poniżej w szczegółowym opisie gramatyki. Możesz uruchomić Python 2 na TIO .

I / O

Dane wejściowe: dodatnia liczba całkowita, nktóra wynosi co najmniej 2.

Wyjście: 1 jeśli njest liczbą pierwszą, a 0 w przeciwnym razie. Truei Falsemogą być również używane. Wygrywa najmniej bajtów.

Ponieważ twój kod jest wyrażeniem, będzie fragmentem, oczekującym wartości wejściowej przechowywanej jako ni oceniającym pożądane wyjście.

Kod musi działać nniezależnie od dowolnych, dużych limitów systemowych. Ponieważ typ liczbowy Pythona jest nieograniczony, operatorzy nie mają żadnych ograniczeń. Uruchomienie kodu może jednak zająć dużo czasu.

xnor
źródło
Może powinien mieć tag python?
fəˈnɛtɪk

Odpowiedzi:

35

43 bajty

(4**n+1)**n%4**n**2/n&2**(2*n*n+n)/-~2**n<1

Wypróbuj online!

Metoda jest podobna do drugiej (usuniętej) odpowiedzi Dennisa, ale łatwiej jest udowodnić, że jest poprawna.

Dowód

Skrócona forma

Najbardziej znacząca cyfra (4**n+1)**n%4**n**2w podstawie która nie jest podzielna przez n, spowoduje, że następna (mniej znacząca) cyfra będzie niezerowa (jeśli ta „kolejna cyfra” nie znajduje się w części ułamkowej), wówczas wykonywana jest a z maską bitową w celu sprawdzenia jeśli jakakolwiek cyfra w nieparzystej pozycji jest niezerowa.2nn(4**n+1)**n%4**n**2/n&2**(2*n*n+n)/-~2**n

Długa forma

Niech jest liczbą o tej podstawy b reprezentację, czyli n b n + + 1 b 1 + 0 b 0 i i być cyfra w " pozycja „ i w reprezentacji bazy b .[an,,a1,a0]bbanbn++a1b1+a0b0aiib

  • .2**(2*n*n+n)/-~2**n=2(2n+1)n1+2n=4n2×2n1+2n=(4n21)×2n1+2n+2n1+2n

Ponieważ (przyn2n-1s) jest liczbą całkowitą, a2n2n×4n211+2n=2n(2n1)×(4n)n14n1=[2n1,0,2n1,0,2n1,0]2nn 2n1, =[2n-1,0,2n-1,0,2n-1,0]2n.2n1+2n=02**(2*n*n+n)/-~2**n[2n1,0,2n1,0,2n1,0]2n

Następnie rozważ

(4**n+1)**n=(4n+1)n=(n0)40n+(n1)41n++(nn)4n2=[(nn),0,,0,(n1),0,(n0)]2n

4n2=(2n)2n , więc%4**n**2 liczbę do ostatnich cyfr - co wyklucza (czyli 1), ale obejmuje wszystkie inne współczynniki dwumianowe.2n(nn)

O /n:

  • Jeśli jest liczbą pierwszą, wynikiem będzie . Wszystkie cyfry w nieparzystej pozycji są równe zero.n[(nn1)/n,0,,0,(n1)/n,0,0]2n

  • Jeśli nie jest liczbą pierwszą:n

    Niech będzie największą liczbą całkowitą taką, że ( ). Przepisz dywidendę jakoan(na)n>a>0

    [(nn1),0,(nn2),0,,(na+1),0,0,0,,0,0,0]2n+[(na),0,(na1),0,,(n0)]2n

    Pierwszy summand ma wszystkie cyfry podzielne przez , a cyfra na pozycji zero.n2a1

    Drugi zbiór ma swoją najbardziej znaczącą cyfrę (w pozycji ) niepodzielną przez i (podstawa) , więc iloraz przy dzieleniu tej przez miałby cyfrę w pozycji niezerową.2an2n>nn2a1

    Dlatego końcowy wynik ( (4**n+1)**n%4**n**2/n) powinien mieć cyfrę (podstawa , oczywiście) w pozycji niezerową.2n2a+1

Wreszcie bitowe AND ( &) wykonuje wektoryzowane bitowe AND na cyfrach w podstawie (ponieważ podstawa jest potęgą 2), a ponieważ dla wszystkich , wynosi zero iff ma wszystkie cyfry w pierwszych nieparzystych pozycjach zero - co odpowiada jest liczbą pierwszą.2na&0=0,a&(2n1)=a0a<2n(4**n+1)**n%4**n**2/n&2**(2*n*n+n)/-~2**n(4**n+1)**n%4**n**2/nnn

użytkownik202729
źródło
2
Czy (4**n+1)**n%2**n**2/n&2**n**2/-~2**n<1zadziała?
Dennis,
11
Jeśli łatwo jest udowodnić poprawność, czy możesz dołączyć dowód do odpowiedzi? Mamy teraz MathJax, więc stosunkowo łatwo jest uczynić dowody czytelnymi i nie widzę oczywistego powodu podziału, nnie powodując niepożądanych interakcji między bazą cyfr 4**n.
Peter Taylor,
3
„Odkryłem naprawdę niezwykły dowód na tę odpowiedź, w której ten komentarz jest zbyt mały, aby go pomieścić ...”
Digital Trauma
1
Sugestie dotyczące skrócenia dowodu są mile widziane.
user202729,
1
Ładnie wykonane! To jest to samo rozwiązanie, które wymyśliłem. Znalazłem kilka bajtów, które można wyciąć (4**n+1)**n%4**n**2/n<<n&4**n**2/-~2**n<1. Jestem ciekawy, czy to wyzwanie jest możliwe bez operatorów bitowych.
xnor
6

Python 2 , 56 bajtów

n**(n*n-n)/(((2**n**n+1)**n**n>>n**n*~-n)%2**n**n)%n>n-2

Wypróbuj online!

Jest to proof-of-concept, że to wyzwanie jest wykonalne tylko operatorów arytmetycznych, w szczególności bez bitowe |, &lub ^. Kod wykorzystuje operatory bitowe i porównania tylko do gry w golfa i można je łatwo zastąpić odpowiednikami arytmetycznymi.

Jednak rozwiązanie jest bardzo wolne i nie byłem w stanie uruchomić `, dzięki dwupoziomowym potęgom takim jak .n=62nn

Główną ideą jest wyrażenie na silnię, który pozwala nam wykonać test pierwszeństwa Twierdzenia Wilsona gdzie jest operatorem modulo.n!(n1)!%n>n2%

Możemy wyrazić współczynnik dwumianowy , który składa się z silni

(mn) =m!n!(mn)!

Ale nie jest jasne, jak wyodrębnić tylko jeden z tych czynników. Sztuką jest rozbicieczyniąc naprawdę ogromnym.n!m

(mn) =m(m1)(mn+1)n!=mnn!(11m)(12m)(1n1m)

Więc jeśli pozwolimy być produktem , mamyc(11m)(12m)(1n1m)

n!=mn(mn)c

Gdybyśmy mogli po prostu zignorować , bylibyśmy skończeni. Reszta tego postu pokazuje, jak duże musimy zrobić aby móc to zrobić.cm

Zauważ, że zbliża się do od dołu jako . Musimy tylko zrobić tak duże, że pominięcie daje nam wartość z liczbą całkowitąabyśmy mogli obliczyćc1mmcn!

n!=mn(mn)

W tym celu wystarczy miećaby uniknąć przekroczenia stosunku następnej liczby całkowitej .1c<1/n!n!+1

Zauważ, że jest iloczynem warunków, z których najmniejszym jest . Więc mamycn(1n1m)

c>(1n1m)n>1n1mn>1n2m,

co oznacza . Ponieważ chcemy mieć, wystarczy wziąć .1c<n2m1c<1/n!mn!n2

W kodzie używamy . Ponieważ używa Twierdzenia Wilsona, w rzeczywistości potrzebujemy tylko . Łatwo zauważyć, że spełnia granicę małych wartości i szybko przerasta asymptotycznie prawą stronę, powiedzmy z przybliżeniem Stirlinga .m=nn(n1)!m(n1)!(n1)2m=nn

xnor
źródło
3

Ta odpowiedź nie wykorzystuje żadnej sprytowej teorii. Spamuje bitowe operatory Pythona, aby utworzyć instrukcję „for loop”, sprawdzając wszystkie pary aby zobaczyć, czy .1i,j<ni×j=n

Python 2, zdecydowanie za dużo bajtów (278 dzięki Jo King w komentarzach!)

((((((2**(n*n)/(2**n-1)**2)*(2**((n**2)*n)/(2**(n**2)-1)**2))^((n*((2**(n*n-n)/(2**n-1))*(2**((n**2)*(n-1))/(2**n**2-1))))))-((2**(n*n-n)/(2**n-1))*(2**((n**2)*(n-1))/(2**(n**2)-1))))&(((2**(n*(n-1))/(2**n-1))*(2**((n**2)*(n-1))/(2**(n**2)-1)))*(2**(n-1)))==0))|((1<n<6)&(n!=4))

Wypróbuj online!

To jest o wiele więcej bajtów niż inne odpowiedzi, więc na razie pozostawiam to bez odpowiedzi. Poniższy fragment kodu zawiera funkcje i przypisanie zmiennych dla przejrzystości, ale podstawienie zamienia isPrime (n) w pojedyncze wyrażenie Python.

def count(k, spacing):
    return 2**(spacing*(k+1))/(2**spacing - 1)**2
def ones(k, spacing):
    return 2**(spacing*k)/(2**spacing - 1)

def isPrime(n):
    x = count(n-1, n)
    y = count(n-1, n**2)
    onebits = ones(n-1, n) * ones(n-1, n**2)
    comparison = n*onebits
    difference = (x*y) ^ (comparison)
    differenceMinusOne = difference - onebits
    checkbits = onebits*(2**(n-1))
    return (differenceMinusOne & checkbits == 0 and n>1)or 1<n<6 and n!=4

Dlaczego to działa?

Zrobię ten sam algorytm tutaj w bazie 10 zamiast binarnej. Spójrz na tę zgrabną frakcję:

1.09992=1.002003004005

Jeśli umieścimy dużą moc 10 w liczniku i użyjemy podziału podłogi Pythona, daje to wyliczenie liczb. Na przykład z podziałem podłogi, wyliczając liczby .1015/(9992)=10020030041,2,3,4

Powiedzmy, że mnożymy dwie liczby w ten sposób, z różnymi odstępami zer. Umieszczę przecinki sugestywnie w produkcie.

1002003004×1000000000002000000000003000000000004=
1002003004,002004006008,003006009012,004008012016

Produkt wylicza, w trzycyfrowych sekwencjach, tabliczkę mnożenia do 4 razy 4. Jeśli chcemy sprawdzić, czy liczba 5 jest liczbą pierwszą, musimy tylko sprawdzić, czy pojawia się gdziekolwiek w tym produkcie.005

Aby to zrobić, XOR powyższy produkt XOR numer , a następnie odejmujemy liczbę . Nazwij wynik . Jeśli w wyliczeniu tablicy mnożenia pojawiło się , spowoduje to przeniesienie odejmowania i umieszczenie w odpowiednim miejscu w .005005005005001001001001d005999d

Aby przetestować to przepełnienie, obliczamy AND AND i liczbę . Wynik wynosi zero wtedy i tylko wtedy, gdy 5 jest liczbą pierwszą.d900900900900

Lopsy
źródło
1
Szybki wydruk wyrażenia podaje 278 bajtów (choć jestem pewien, że wiele nawiasów nie jest koniecznych)
Jo King