Dans ce défi posé par xnor, on nous a demandé d'implémenter la multiplication XOR. Dans ce défi, l'objectif est de trouver les premiers nnombres premiers XOR. Les nombres premiers XOR sont très similaires aux nombres premiers réguliers comme vous pouvez le voir par les définitions suivantes:

Définition du nombre premier: un nombre positif supérieur à 1 qui ne peut être formé par la multiplication de deux nombres que par la multiplication de 1 et de lui-même.

Définition de XOR Prime: Un nombre positif supérieur à 1 qui ne peut pas être formé par la multiplication XOR de deux nombres, sauf par la multiplication XOR de 1 et lui-même. Notez que les nombres premiers XOR composent la séquence Oeis A014580 .

La multiplication XOR est définie comme une multiplication binaire longue sans transport. Vous pouvez trouver plus d'informations sur la multiplication XOR dans le défi xnor .

Contribution:

Un entier n.

Production:

Les premiers nnombres XOR premiers.

Voici les nombres premiers XOR inférieurs à 500:

2 3 7 11 13 19 25 31 37 41 47 55 59 61 67 73 87 91 97 103 109 115 117 131 137 143 145 157 167 171 185 191 193 203 211 213 229 239 241 247 253 283 285 299 301 313 319 333 351 355 357 361 369 375 379 391 395 397 415 419 425 433 445 451 463 471 477 487 499

Pyth, 26 octets

.fq2/muxyG*Hhdjed2 0^SZ2ZQ

Manifestation

Pour tester si un nombre est un nombre XOR premier, nous générons la table de multiplication complète jusqu'à ce nombre en utilisant l'algorithme d' ici , puis comptons le nombre de fois où ce nombre apparaît. Si c'est exactement 2, le nombre est premier.

Ensuite, .fretourne les n premiers nombres premiers.

Mathematica, 100 99 octets

Comme l'a noté xnor, la multiplication XOR est juste une multiplication dans l'anneau polynomial $\mathbb{F}_2[x]$.

For[p=i=0,i<#,If[IrreduciblePolynomialQ[++p~IntegerDigits~2~FromDigits~x,Modulus->2],Print@p;i++]]&

Pari / GP , 74 octets

Enregistré 4 octets grâce à Charles .

Comme l'a noté xnor, la multiplication XOR est juste une multiplication dans l'anneau polynomial $\mathbb{F}_2[x]$.

n->p=0;while(n,if(polisirreducible(Mod(Pol(binary(p++)),2)),print(p);n--))

Essayez-le en ligne!

Fondamentalement, la même chose que ma réponse Mathematica , mais PARI / GP a des noms de fonction plus courts.

Ceylan, 166 octets

Bien sûr, cela ne peut pas rivaliser avec Pyth & Co ...

{Integer*}p(Integer n)=>loop(2)(1.plus).filter((m)=>{for(i in 2:m-2)for(j in 2:m-2)if(m==[for(k in 0:64)if(j.get(k))i*2^k].fold(0)((y,z)=>y.xor(z)))i}.empty).take(n);

Formaté:

{Integer*} p(Integer n) =>
        loop(2)(1.plus).filter((m) => {
            for (i in 2 : m-2)
                for (j in 2 : m-2)
                    if (m == [
                            for (k in 0:64)
                                if (j.get(k))
                                    i * 2^k
                        ].fold(0)((y, z) => y.xor(z))) i
        }.empty).take(n);

Cela crée un itérable infini d'entiers (commençant par 2), le filtre en vérifiant si un nombre est un nombre XOR premier et en prend les premiers néléments.

Ce filtrage fonctionne en bouclant sur tous les éléments de 2 à m-1 (qui sont m-2) et en vérifiant chaque paire si le produit xor donne m. Si l'itérable créé par celui-ci est vide, mest un xor-prime, et donc inclus.

Le produit xor lui-même est calculé en utilisant le même algorithme (et presque le même code) que dans ma réponse pour le calcul du produit XOR .

Julia, 116 octets

f(a,b)=b%2*a$(b>0&&f(2a,b÷2))
n->(A=[i=2];while endof(A)<n i+=1;i∈[f(a,b)for a=2:i-1,b=2:i-1]||push!(A,i)end;A[n])

La fonction principale est la fonction anonyme sur la deuxième ligne. Il appelle une fonction d'aide f(qui est d'ailleurs ma soumission pour le défi de xnor).

Non golfé:

function xor_mult(a::Integer, b::Integer)
    return b % 2 * a $ (b > 0 && f(2a, b÷2))
end

function xor_prime(n::Integer)
    # Initialize an array to hold the generated XOR primes as well as
    # an index at which to start the search
    A = [i = 2]

    # Loop while we've generated fewer than n XOR primes
    while endof(A) < n
        # Increment the prime candidate
        i += 1

        # If the number does not appear in the XOR multiplication
        # table of all numbers from 2 to n-1, it's an XOR prime
        i ∈ [xor_mult(a, b) for a in 2:i-1, b in 2:i-1] || push!(A, i)
    end

    # Return the nth XOR prime
    return A[n]
end