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.

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.$2^n$$n$(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 .$[a_n,\dots,a_1,a_0]_b$$b$$a_nb^n+\dots+a_1b^1+a_0b^0$$a_i$$i$$b$

• .$\texttt{2**(2*n*n+n)/-~2**n} =\lfloor{2^{(2n+1)n}\over1+2^n}\rfloor =\lfloor{4^{n^2}\times 2^n\over1+2^n}\rfloor =\lfloor{{(4^{n^2}-1)\times 2^n\over1+2^n} +{2^n\over1+2^n}}\rfloor$

Ponieważ (przyn2n-1s) jest liczbą całkowitą, a⌊2$2^n\times{4^{n^2}-1\over1+2^n} =2^n(2^n-1)\times{(4^n)^n-1\over4^n-1} =[2^n-1,0,2^n-1,0,2^n-1,0]_{2^n}$$n$ $2^n-1$, =[2n-1,0,2n-1,0,2n-1,0]2n.$\lfloor{2^n\over1+2^n}\rfloor=0$2**(2*n*n+n)/-~2**n$[2^n-1,0,2^n-1,0,2^n-1,0]_{2^n}$

Następnie rozważ

$$\begin{align} \texttt{(4**n+1)**n} &=(4^n+1)^n \\ &=\binom n04^{0n}+\binom n14^{1n}+\dots+\binom nn4^{n^2} \\ &=\left[\binom nn,0,\dots,0,\binom n1,0,\binom n0\right]_{2^n} \end{align}$$

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

O /n:

• Jeśli jest liczbą pierwszą, wynikiem będzie . Wszystkie cyfry w nieparzystej pozycji są równe zero.$n$$\left[\binom n{n-1}/n,0,\dots,0,\binom n1/n,0,0\right]_{2^n}$

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

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

  $\left[\binom n{n-1},0,\binom n{n-2},0,\dots,\binom n{a+1}, 0,0,0,\dots,0,0,0\right]_{2^n} + \left[\binom na,0,\binom n{a-1},0,\dots,\binom n0\right]_{2^n}$

  Pierwszy summand ma wszystkie cyfry podzielne przez , a cyfra na pozycji zero.$n$$2a-1$

  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ą.$2a$$n$$2^n>n$$n$$2a-1$

  Dlatego końcowy wynik ( (4**n+1)**n%4**n**2/n) powinien mieć cyfrę (podstawa , oczywiście) w pozycji niezerową.$2^n$$2a+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ą.$2^n$$a\texttt &0=0,a\texttt&(2^n-1)=a$$0\le a<2^n$(4**n+1)**n%4**n**2/n&2**(2*n*n+n)/-~2**n(4**n+1)**n%4**n**2/n$n$$n$

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=6$$2^{n^n}$

Główną ideą jest wyrażenie na silnię, który pozwala nam wykonać test pierwszeństwa Twierdzenia Wilsona gdzie jest operatorem modulo.$n!$$(n-1)! \mathbin{\%} n > n-2$$\mathbin{\%}$

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

$$\binom{m}{n} \ = \frac{m!}{n!(m-n)!}$$

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

$$\binom{m}{n} \ = \frac{m(m-1)\cdots(m-n+1)}{n!}= \frac{m^n}{n!}\cdot \left(1-\frac{1}{m}\right)\left(1-\frac{2}{m}\right)\cdots \left(1-\frac{n-1}{m}\right)$$

Więc jeśli pozwolimy być produktem , mamy$c$$\left(1-\frac{1}{m}\right)\left(1-\frac{2}{m}\right)\cdots \left(1-\frac{n-1}{m}\right)$

$$n! = \frac{m^n}{\binom{m}{n}} \cdot 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ć.$c$$m$

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ć$c$$1$$m \to \infty$$m$$c$$n!$

$$n! = \left\lfloor \frac{m^n}{\binom{m}{n}} \right\rfloor$$

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

Zauważ, że jest iloczynem warunków, z których najmniejszym jest . Więc mamy$c$$n$$\left(1-\frac{n-1}{m}\right)$

$$c > \left(1-\frac{n-1}{m}\right)^n > 1 - \frac{n-1}{m} n > 1-\frac{n^2}{m},$$

co oznacza . Ponieważ chcemy mieć, wystarczy wziąć .$1 - c < \frac{n^2}{m}$$1 - c < 1/n!$$m \geq n! \cdot n^2$

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=n^n$$(n-1)!$$m \geq (n-1)! \cdot (n-1)^2$$m=n^n$

Ta odpowiedź nie wykorzystuje żadnej sprytowej teorii. Spamuje bitowe operatory Pythona, aby utworzyć instrukcję „for loop”, sprawdzając wszystkie pary aby zobaczyć, czy .$1 \leq i,j < n$$i \times 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ę:

$$\frac{1.0}{999^2} = 1.002003004005\dots$$

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 .$10^{15}/(999^2) = 1002003004$$1,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 \times 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 .$005005005\dots005$$001001001\dots001$$d$$005$$999$$d$

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