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