Tujuan Anda adalah untuk menentukan apakah angka yang diberikan nprima dalam byte paling sedikit. Tapi, kode Anda harus berupa ekspresi Python 2 tunggal pada angka yang hanya terdiri dari

• operator
• variabel input n
• konstanta bilangan bulat
• tanda kurung

Tidak ada loop, tidak ada tugas, tidak ada fungsi bawaan, hanya apa yang tercantum di atas. Iya itu mungkin.

Operator

Berikut daftar semua operator di Python 2 , yang termasuk operator aritmatika, bitwise, dan logis:

+    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

Semua nilai menengah adalah bilangan bulat (atau Salah / Benar, yang secara implisit sama dengan 0 dan 1). Eksponen tidak boleh digunakan dengan eksponen negatif, karena ini dapat menghasilkan pelampung. Catatan yang /melakukan pembagian lantai, tidak seperti Python 3, jadi //tidak diperlukan.

Bahkan jika Anda tidak terbiasa dengan Python, operator harus cukup intuitif. Lihat tabel ini untuk diutamakan operator dan bagian ini dan di bawah untuk spesifikasi rinci tata bahasa. Anda dapat menjalankan Python 2 di TIO .

I / O

Input: Bilangan bulat positif nminimal 2.

Output: 1 jika nprima, dan 0 sebaliknya. Truedan Falsebisa juga digunakan. Bytes paling sedikit menang.

Karena kode Anda adalah ekspresi, itu akan menjadi potongan, mengharapkan nilai input disimpan n, dan mengevaluasi untuk output yang diinginkan.

Kode Anda harus bekerja untuk nbatas sewenang - wenang yang besar dan sistem. Karena tipe bilangan bulat Python tidak terikat, tidak ada batasan pada operator. Kode Anda mungkin membutuhkan waktu lama untuk dijalankan.

43 byte

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

Cobalah online!

Metode ini mirip dengan jawaban kedua Dennis (dihapus), tetapi jawaban ini lebih mudah dibuktikan benar.

Bukti

Bentuk pendek

Digit paling signifikan (4**n+1)**n%4**n**2dalam basis yang tidak dapat dibagi oleh n akan membuat digit (kurang signifikan) berikutnya dalam bukan nol (jika "digit berikutnya" tidak berada di bagian fraksional), maka a dengan bitmask dieksekusi untuk memeriksa jika ada digit pada posisi ganjil bukan nol.$2^n$$n$(4**n+1)**n%4**n**2/n&2**(2*n*n+n)/-~2**n

Bentuk panjang

Misalkan menjadi bilangan yang memiliki representasi basis b , yaitu a n b n + ⋯ + a 1 b 1 + a 0 b 0 , dan a i be the digit at " posisi " i dalam basis b representasi.$[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$

Karena (dengann2n-1s) adalah bilangan bulat, dan⌊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}$

Selanjutnya, pertimbangkan

$$\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}$$

