Iyfjky

Question

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?
â€“Â fÃ‰Â™Ã‹ÂˆnÃ‰Â›tÃ‰Âªk
Aug 24 at 19:41 — Aug 24 at 19:41

score 33 · Answer 1 · 2018-08-11 10:39:09Z

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.

$texttt2**(2*n*n+n)/-~2**n
=lfloor2^(2n+1)nover1+2^nrfloor
=lfloor4^n^2times 2^nover1+2^nrfloor
=lfloor(4^n^2-1)times 2^nover1+2^n
+2^nover1+2^nrfloor
$.

Because $2^ntimes4^n^2-1over1+2^n
=2^n(2^n-1)times(4^n)^n-1over4^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 $lfloor2^nover1+2^nrfloor=0$,
2**(2*n*n+n)/-~2**n = $[2^n-1,0,2^n-1,0,2^n-1,0]_2^n$.

Next, consider
$$beginalign
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 n0right]_2^n
endalign$$

$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 nn-1/n,0,dots,0,binom n1/n,0,0right]_2^n$. All digits at odd position are zero.

If $n$ is not a prime:

Let $a$ be the largest integer such that $nnmidbinom na$ ($n>a>0$). Rewrite the dividend as

$left[binom nn-1,0,binom nn-2,0,dots,binom na+1,
0,0,0,dots,0,0,0right]_2^n +
left[binom na,0,binom na-1,0,dots,binom n0right]_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 $atexttt &0=0,atexttt&(2^n-1)=a$ for all $0le 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.

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 at 18:30
"I have discovered a truly remarkable proof of this answer which this comment is too small to contain..." — Aug 11 at 4:17
I have no idea what's going on here, but it's pretty darn cool. — Aug 11 at 10:44

xnor 86k16181427 · Answer 2 · 2018-08-16 00:17:48Z

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

$$binommn = fracm!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.

$$binommn = fracm(m-1)cdots(m-n+1)n!= fracm^nn!cdot left(1-frac1mright)left(1-frac2mright)cdots left(1-fracn-1mright)$$

So, if we let $c $ be the product $ left(1-frac1mright)left(1-frac2mright)cdots left(1-fracn-1mright)$, we have

$$n! = fracm^nbinommn 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! = leftlfloor fracm^nbinommn rightrfloor $$

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-fracn-1mright)$. So, we have

$$c > left(1-fracn-1mright)^n > 1 - fracn-1m n > 1-fracn^2m,$$

which means $1 - c < fracn^2m$. 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.

xnor 86k16181427 · Answer 3 · 2018-08-30 19:20:43Z

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:

$$ frac1.0999^2 = 1.002003004005dots $$

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 $ 005005005dots005 $, and then subtract the number $ 001001001dots001 $. 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 $ 900900900dots900 $. 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) — Aug 30 at 5:57

score 33 · Answer 4 · 2018-08-11 10:39:09Z

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.

$texttt2**(2*n*n+n)/-~2**n
=lfloor2^(2n+1)nover1+2^nrfloor
=lfloor4^n^2times 2^nover1+2^nrfloor
=lfloor(4^n^2-1)times 2^nover1+2^n
+2^nover1+2^nrfloor
$.

Because $2^ntimes4^n^2-1over1+2^n
=2^n(2^n-1)times(4^n)^n-1over4^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 $lfloor2^nover1+2^nrfloor=0$,
2**(2*n*n+n)/-~2**n = $[2^n-1,0,2^n-1,0,2^n-1,0]_2^n$.

Next, consider
$$beginalign
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 n0right]_2^n
endalign$$

$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 nn-1/n,0,dots,0,binom n1/n,0,0right]_2^n$. All digits at odd position are zero.

If $n$ is not a prime:

Let $a$ be the largest integer such that $nnmidbinom na$ ($n>a>0$). Rewrite the dividend as

$left[binom nn-1,0,binom nn-2,0,dots,binom na+1,
0,0,0,dots,0,0,0right]_2^n +
left[binom na,0,binom na-1,0,dots,binom n0right]_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 $atexttt &0=0,atexttt&(2^n-1)=a$ for all $0le 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.

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 at 18:30
"I have discovered a truly remarkable proof of this answer which this comment is too small to contain..." — Aug 11 at 4:17
I have no idea what's going on here, but it's pretty darn cool. — Aug 11 at 10:44

xnor 86k16181427 · Answer 5 · 2018-08-16 00:17:48Z

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

$$binommn = fracm!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.

$$binommn = fracm(m-1)cdots(m-n+1)n!= fracm^nn!cdot left(1-frac1mright)left(1-frac2mright)cdots left(1-fracn-1mright)$$

So, if we let $c $ be the product $ left(1-frac1mright)left(1-frac2mright)cdots left(1-fracn-1mright)$, we have

$$n! = fracm^nbinommn 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! = leftlfloor fracm^nbinommn rightrfloor $$

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-fracn-1mright)$. So, we have

$$c > left(1-fracn-1mright)^n > 1 - fracn-1m n > 1-fracn^2m,$$

which means $1 - c < fracn^2m$. 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.

xnor 86k16181427 · Answer 6 · 2018-08-30 19:20:43Z

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:

$$ frac1.0999^2 = 1.002003004005dots $$

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 $ 005005005dots005 $, and then subtract the number $ 001001001dots001 $. 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 $ 900900900dots900 $. 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) — Aug 30 at 5:57

Category

Random preview

Primality testing formula

3 Answers 3

43 bytes

Proof

Short form

Long form

Python 2, 56 bytes

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

Why does it work?

Your Answer

Sign up or log in

Post as a guest

Post as a guest

3 Answers 3

3 Answers 3

43 bytes

Proof

Short form

Long form

43 bytes

Proof

Short form

Long form

43 bytes

Proof

Short form

Long form

43 bytes

Proof

Short form

Long form

Python 2, 56 bytes

Python 2, 56 bytes

Python 2, 56 bytes

Python 2, 56 bytes

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

Why does it work?

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

Why does it work?

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

Why does it work?

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

Why does it work?

Sign up or log in

Post as a guest

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Comments

Post a Comment

Popular posts from this blog

Long meetings (6-7 hours a day): Being â€œbabysatâ€ by supervisor

Is the Concept of Multiple Fantasy Races Scientifically Flawed? [closed]

Confectionery

3 Answers
3

3 Answers
3

3 Answers
3

Long meetings (6-7 hours a day): Being â€œbabysatâ€ by supervisor