Project Euler 301 - Nim

Official link: https://projecteuler.net/problem=301

Thought Process

A quick google search of Nim, quickly defines the function X in the problem it is called Nim-Sum and what it does if it takes 2 number in binary and cancels "overlapping" 1's. I have given 2 examples below.

Please note that in python this function is called bitwise XOR and is denoted by the ^ symbol, as such ^ will represent bitwise XOR and ** will represent to the power in this explanation!

  1. 5 + 2

    • 1 0 1 (base 2) = 5

    • ^ 0 1 0 (base 2) = 2

    • = 1 1 1 (base 2) = 7 (Here there are no "overlapping" 1's so we add them all up)

  2. 5 + 7

    • 1 0 1 (base 2) = 5

    • ^ 1 1 1 (base 2) = 7

    • = 0 1 0 (base 2) = 2 (Here there are 2 "overlapping" 1's so we cancel them)

Now we can notice a few fairly obvious facts:

  1. n+2n = 3n

    • Obviously

  2. a^b = 0 iff a=b

    • Think about it, 2 numbers can only cancel themselves completely if they are the same number

  3. n + an extra 0 at the end = 2n in base 2

    • Because if n = 2**k + ... + 2**1 + 2**0 => 2n = 2**(k+1) + ... + 2**2 + 2**1, we can see in base 2, 2n is exactly the same as n except we have 0*(2**0) which is the extra 0

    • an example: n = 10 (base 2) = 2, 2n = 100 (base 2) = 4

The objective of this problem is to find all n such that n^2n^3n = 0 => (n^2n)^3n = 0, from point 2 above this implies that n^2n = 3n = 2n + n, now we derive the key fact which will solve the problem for us.

Notice that if n has consecutive 1's in its base 2 representation then n + 2n will increase in digit length by 1 but n^2n will stay the same digit length!

  1. Here is an example to showcase the above

    • n: 0 1 1 0 1 1

    • 2n: + 1 1 0 ^ 1 1 0

    • n+2n: = 1 0 0 1 = 1 0 1

So this entire problem is reduced to find all n that do not have consecutive 1's in it's base 2 representation! I recommend you stop here and solve the rest yourself as the next fact I will introduce instantly solves the problem

Interactive Code

Enter an integer (yourinput)

Code will output the number of n <= 2**yourinput such that n^2n^3n = 0