, sehinggaakan memotong angka menjadi 2 n digit terakhir - yang tidak termasuk ($4^{n^2}=(2^n)^{2n}$%4**n**2$2n$ (yaitu 1) tetapi termasuk semua koefisien binomial lainnya.$\binom nn$

Tentang /n:

• Jika adalah bilangan prima, hasilnya adalah [ ($n$. Semua digit pada posisi ganjil adalah nol.$\left[\binom n{n-1}/n,0,\dots,0,\binom n1/n,0,0\right]_{2^n}$

• Jika bukan bilangan prima:$n$

  Biarkan menjadi bilangan bulat terbesar sehingga n ∤ ($a$ (n>a>0). Tulis ulang dividen sebagai$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}$

  Puncak pertama memiliki semua digit yang dapat dibagi dengan , dan digit pada posisi 2 a - 1 nol.$n$$2a-1$

  Sumand kedua memiliki digit paling signifikan (pada posisi ) tidak dapat dibagi dengan n dan (dasar) 2 n > n , sehingga hasil bagi ketika membagi bahwa dengan n akan memiliki digit pada posisi 2 a - 1 bukan nol.$2a$$n$$2^n>n$$n$$2a-1$

  Oleh karena itu, hasil akhir ( (4**n+1)**n%4**n**2/n) harus memiliki digit (basis , tentu saja) di posisi 2 a + 1 bukan nol.$2^n$$2a+1$

Akhirnya, bitwise AND ( &) melakukan bitwise vectorized AND pada digit dalam basis (karena base adalah kekuatan 2), dan karena a & 0 = 0 , a & ( 2 n - 1 ) = a untuk semua 0 ≤ a < 2 n , adalah nol iff memiliki semua digit di posisi n pertama ganjil nol - yang setara dengan n menjadi prima.$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 byte

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

Cobalah online!

Ini adalah bukti-of-konsep yang tantangan ini bisa dilakukan dengan hanya operator aritmatika, khususnya tanpa bitwise |, &atau ^. Kode ini menggunakan bitwise dan operator perbandingan hanya untuk bermain golf, dan mereka dapat dengan mudah diganti dengan persamaan aritmatika.

Namun, solusinya sangat lambat, dan saya belum dapat menjalankan `, terima kasih kepada eksponen dua tingkat seperti 2 n n .$n=6$$2^{n^n}$

Gagasan utamanya adalah membuat ekspresi untuk faktorial , yang memungkinkan kita melakukan tes primoral Teorema Wilson ( n - 1 ) ! % n > n - 2 di mana % adalah operator modulo.$n!$$(n-1)! \mathbin{\%} n > n-2$$\mathbin{\%}$

Kita dapat membuat ekspresi untuk koefisien binomial , yang terbuat dari faktorial

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

Tetapi tidak jelas bagaimana cara mengekstrak hanya satu dari faktor-faktor ini. Caranya adalah dengan memalu dengan membuat m benar-benar besar.$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)$$

So, if we let $c$ be the product $\left(1-\frac{1}{m}\right)\left(1-\frac{2}{m}\right)\cdots \left(1-\frac{n-1}{m}\right)$, we have

$$n! = \frac{m^n}{\binom{m}{n}} \cdot c$$

If we could just ignore $c$, we'd be done. The rest of this post is looking how large we need to make $m$ to be able to do this.

$c$$1$ from below as $m \to \infty$. We just need to make $m$ huge enough that omitting $c$ gives us a value with integer part $n!$ so that we may compute

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

For this, it suffices to have $1 - c < 1/n!$ to avoid the ratio passing the next integer $n!+1$.

Observe that $c$ is a product of $n$ terms of which the smallest is $\left(1-\frac{n-1}{m}\right)$. So, we have

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

which means $1 - c < \frac{n^2}{m}$. Since we're looking to have $1 - c < 1/n!$, it suffices to take $m \geq n! \cdot n^2$.

In the code, we use $m=n^n$. Since Wilson's Theorem uses $(n-1)!$, we actually only need $m \geq (n-1)! \cdot (n-1)^2$. It's easy to see that $m=n^n$ satisfies the bound for the small values and quickly outgrows the right hand side asymptotically, say with Stirling's approximation.

This answer doesn't use any number-theoretic cleverness. It spams Python's bitwise operators to create a manual "for loop", checking all pairs $1 \leq i,j < n$ to see whether $i \times j = n$.

Python 2, way too many bytes (278 thanks to Jo King in the comments!)

((((((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))

Try it online!

This is a lot more bytes than the other answers, so I'm leaving it ungolfed for now. The code snippet below contains functions and variable assignment for clarity, but substitution turns isPrime(n) into a single Python expression.

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

Why does it work?

I'll do the same algorithm here in base 10 instead of binary. Look at this neat fraction:

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

If we put a large power of 10 in the numerator and use Python's floor division, this gives an enumeration of numbers. For example, $10^{15}/(999^2) = 1002003004$ with floor division, enumerating the numbers $1,2,3,4$.

Let's say we multiply two numbers like this, with different spacings of zeroes. I'll place commas suggestively in the product.

$$1002003004 \times 1000000000002000000000003000000000004 =$$ $$1002003004,002004006008,003006009012,004008012016$$

The product enumerates, in three-digit sequences, the multiplication table up to 4 times 4. If we want to check whether the number 5 is prime, we just have to check whether $005$ appears anywhere in that product.

To do that, we XOR the above product by the number $005005005\dots005$, and then subtract the number $001001001\dots001$. Call the result $d$. If $005$ appeared in the multiplication table enumeration, it will cause the subtraction to carry over and put $999$ in the corresponding place in $d$.

To test for this overflow, we compute an AND of $d$ and the number $900900900\dots900$. The result is zero if and only if 5 is prime.