Votre objectif est de déterminer si un nombre donné nest premier dans le moins d'octets. Mais, votre code doit être une seule expression Python 2 sur des nombres composés uniquement de

• les opérateurs
• la variable d'entrée n
• constantes entières
• parenthèses

Pas de boucles, pas d'affectations, pas de fonctions intégrées, seulement ce qui est indiqué ci-dessus. Oui c'est possible.

Les opérateurs

Voici une liste de tous les opérateurs de Python 2 , qui incluent les opérateurs arithmétiques, au niveau du bit et logiques:

+    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

Toutes les valeurs intermédiaires sont des entiers (ou False / True, ce qui équivaut implicitement à 0 et 1). L'exponentiation ne peut pas être utilisée avec des exposants négatifs, car cela peut produire des flottants. Notez que la /division au sol, contrairement à Python 3, //n'est donc pas nécessaire.

Même si vous n'êtes pas familier avec Python, les opérateurs devraient être assez intuitifs. Voir ce tableau pour la priorité des opérateurs et cette section et ci-dessous pour une spécification détaillée de la grammaire. Vous pouvez exécuter Python 2 sur TIO .

E / S

Entrée: un entier positif nd'au moins 2.

Sortie: 1 si nest premier et 0 sinon. Trueet Falsepeut également être utilisé. Le moins d'octets gagne.

Étant donné que votre code est une expression, il s'agira d'un extrait de code, qui attend la valeur d'entrée stockée en tant que net évalue la sortie souhaitée.

Votre code doit fonctionner pour ndes limites arbitrairement grandes, système mis à part. Étant donné que le type de nombre entier de Python est illimité, il n'y a pas de limites sur les opérateurs. Votre code peut toutefois être long à exécuter.

43 octets

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

Essayez-le en ligne!

La méthode est similaire à la deuxième réponse (supprimée) de Dennis, mais cette réponse est plus facile à prouver.

Preuve

Forme courte

Le chiffre le plus significatif de (4**n+1)**n%4**n**2dans la base qui n'est pas divisible par n fera le chiffre suivant (moins significatif) en non nul (si ce "chiffre suivant" n'est pas dans la partie fractionnaire), alors a avec le masque binaire est exécuté pour vérifier si un chiffre à une position impaire est différent de zéro.$2^n$$n$(4**n+1)**n%4**n**2/n&2**(2*n*n+n)/-~2**n

Forme longue

Soit le nombre ayant cette représentation de base b , c'est-à-dire a n b n + ⋯ + a 1 b 1 + a 0 b 0 , et a i le chiffre à " position " i dans la représentation de base b .$[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$

Parce que (avecn2n-1s) est un entier, et⌊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}$

Ensuite, considérez

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

