# 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
<<   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


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.

• Maybe this should have the python tag? Aug 24, 2018 at 19:41

# 43 bytes

(4**n+1)**n%4**n**2/n&2**(2*n*n+n)/-~2**n<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 & 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} &=(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}$, 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>a>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>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 (&) performs a vectorized bitwise AND on the digits in base $2^n$ (because the base is a power of 2), and because $a\texttt &0=0,a\texttt&(2^n-1)=a$ for all $0\le a<2^n$, (4**n+1)**n%4**n**2/n&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.

• Would (4**n+1)**n%2**n**2/n&2**n**2/-~2**n<1 work? Aug 10, 2018 at 14:00
• If it's easy to prove correct, could you include the proof in the answer? We have MathJax now, so it's relatively easy to make proofs legible, and I can't see an obvious reason for the division by n not to cause unwanted interactions between the digits base 4**n. Aug 10, 2018 at 18:30
• "I have discovered a truly remarkable proof of this answer which this comment is too small to contain..." Aug 11, 2018 at 4:17
• Suggestions for shortening the proof are welcome. Aug 11, 2018 at 10:32
• Nicely done! This is the same solution I had come up with. I found a couple of bytes can be cut with (4**n+1)**n%4**n**2/n<<n&4**n**2/-~2**n<1. I'm curious if this challenge is possible without bitwise operators.
– xnor
Aug 13, 2018 at 0:24

# Python 2, 56 bytes

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


Try it online!

This is a proof-of-concept that this challenge is doable with only arithmetic operators, in particular without bitwise |, &, or ^. The code uses bitwise and comparison operators only for golfing, and they can easily be replaced with arithmetic equivalents.

However, the solution is extremely slow, and I haven't been able to run $n=6$, thanks to two-level exponents like $2^{n^n}$.

The main idea is to make an expression for the factorial $n!$, which lets us do a Wilson's Theorem primality test $(n-1)! \mathbin{\%} n > n-2$ where $\mathbin{\%}$ is the modulo operator.

We can make an expression for the binomial coefficient, which is made of factorials

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

But it's not clear how to extract just one of these factorials. The trick is to hammer apart $n!$ by making $m$ really huge.

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

Note that $c$ approaches $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.

• A quick print of the expression puts this at 278 bytes (though I'm sure a lot of the parenthesises aren't necessary)
– Jo King
Aug 30, 2018 at 5:57