← Complete problem index

PROJECT EULER · #0810

XOR-Primes

Statement only · SolvedOriginal problem ↗

We use x⊕y for the bitwise XOR of x and y.

Define the XOR-product of x and y, denoted by x⊗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⊗3=9, or in base 2, 1112⊗112=10012:

⊗1111112⊗1111112⊗1111112⊕1111129⊗1110012

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⊗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 5000000th XOR-prime.

Write-up coming later

The complete problem is available here. An approach, code, and answer will be added later.