En este desafío planteado por xnor, se nos pidió implementar la multiplicación XOR. En este desafío, el objetivo es encontrar los primeros nprimos XOR. Los primos XOR son muy similares a los primos regulares como se puede ver en las siguientes definiciones:

Definición de número primo: un número positivo mayor que 1 que no puede formarse mediante la multiplicación de dos números, excepto mediante la multiplicación de 1 y de sí mismo.

Definición de XOR Prime: un número positivo mayor que 1 que no se puede formar a través de la multiplicación XOR de dos números, excepto a través de la multiplicación XOR de 1 y de sí mismo. Tenga en cuenta que los primos XOR componen la secuencia oeis A014580 .

La multiplicación XOR se define como la multiplicación binaria larga sin llevar. Puedes encontrar más información sobre la multiplicación de XOR en el desafío de xnor .

Entrada:

Un entero n.

Salida:

Los primeros nprimos XOR.

Aquí están los primos XOR por debajo de 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 bytes

.fq2/muxyG*Hhdjed2 0^SZ2ZQ

Demostración

Para probar si un número es un XOR-primo, generamos la tabla de multiplicación completa hasta ese número usando el algoritmo de aquí , y luego contamos cuántas veces aparece ese número. Si es exactamente 2, el número es primo.

Luego, .fdevuelve los primeros n primos.

Mathematica, 100 99 bytes

$\mathbb{F}_2[x]$

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

Pari / GP , 74 bytes

Guardado 4 bytes gracias a Charles .

Como señaló xnor, la multiplicación XOR es solo multiplicación en el anillo polinómico $\mathbb{F}_2[x]$.

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

Pruébalo en línea!

Básicamente lo mismo que mi respuesta de Mathematica , pero PARI / GP tiene nombres de funciones más cortos.

Ceilán, 166 bytes

Por supuesto, esto no puede competir con 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);

Formateado:

{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);

Esto crea un número infinito de enteros (comenzando con 2), lo filtra comprobando si un número es un XOR-primo y toma los primeros nelementos de ese número.

Este filtrado funciona haciendo un bucle sobre todos los elementos de 2 a m-1 (que son m-2), y verificando cada par si el producto xor da m. Si el iterable creado por eso está vacío, mes un xor-prime y, por lo tanto, está incluido.

El producto xor en sí mismo se calcula utilizando el mismo algoritmo (y casi el mismo código) que en mi respuesta para el cálculo del producto XOR .

Julia, 116 bytes

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 función principal es la función anónima en la segunda línea. Llama a una función auxiliar f(que, por cierto, es mi sumisión para el desafío de xnor).

Sin 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