Detailed mathematical approach

Problem Summary

The title refers to a three-heap Nim position with heap sizes

$n,\qquad 2n,\qquad 3n.$

In Nim, a position is losing for the next player exactly when the xor of the heap sizes is zero. So we must count the integers \(n\) with

$1\le n\le 2^k,\qquad n\oplus 2n\oplus 3n=0.$

Mathematical Approach

1. Convert the Nim condition into a carry condition

Since

$3n=n+2n,$

the xor condition becomes

$n\oplus 2n\oplus (n+2n)=0.$

Now recall the binary identity

$a\oplus b=a+b \iff a\land b=0,$

which says that xor equals ordinary addition exactly when no carry occurs. Therefore

$n\oplus 2n\oplus 3n=0 \iff n\oplus 2n = n+2n \iff n\land 2n = 0.$

So the whole problem is reduced to asking when the binary expansions of \(n\) and \(2n\) overlap.

2. Why this means “no adjacent 1-bits”

Multiplying by \(2\) is just a left shift:

$2n = n \ll 1.$

Thus the bitwise condition

$n\land 2n = 0$

means that no 1-bit of \(n\) may sit immediately next to another 1-bit, because a bit at position \(i\) in \(n\) overlaps with a bit at position \(i+1\) after shifting. Hence

$n\oplus 2n\oplus 3n=0$

if and only if the binary representation of \(n\) contains no substring \(11\).

3. Small example

Take \(n=5\). In binary,

$5=101_2,\qquad 10=1010_2,\qquad 15=1111_2.$

Because \(101\) has no adjacent 1s, the carry-free condition holds, and indeed

$5\oplus 10\oplus 15=0.$

Now take \(n=6\):

$6=110_2.$

This contains adjacent 1s, so \(6+12\) has a carry, and correspondingly

$6\oplus 12\oplus 18\ne 0.$

4. Counting binary strings with no consecutive ones

Let \(A_t\) be the number of binary strings of length \(t\) with no adjacent 1s. There are two cases:

Ending in 0. Then the first \(t-1\) bits form any valid length-\((t-1)\) string.

Ending in 1. Then the previous bit must be 0, and the first \(t-2\) bits form any valid length-\((t-2)\) string.

Therefore

$A_t=A_{t-1}+A_{t-2},$

with initial values

$A_0=1,\qquad A_1=2.$

So \(A_t\) is a Fibonacci count. If we use the convention

$F_1=1,\qquad F_2=1,\qquad F_{m}=F_{m-1}+F_{m-2},$

then

$A_t=F_{t+2}.$

5. Why the answer for \([1,2^k]\) is still one Fibonacci number

The count \(A_k\) describes valid \(k\)-bit strings, which is the same as valid integers in the half-open range

$0\le n<2^k.$

But the problem asks for

$1\le n\le 2^k.$

This changes the set in a very simple way: we remove \(0\), but we add \(2^k\), whose binary form is

$1000\cdots 0,$

and that number is also valid because it clearly has no adjacent 1s. So the count does not change at all. Hence the final answer is

$A_k=F_{k+2}.$

The implementation sets bits = exponent + 1 and returns the corresponding Fibonacci entry, which is exactly this value.

6. Checkpoints

For \(k=3\), the valid values are

$1,2,4,5,8,$

so the count is

$5=F_5.$

For the C++ checkpoint,

$k=10 \Rightarrow F_{12}=144.$

For the actual Project Euler target,

$k=30 \Rightarrow F_{32}=2178309.$

How the Code Works

The solver does not test any \(n\) individually. It simply builds Fibonacci numbers up to index \(k+2\) and returns that value. The brute-force checks in the C++ version for small exponents confirm that this combinatorial count exactly matches the xor definition.

Complexity Analysis

The runtime is

$O(k),$

and memory is also \(O(k)\) in the current implementation, though it could be reduced to \(O(1)\) with two rolling Fibonacci variables. This is exponentially better than checking all \(2^k\) candidates.

Further Reading

1. Problem page: https://projecteuler.net/problem=301
2. Nim and xor: https://en.wikipedia.org/wiki/Nim
3. Fibonacci counting of binary strings: https://en.wikipedia.org/wiki/Fibonacci_number