Project Euler Problem 301

Project Euler Problem 301

Solution

Answer: 2178309

For normal-play Nim, the winning/losing condition is completely characterized by the nim-sum (bitwise XOR of heap sizes).

A position $(n_1,n_2,n_3)$ is losing iff

$$n_1 \oplus n_2 \oplus n_3 = 0.$$

So we want the number of positive integers $n \le 2^{30}$ such that

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

The key is to simplify this bitwise condition.

---

1. Mathematical analysis

The Nim losing condition gives:

$$X(n,2n,3n)=0 \iff n\oplus 2n\oplus 3n = 0.$$

Now observe:

$$3n = n + 2n.$$

A useful bitwise identity is:

$$a+b = (a\oplus b) + 2(a&b).$$

Thus:

$$a\oplus b = a+b \quad\Longleftrightarrow\quad a&b = 0.$$

Apply this with $a=n$, $b=2n$.

If

$$n\oplus 2n = 3n,$$

then

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

Since $3n=n+2n$, this happens exactly when there are no carries in the binary addition $n+2n$, i.e.

$$n&2n = 0.$$

But multiplying by 2 is just a left shift:

$$2n = n \ll 1.$$

Therefore:

$$n & (n\ll1)=0.$$

This means:

No two adjacent bits of $n$ may both be 1.

So the problem becomes:

Count integers $1\le n\le 2^{30}$ whose binary representation contains no consecutive 1s.

---

Fibonacci structure

Let $f(k)$ be the number of binary strings of length $k$ with no adjacent 1s.

Split by first bit:

• Starts with 0: $f(k-1)$
• Starts with 10: $f(k-2)$

Hence:

$$f(k)=f(k-1)+f(k-2),$$

the Fibonacci recurrence.

With:

$$f(0)=1,\qquad f(1)=2$$

we get:

$$f(k)=F_{k+2},$$

where $F_1=1,F_2=1$.

Now consider numbers $0\le n<2^{30}$. These correspond exactly to binary strings of length at most 30, so the count is

$$F_{32}.$$

But our range is

$$1\le n\le 2^{30}.$$

Notice:

• $n=0$ is included in $F_{32}$ count but must be excluded.
• $n=2^{30}$ (binary $1000\ldots0$) is valid and must be included.

These cancel exactly.

So the final count remains:

$$F_{32}.$$

Compute:

$$F_{32}=2178309.$$

---

2. Python implementation

def solve(limit_power=30):
    # We need F_(limit_power + 2)
    # Fibonacci with F1 = 1, F2 = 1

    a, b = 1, 1  # F1, F2

    # Compute F32 for limit_power = 30
    target = limit_power + 2

    for _ in range(3, target + 1):
        a, b = b, a + b

    return b

print(solve())

---

3. Code walkthrough

a, b = 1, 1

Initialize Fibonacci numbers:

$$F_1=1,\quad F_2=1.$$

target = limit_power + 2

For $2^{30}$, we need:

$$F_{30+2}=F_{32}.$$

for _ in range(3, target + 1):
    a, b = b, a + b

Standard iterative Fibonacci computation.

After the loop:

return b

returns $F_{32}$.

Small sanity check

Example from the statement:

$$(1,2,3)$$

Binary:

• $1=001$
• $2=010$
• $3=011$

XOR:

$$1\oplus2\oplus3=0$$

So $X(1,2,3)=0$, matching the problem statement.

Check a few $n$:

• $n=1$: binary 1 → valid
• $n=2$: binary 10 → valid
• $n=3$: binary 11 → invalid (adjacent ones)
• $n=5$: binary 101 → valid
• $n=6$: binary 110 → invalid

Exactly the “no consecutive 1s” rule.

---

4. Final verification

The answer should be around Fibonacci growth:

$$F_{32}\approx 2.1\times10^6,$$

which is plausible given there are $2^{30}\approx10^9$ candidates and valid bitstrings without consecutive 1s are exponentially sparse.

The cancellation of excluding $0$ and including $2^{30}$ is an important edge case and confirms the count remains exactly $F_{32}$.

Answer: 2178309