Primality testing formula Your goal is to determine whether a given number n is prime in the fewest bytes. But, your code must be a single Python 2 expression on numbers consisting of only 


operators
the input variable n
integer constants
parentheses


No loops, no assignments, no built-in functions, only what's listed above. Yes, it's possible.

Operators

Here's a list of all operators in Python 2, which include arithmetic, bitwise, and logical operators:

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


All intermediate values are integers (or False/True, which implicitly equals 0 and 1). Exponentiation may not be used with negative exponents, as this may produce floats. Note that / does floor-division, unlike Python 3, so // is not needed.

Even if you're not familiar with Python, the operators should be pretty intuitive. See this table for operator precedence and this section and below for a detailed specification of the grammar. You can run Python 2 on TIO.

I/O

Input: A positive integer n that's at least 2.

Output: 1 if n is prime, and 0 otherwise. True and False may also be used. Fewest bytes wins.

Since your code is an expression, it will be a snippet, expecting the input value stored as n, and evaluating to the output desired.

Your code must work for n arbitrarily large, system limits aside. Since Python's whole-number type is unbounded, there are no limits on the operators. Your code may take however long to run.
43 bytes



(4**n+1)**n%4**n**2/n&amp;2**(2*n*n+n)/-~2**n&lt;1


Try it online!

The method is similar to Dennis' second (deleted) answer, but this answer is easier to be proved correct.

Proof

Short form

The most significant digit of (4**n+1)**n%4**n**2 in base \$2^n\$ that is not divisible by \$n\$ will make the next (less significant) digit in (4**n+1)**n%4**n**2/n nonzero (if that "next digit" is not in the fractional part), then a &amp; with the bitmask 2**(2*n*n+n)/-~2**n is executed to check if any digit at odd position is nonzero.

Long form

Let \$[a_n,\dots,a_1,a_0]_b\$ be the number having that base \$b\$ representation, i.e., \$a_nb^n+\dots+a_1b^1+a_0b^0\$, and \$a_i\$ be the digit at "position" \$i\$ in base \$b\$ representation.


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


Because \$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}\$ (with \$n\$ \$2^n-1\$s) is an integer,
and \$\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}\$.

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

\$4^{n^2}=(2^n)^{2n}\$, so %4**n**2 will truncate the number to \$2n\$ last digits - that excludes the \$\binom nn\$ (which is 1) but include all other binomial coefficients.

About /n:


If \$n\$ is a prime, the result will be \$\left[\binom n{n-1}/n,0,\dots,0,\binom n1/n,0,0\right]_{2^n}\$. All digits at odd position are zero.
If \$n\$ is not a prime:

Let \$a\$ be the largest integer such that \$n\nmid\binom na\$ (\$n&gt;a&gt;0\$). Rewrite the dividend as

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

The first summand has all digits divisible by \$n\$, and the digit at position \$2a-1\$ zero.

The second summand has its most significant digit (at position \$2a\$) not divisible by \$n\$ and (the base) \$2^n&gt;n\$, so the quotient when dividing that by \$n\$ would have the digit at position \$2a-1\$ nonzero.

Therefore, the final result ((4**n+1)**n%4**n**2/n) should have the digit (base \$2^n\$, of course) at position \$2a+1\$ nonzero.


Finally, the bitwise AND (&amp;) performs a vectorized bitwise AND on the digits in base \$2^n\$ (because the base is a power of 2), and because \$a\texttt &amp;0=0,a\texttt&amp;(2^n-1)=a\$ for all \$0\le a&lt;2^n\$, (4**n+1)**n%4**n**2/n&amp;2**(2*n*n+n)/-~2**n is zero iff (4**n+1)**n%4**n**2/n has all digits in first \$n\$ odd positions zero - which is equivalent to \$n\$ being prime.