XOR-Primes

We use $x\oplus y$ for the bitwise XOR of $x$ and $y$.
Define the XOR-product of $x$ and $y$, denoted by $x \otimes y$, similar to a long multiplication in base $2$, except that the intermediate results are XORed instead of the usual integer addition.
For example, $7 \otimes 3 = 9$, or in base $2$, $111_2 \otimes 11_2 = 1001_2$:
$$
\begin{align*}
\phantom{\otimes 111} 111_2 \\
\otimes \phantom{1111} 11_2 \\
\hline
\phantom{\otimes 111} 111_2 \\
\oplus \phantom{11} 111_2 \phantom{9} \\
\hline
\phantom{\otimes 11} 1001_2 \\
\end{align*}
$$

An XOR-prime is an integer $n$ greater than $1$ that is not an XOR-product of two integers greater than $1$. The above example shows that $9$ is not an XOR-prime. Similarly, $5 = 3 \otimes 3$ is not an XOR-prime. The first few XOR-primes are $2, 3, 7, 11, 13, …$ and the 10th XOR-prime is $41$.
Find the $5\,000\,000$th XOR-prime.

To solve this problem, we need to handle it programmatically via pseudo code since it’s not feasible to solve by hand due to the large number – 5,000,000.

Let’s define a pseudo code to solve it:

“`ruby
XOR_Primes = []
i = 2

while XOR_Primes.length < 5000000 isXOR_Prime = True for j in range(2, i-1): if i % j == 0: isXOR_Prime = False break if isXOR_Prime: for x in XOR_Primes: for y in XOR_Primes: if x * y == i: isXOR_Prime = False break if not isXOR_Prime: break if isXOR_Prime: XOR_Primes.append(i) i += 1 print(XOR_Primes[-1]) ``` This pseudo code in essence creates an array to hold our XOR-primes, which starts with 2. Then, it continues to loop as long as we still haven't found the 5,000,000th XOR-prime. For each number, it checks to see if it's a prime number. If it is, it additionally checks to see if it's an XOR-prime. It does this by iterating through all XOR-primes we've found so far and checking if any XORed number equals current value, in which case it's not an XOR-prime. If after all these checks, a number is still considered an XOR-prime, it's added to our array, until we find the 5,000,000th XOR-prime. Remember that, pseudo code needs to be translated into real programming code. Also, some optimizations could be added such as using sieve of Eratosthene or bitwise operations to enhance the performance due to large amount of required computations. The above explanation and pseudo code provides a general guideline on how to approach this problem.

More Answers: