W tym wyzwaniu postawionym przez xnor poproszono nas o wdrożenie mnożenia XOR. W tym wyzwaniu celem jest znalezienie pierwszych nliczb pierwszych XOR. Liczby pierwsze XOR są bardzo podobne do liczb pierwszych regularnych, co widać po następujących definicjach:

Definicja liczby pierwszej: Liczba dodatnia większa niż 1, której nie można utworzyć przez pomnożenie dwóch liczb, z wyjątkiem pomnożenia 1 i samego siebie.

Definicja XOR Prime: Liczba dodatnia większa niż 1, której nie można utworzyć przez pomnożenie przez XOR dwóch liczb, z wyjątkiem pomnożenia przez XOR 1 i samego siebie. Należy zauważyć, że liczby pierwsze XOR składają się na sekwencję Oeis A014580 .

Mnożenie XOR jest definiowane jako binarne długie mnożenie bez przenoszenia. Więcej informacji na temat mnożenia XOR znajdziesz w wyzwaniu xnor .

Wejście:

Liczba całkowita n.

Wynik:

Pierwsze nliczby pierwsze XOR.

Oto liczby pierwsze XOR poniżej 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 bajtów

.fq2/muxyG*Hhdjed2 0^SZ2ZQ

Demonstracja

Aby sprawdzić, czy liczba jest liczbą pierwszą XOR, generujemy pełną tabliczkę mnożenia do tej liczby za pomocą algorytmu z tego miejsca , a następnie zliczamy, ile razy ta liczba się pojawia. Jeśli to dokładnie 2, liczba jest liczbą pierwszą.

Następnie .fzwraca pierwsze n liczb pierwszych.

Mathematica, 100 99 bajtów

$\mathbb{F}_2[x]$

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

Pari / GP , 74 bajty

Zaoszczędź 4 bajty dzięki Charlesowi .

$\mathbb{F}_2[x]$

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

Wypróbuj online!

Zasadniczo to samo, co moja odpowiedź Mathematica , ale PARI / GP ma krótsze nazwy funkcji.

Ceylon, 166 bajtów

Oczywiście to nie może konkurować z 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);

Sformatowany:

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

Tworzy to nieskończoną iterowalną liczbę całkowitą (zaczynając od 2), filtruje ją, sprawdzając, czy liczba jest liczbą pierwszą XOR, i bierze jej pierwsze nelementy.

Filtrowanie to polega na zapętlaniu wszystkich elementów od 2 do m-1 (które są m-2) i sprawdzaniu każdej pary, czy daje wynik xor m. Jeśli iterowalność utworzona przez to jest pusta, mjest liczbą pierwszą xor i dlatego została uwzględniona.

Sam produkt xor jest obliczany przy użyciu tego samego algorytmu (i prawie tego samego kodu), co w mojej odpowiedzi dla obliczenia produktu XOR .

Julia, 116 bajtów

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

Podstawową funkcją jest anonimowa funkcja w drugim wierszu. Wywołuje funkcję pomocnika f(która jest zresztą moim poddaniem się na wyzwanie xnora).

Nie golfowany:

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