2 n ($4^{n^2}=(2^n)^{2n}$ , donc %4**n**2tronquera le nombre à derniers chiffres - ce qui exclut le (qui est 1) mais inclut tous les autres coefficients binomiaux.$2n$$\binom nn$

À propos de /n:

• Si est un nombre premier, le résultat sera . Tous les chiffres en position impaire sont nuls.[ ($n$$\left[\binom n{n-1}/n,0,\dots,0,\binom n1/n,0,0\right]_{2^n}$

• Si n'est pas un nombre premier:$n$

  Soit le plus grand entier tel que ( ). Réécrivez le dividende comme$a$$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}$

  Le premier sommet a tous les chiffres divisibles par , et le chiffre à la position zéro.$n$$2a-1$

  La deuxième somme a son chiffre le plus significatif (à la position ) non divisible par et (la base) , donc le quotient en divisant cela par aurait le chiffre à la position non nul.$2a$$n$$2^n>n$$n$$2a-1$

  Par conséquent, le résultat final ( (4**n+1)**n%4**n**2/n) devrait avoir le chiffre (base , bien sûr) à la position différent de zéro.$2^n$$2a+1$

Enfin, l'ET au niveau du bit ( &) effectue un AND au niveau du vecteur vectorisé sur les chiffres de la base (car la base est une puissance de 2), et parce pour tout , est nul ssi tous les chiffres sont dans les premières positions impaires zéro - ce qui équivaut à étant premier.$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 octets

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

Essayez-le en ligne!

Ceci est une preuve de concept que ce défi est réalisable avec seulement des opérateurs arithmétiques, en particulier sans bitwise |, &ou ^. Le code utilise des opérateurs de bits et de comparaison uniquement pour le golf, et ils peuvent facilement être remplacés par des équivalents arithmétiques.

Cependant, la solution est extrêmement lente, et je n'ai pas pu exécuter `, grâce à des exposants à deux niveaux comme .$n=6$$2^{n^n}$

L'idée principale est de faire une expression pour le factoriel, ce qui nous permet de faire un test de primalité du théorème de Wilson où est l'opérateur modulo.$n!$$(n-1)! \mathbin{\%} n > n-2$$\mathbin{\%}$

Nous pouvons faire une expression pour le coefficient binomial , qui est composé de factorielles

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

Mais il n'est pas clair comment extraire un seul de ces factoriels. L'astuce consiste à marteleren faisant vraiment énorme.$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)$$

Donc, si nous laissons le produit , nous avons$c$$\left(1-\frac{1}{m}\right)\left(1-\frac{2}{m}\right)\cdots \left(1-\frac{n-1}{m}\right)$

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

Si nous pouvions simplement ignorer , nous aurions fini. Le reste de cet article examine la taille dont nous avons besoin pour faire pour pouvoir le faire.$c$$m$

Notez que approche par le bas comme . Nous avons juste besoin de faire assez grand pour que l'omission de nous donne une valeur avec la partie entièreafin que nous puissions calculer$c$$1$$m \to \infty$$m$$c$$n!$

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

Pour cela, il suffit d'avoirpour éviter que le rapport ne passe le prochain entier .$1 - c < 1/n!$$n!+1$

Remarquez que est un produit de termes dont le plus petit est . Nous avons donc$c$$n$$\left(1-\frac{n-1}{m}\right)$

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

ce qui signifie . Puisque nous cherchons à avoir, il suffit de prendre .$1 - c < \frac{n^2}{m}$$1 - c < 1/n!$$m \geq n! \cdot n^2$

Dans le code, nous utilisons . Depuis le théorème de Wilson utilise, nous n'avons en fait besoin que de . Il est facile de voir que satisfait la limite pour les petites valeurs et dépasse rapidement le côté droit asymptotiquement, par exemple avec l'approximation de Stirling .$m=n^n$$(n-1)!$$m \geq (n-1)! \cdot (n-1)^2$$m=n^n$

Cette réponse n'utilise aucune intelligence théorique des nombres. Il spams les opérateurs au niveau du bit de Python pour créer un manuel "for loop", vérifiant toutes les paires pour voir si .$1 \leq i,j < n$$i \times j = n$

Python 2, beaucoup trop d'octets (278 merci à Jo King dans les commentaires!)

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

Essayez-le en ligne!

C'est beaucoup plus d'octets que les autres réponses, donc je ne le laisse pas pour l'instant. L'extrait de code ci-dessous contient des fonctions et des affectations de variables pour plus de clarté, mais la substitution transforme isPrime (n) en une seule expression Python.

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

Pourquoi ça marche?

Je ferai le même algorithme ici en base 10 au lieu de binaire. Regardez cette fraction soignée:

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

Si nous mettons une grande puissance de 10 dans le numérateur et utilisons la division de plancher de Python, cela donne une énumération de nombres. Par exemple, avec division au sol, en énumérant les nombres .$10^{15}/(999^2) = 1002003004$$1,2,3,4$

Disons que nous multiplions deux nombres comme celui-ci, avec différents espacements de zéros. Je placerai des virgules de manière suggestive dans le produit.

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

Le produit énumère, en séquences à trois chiffres, la table de multiplication jusqu'à 4 fois 4. Si nous voulons vérifier si le nombre 5 est premier, il suffit de vérifier si apparaît n'importe où dans ce produit.$005$

Pour ce faire, nous XOR le produit ci-dessus par le numéro , puis soustrayons le numéro . Appelez le résultat . Si est apparu dans l'énumération de la table de multiplication, cela entraînera le report de la soustraction et mettra à la place correspondante en .$005005005\dots005$$001001001\dots001$$d$$005$$999$$d$

Pour tester ce débordement, nous calculons un ET de et le nombre . Le résultat est nul si et seulement si 5 est premier.$d$$900900900\dots900$