Primalitätstestformel

30

Ihr Ziel ist es festzustellen, ob eine bestimmte Zahl nin den wenigsten Bytes eine Primzahl ist. Ihr Code muss jedoch ein einzelner Python 2- Ausdruck sein, der nur aus Zahlen besteht

  • Betreiber
  • die Eingangsvariable n
  • ganzzahlige Konstanten
  • Klammern

Keine Schleifen, keine Zuweisungen, keine eingebauten Funktionen, nur das, was oben aufgeführt ist. Ja es ist möglich.

Betreiber

Hier ist eine Liste aller Operatoren in Python 2 , einschließlich arithmetischer, bitweiser und logischer Operatoren:

+    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

Alle Zwischenwerte sind Ganzzahlen (oder False / True, was implizit 0 und 1 entspricht). Exponentiation darf nicht mit negativen Exponenten verwendet werden, da dies zu Floats führen kann. Beachten Sie, dass /die Unterteilung im Gegensatz zu Python 3 //nicht erforderlich ist.

Auch wenn Sie nicht mit Python vertraut sind, sollten die Operatoren ziemlich intuitiv sein. In dieser Tabelle finden Sie die Rangfolge der Operatoren sowie in diesem und dem folgenden Abschnitt eine detaillierte Beschreibung der Grammatik. Sie können Python 2 unter TIO ausführen .

I / O

Eingabe: Eine positive Ganzzahl n, die mindestens 2 ist.

Ausgang: 1 wenn nPrimzahl und 0 sonst. Trueund Falsekann auch verwendet werden. Wenigste Bytes gewinnt.

Da es sich bei Ihrem Code um einen Ausdruck handelt, handelt es sich um ein Snippet, bei dem der Eingabewert als gespeichert nund die gewünschte Ausgabe ausgewertet wird.

Ihr Code muss für nbeliebig große Systemgrenzen funktionieren. Da der Ganzzahltyp von Python unbegrenzt ist, sind den Operatoren keine Grenzen gesetzt. Es kann jedoch lange dauern, bis Ihr Code ausgeführt wird.

xnor
quelle
Vielleicht sollte dies das Python-Tag haben?
Freitag,

Antworten:

35

43 Bytes

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

Probieren Sie es online!

Die Methode ähnelt der zweiten (gelöschten) Antwort von Dennis, aber diese Antwort lässt sich leichter als richtig erweisen.

Beweis

Kurzform

Die höchstwertige Ziffer (4**n+1)**n%4**n**2in der Basis 2n , die nicht durch teilbar ist, ergibt ndie nächste (niedrigere) Ziffer (4**n+1)**n%4**n**2/nungleich Null (wenn diese "nächste Ziffer" nicht im Bruchteil liegt), dann a &mit der Bitmaske2**(2*n*n+n)/-~2**n wird zur Überprüfung ausgeführt Wenn eine Ziffer an einer ungeraden Position ungleich Null ist.

Lange Form

Sei die Zahl mit der Darstellung der Basis b , dh a n b n + + a 1 b 1 + a 0 b 0 , und a i sei die Ziffer bei Position " i " in der Darstellung der Basis b .[an,,a1,a0]bbanbn++a1b1+a0b0aiib

  • .2**(2*n*n+n)/-~2**n=2(2n+1)n1+2n=4n2×2n1+2n=(4n21)×2n1+2n+2n1+2n

Weil (mitn22n×4n211+2n=2n(2n1)×(4n)n14n1=[2n1,0,2n1,0,2n1,0]2nn s) ist eine ganze Zahl und2 n2n1, =[2n-1,0,2n-1,0,2n-1,0]2n.2n1+2n=02**(2*n*n+n)/-~2**n[2n1,0,2n1,0,2n1,0]2n

Als nächstes betrachten

(4**n+1)**n=(4n+1)n=(n0)40n+(n1)41n++(nn)4n2=[(nn),0,,0,(n1),0,(n0)]2n

, alsowird die Zahl auf 2 n letzte Stellen gekürzt - das schließt das ( n) aus4n2=(2n)2n%4**n**22n (ist 1), enthält aber alle anderen Binomialkoeffizienten.(nn)

Über /n:

  • Wenn eine Primzahl ist, ist das Ergebnis [n. Alle Ziffern an der ungeraden Position sind Null.[(nn1)/n,0,,0,(n1)/n,0,0]2n

  • Wenn keine Primzahl ist:n

    Sei die größte ganze Zahl, so dass n ( na (n>a>0). Schreiben Sie die Dividende um alsn(na)n>a>0

    [(nn1),0,(nn2),0,,(na+1),0,0,0,,0,0,0]2n+[(na),0,(na1),0,,(n0)]2n

    The first summand has all digits divisible by n, and the digit at position 2a1 zero.

    The second summand has its most significant digit (at position 2a) not divisible by n and (the base) 2n>n, so the quotient when dividing that by n would have the digit at position 2a1 nonzero.

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

Finally, the bitwise AND (&) performs a vectorized bitwise AND on the digits in base 2n (because the base is a power of 2), and because a&0=0,a&(2n1)=a for all 0a<2n, (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.

user202729
quelle
2
Would (4**n+1)**n%2**n**2/n&2**n**2/-~2**n<1 work?
Dennis
11
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.
Peter Taylor
3
"I have discovered a truly remarkable proof of this answer which this comment is too small to contain..."
Digital Trauma
1
Vorschläge zur Verkürzung des Nachweises sind willkommen.
user202729
1
Schön gemacht! Dies ist die gleiche Lösung, die ich mir ausgedacht hatte. Ich fand, dass ein paar Bytes mit geschnitten werden können (4**n+1)**n%4**n**2/n<<n&4**n**2/-~2**n<1. Ich bin gespannt, ob diese Herausforderung ohne bitweise Operatoren möglich ist.
xnor
6

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!

Dies ist ein Proof-of-Concept, dass diese Herausforderung nur mit arithmetischen Operatoren, insbesondere ohne bitweise, durchgeführt werden kann |, &, or ^. The code uses bitwise and comparison operators only for golfing, and they can easily be replaced with arithmetic equivalents.

Die Lösung ist jedoch extrem langsam und ich konnte nicht ausführenn=62nn.

The main idea is to make an expression for the factorial n!, which lets us do a Wilson's Theorem primality test (n1)!%n>n2 where % is the modulo operator.

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

(mn) =m!n!(mn)!

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.

(mn) =m(m1)(mn+1)n!=mnn!(11m)(12m)(1n1m)

So, if we let c be the product (11m)(12m)(1n1m), we have

n!=mn(mn)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. 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!=mn(mn)

For this, it suffices to have 1c<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 (1n1m). So, we have

c>(1n1m)n>1n1mn>1n2m,

which means 1c<n2m. Since we're looking to have 1c<1/n!, it suffices to take mn!n2.

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

xnor
quelle
3

This answer doesn't use any number-theoretic cleverness. It spams Python's bitwise operators to create a manual "for loop", checking all pairs 1i,j<n to see whether i×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:

1.09992=1.002003004005

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, 1015/(9992)=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×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 005005005005, and then subtract the number 001001001001. 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 900900900900. The result is zero if and only if 5 is prime.

Lopsy
quelle
1
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