Nesse desafio proposto pelo xnor, fomos solicitados a implementar a multiplicação do XOR. Neste desafio, o objetivo é encontrar os primeiros nprimos XOR. Os primos XOR são muito semelhantes aos primos regulares, como você pode ver nas seguintes definições:

Definição de número primo: Um número positivo maior que 1 que não pode ser formado através da multiplicação de dois números, exceto pela multiplicação de 1 e ele próprio.

Definição de XOR Prime: Um número positivo maior que 1 que não pode ser formado através da multiplicação XOR de dois números, exceto através da multiplicação XOR de 1 e de si próprio. Observe que os primos XOR compõem a sequência de oeis A014580 .

A multiplicação XOR é definida como multiplicação longa binária sem carregar. Você pode encontrar mais informações sobre a multiplicação de XOR no desafio do xnor .

Entrada:

Um inteiro n.

Resultado:

O primeiro nXOR inicia.

Aqui estão os números primos do XOR abaixo 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

Pitão, 26 bytes

.fq2/muxyG*Hhdjed2 0^SZ2ZQ

Demonstração

Para testar se um número é XOR-prime, geramos a tabela de multiplicação completa até esse número usando o algoritmo daqui e, em seguida, contamos quantas vezes esse número aparece. Se for exatamente 2, o número é primo.

Em seguida, .fretorna os primeiros 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

Economizou 4 bytes graças a Charles .

$\mathbb{F}_2[x]$

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

Experimente online!

Basicamente, o mesmo que minha resposta do Mathematica , mas o PARI / GP possui nomes de funções mais curtos.

Ceilão, 166 bytes

Claro que isso não pode competir com a 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);

Formatado:

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

Isso cria um número iterável infinito de números inteiros (começando com 2), filtra-o verificando se um número é primo por XOR e leva o primeiro n elementos disso.

Essa filtragem funciona repetindo todos os elementos de 2 a m-1 (que são m-2) e verificando cada par se o xor-produto fornece m. Se o iterável criado por ele estiver vazio, mé um xor-prime e, portanto, está incluído.

O próprio produto xor é calculado usando o mesmo algoritmo (e quase o mesmo código) da minha resposta para o cálculo do produto 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])

A função principal é a função anônima na segunda linha. Ele chama uma função auxiliar f(que é incidentalmente minha submissão ao desafio do xnor).

Ungolfed:

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