16
\$\begingroup\$

In this challenge posed by xnor, we were asked to implement XOR multiplication. In this challenge the goal is to find the first n XOR primes. XOR primes are very similar to regular primes as you can see by the following definitions:

Definition of Prime Number: A positive number greater than 1 which cannot be formed through multiplication of two numbers except through the multiplication of 1 and itself.

Definition of XOR Prime: A positive number greater than 1 which cannot be formed through XOR multiplication of two numbers except through the XOR multiplication of 1 and itself. Note that the XOR primes compose oeis sequence A014580.

XOR multiplication is defined as binary long multiplication without carrying. You can find more information about XOR multiplication in xnor's challenge.

Input:

An integer n.

Output:

The first n XOR primes.

Here are the XOR primes under 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
\$\endgroup\$
  • 7
    \$\begingroup\$ FWIW these are the prime elements of the unique factorisation domain F_2[x]. \$\endgroup\$ – Peter Taylor Dec 17 '15 at 19:41
  • \$\begingroup\$ Uhm what exactly is the challenge? Shortest code? Fastest code? \$\endgroup\$ – Eumel Dec 17 '15 at 21:46
  • 2
    \$\begingroup\$ @Eumel The tag is code-golf, so shortest code in bytes is the default. \$\endgroup\$ – Mego Dec 17 '15 at 22:00
  • 4
    \$\begingroup\$ OEIS A014580 \$\endgroup\$ – xnor Dec 18 '15 at 4:58
5
\$\begingroup\$

Pyth, 26 bytes

.fq2/muxyG*Hhdjed2 0^SZ2ZQ

Demonstration

To test whether a number is a XOR-prime, we generate the complete multiplication table up to that number using the algorithm from here, and then count how many times that number appears. If it's exactly 2, the number is prime.

Then, .f returns the first n primes.

\$\endgroup\$
2
\$\begingroup\$

Mathematica, 100 99 bytes

As noted by xnor, XOR multiplication is just multiplication in the polynomial ring \$\mathbb{F}_2[x]\$.

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

Pari/GP, 74 bytes

Saved 4 bytes thanks to Charles.

As noted by xnor, XOR multiplication is just multiplication in the polynomial ring \$\mathbb{F}_2[x]\$.

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

Try it online!

Basically the same as my Mathematica answer, but PARI/GP has shorter function names.

\$\endgroup\$
  • 1
    \$\begingroup\$ Nice, an improvement on the version at A014580. You can shave off 4 bytes if you decrement instead: n->p=0;while(n,if(polisirreducible(Mod(Pol(binary(p++)),2)),print(p);n--)). \$\endgroup\$ – Charles Feb 3 '16 at 21:38
1
\$\begingroup\$

Ceylon, 166 bytes

Of course this can't compete with 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);

Formatted:

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

This creates an infinite iterable of integers (starting with 2), filters it by checking if a number is an XOR-prime, and takes the first n elements of that.

This filtering works by looping over all elements from 2 to m-1 (which are m-2 ones), and checking each pair if the xor-product give m. If the iterable created by that is empty, m is an xor-prime, and therefore included.

The xor-product itself is calculated using the same algorithm (and almost the same code) as in my answer for the XOR product calculation.

\$\endgroup\$
1
\$\begingroup\$

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

The primary function is the anonymous function on the second line. It calls a helper function f (which is incidentally my submission for xnor's challenge).

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.