Problem 301: Nim

Project Euler Problem 301 Solution

EulerSolve provides an optimized solution for Project Euler Problem 301, Nim, with C++, Python, Java, and a step-by-step mathematical explanation.

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$....

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.

Problem 301 source code

C++

#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

using u64 = std::uint64_t;

struct Options {
    int exponent = 30;  // n <= 2^exponent
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--exponent=", options.exponent)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.exponent >= 1 && options.exponent <= 60;
}

u64 solve(const int exponent) {
    const int bits = exponent + 1;
    std::vector<u64> fib(static_cast<std::size_t>(bits + 2), 0ULL);
    fib[1] = 1ULL;
    for (int i = 2; i <= bits + 1; ++i) {
        fib[static_cast<std::size_t>(i)] =
            fib[static_cast<std::size_t>(i - 1)] + fib[static_cast<std::size_t>(i - 2)];
    }

    // Count of n in [1, 2^exponent] with no adjacent 1 bits.
    return fib[static_cast<std::size_t>(bits + 1)];
}

u64 brute_small(const int exponent) {
    const u64 limit = 1ULL << exponent;
    u64 count = 0;
    for (u64 n = 1; n <= limit; ++n) {
        if ((n ^ (2ULL * n) ^ (3ULL * n)) == 0ULL) {
            ++count;
        }
    }
    return count;
}

bool run_checkpoints() {
    if (solve(3) != brute_small(3)) {
        std::cerr << "Checkpoint failed for exponent=3" << '\n';
        return false;
    }
    if (solve(10) != brute_small(10)) {
        std::cerr << "Checkpoint failed for exponent=10" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }
    std::cout << solve(options.exponent) << '\n';
    return 0;
}

Python

def solve(exponent=30):
    bits = exponent + 1
    fib = [0] * (bits + 2)
    fib[1] = 1
    for i in range(2, bits + 2):
        fib[i] = fib[i - 1] + fib[i - 2]
    return str(fib[bits + 1])

if __name__ == '__main__':
    print(solve())

Java

public class Euler301 {
    public static String solve() {
        int exponent = 30;
        int bits = exponent + 1;
        long[] fib = new long[bits + 2];
        fib[1] = 1L;
        for (int i = 2; i <= bits + 1; ++i) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
        return String.valueOf(fib[bits + 1]);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}