Project Euler Problem 242

Solution

Answer: 997104142249036713

Let

$$f(n,k)=#\left{A\subseteq {1,2,\dots,n}:\ |A|=k,\ \sum_{a\in A} a \text{ is odd}\right}.$$

We seek the number of triples

$$[n,k,f(n,k)]$$

such that all three quantities are odd, with $n\le 10^{12}$.

---

Step 1 — Express $f(n,k)$

Among $1,2,\dots,n$:

• the odd numbers contribute odd parity,
• the even numbers contribute even parity.

A subset has odd sum iff it contains an odd number of odd elements.

---

Case analysis on $n$

Write:

• $o=#\text{odd numbers}$,
• $e=#\text{even numbers}$.

Then

$$f(n,k)=\sum_{\substack{j\ \text{odd}}} \binom{o}{j}\binom{e}{k-j}.$$

We only care about parity (odd/even).

---

Step 2 — Reduce modulo 2

We now work modulo $2$.

A standard identity is

$$(1+x)^{2m}\equiv (1+x^2)^m \pmod 2,$$

because all middle binomial coefficients are even.

Similarly,

$$(1+x)^{2m+1}\equiv (1+x)(1+x^2)^m \pmod 2.$$

---

Step 3 — Separate the two congruence classes of $n$

Since $n$ itself must be odd, write either

$$n=4r+1 \quad\text{or}\quad n=4r+3.$$

Also $k$ must be odd.

---

Case A: $n=4r+1$

Then:

• number of odd integers = $2r+1$,
• number of even integers = $2r$.

Write

$$k=4s+1 \quad\text{or}\quad k=4s+3.$$

The odd-coefficient part of

$$(1+x)^{2r+1}$$

modulo $2$ is

$$x(1+x^2)^r.$$

The even-number generating polynomial is

$$(1+x)^{2r}\equiv (1+x^2)^r.$$

Therefore,

$$f(4r+1,k) \equiv [x^k], x(1+x^2)^{2r} \pmod 2.$$

But

$$(1+x^2)^{2r}\equiv (1+x^4)^r \pmod2.$$

Hence

$$f(4r+1,k) \equiv x^{k-1}^r.$$

This coefficient is nonzero only when $k-1$ is divisible by $4$, i.e.

$$k=4s+1.$$

Then

$$f(4r+1,4s+1) \equiv \binom{r}{s} \pmod2.$$

So:

$$f(4r+1,4s+1)\text{ is odd} \iff \binom{r}{s}\text{ is odd}.$$

---

Case B: $n=4r+3$

Now:

• odds = $2r+2$,
• evens = $2r+1$.

A similar calculation gives

$$f(4r+3,k)\equiv 0 \pmod2$$

for every odd $k$.

So no odd-triplets occur when $n\equiv 3\pmod4$.

---

Step 4 — Count odd binomial coefficients

Thus every odd-triplet corresponds exactly to:

$$n=4r+1,\qquad k=4s+1,$$

with

$$\binom{r}{s}\ \text{odd}.$$

---

Lucas' theorem

A binomial coefficient is odd iff every binary digit of $s$ is at most the corresponding digit of $r$.

Equivalently:

$$s \subseteq r \quad\text{bitwise}.$$

If $r$ has $t$ ones in binary, then each 1-bit may independently be:

• used in $s$,
• or not used.

Therefore the number of odd coefficients in row $r$ is

$$2^{\operatorname{popcount}(r)}.$$

---

Step 5 — Final summation

We need

$$4r+1\le 10^{12}.$$

Hence

$$r\le \frac{10^{12}-1}{4}=249999999999.$$

So the answer is

$$\sum_{r=0}^{249999999999} 2^{\operatorname{popcount}(r)}.$$

---

Step 6 — Evaluate the sum

Define

$$S(N)=\sum_{r=0}^{N}2^{\operatorname{popcount}(r)}.$$

A standard binary DP gives:

If the highest remaining bit position is $m$, then all smaller numbers contribute

$$(1+2)^m = 3^m.$$

Processing the bits of $N$ from top to bottom yields the exact value.

---

Python implementation

def count_odd_triplets(limit):
    # Largest r such that 4r + 1 <= limit
    R = (limit - 1) // 4

    # Computes:
    # S(R) = sum_{r=0}^R 2^(popcount(r))
    ans = 0

    bits = bin(R)[2:]

    # Number of 1-bits already fixed in the prefix
    ones_so_far = 0

    for i, b in enumerate(bits):
        remaining = len(bits) - i - 1

        if b == '1':
            # Put 0 here instead of 1.
            # Remaining bits are arbitrary.
            #
            # Each remaining bit contributes factor:
            #   1 (bit = 0)
            #   2 (bit = 1)
            #
            # so total factor is 3^remaining.
            ans += (2 ** ones_so_far) * (3 ** remaining)

            # Continue along the actual prefix with this bit = 1
            ones_so_far += 1

    # Include R itself
    ans += 2 ** ones_so_far

    return ans

print(count_odd_triplets(10))       # should be 5
print(count_odd_triplets(10**12))

---

Code walkthrough

1. Convert the problem

We proved the answer equals

$$\sum_{r=0}^{R}2^{\operatorname{popcount}(r)},$$

where

$$R=\frac{10^{12}-1}{4}.$$

---

2. Binary digit DP

Suppose we process bits from left to right.

Whenever the current bit of $R$ is 1:

• we may place a 0 there,
• then the remaining bits are free.

For each free bit:

• choosing 0 contributes factor $1$,
• choosing 1 contributes factor $2$.

So each free bit contributes $1+2=3$.

Hence a block of $m$ free bits contributes $3^m$.

---

3. Complexity

The algorithm uses only the binary length of $R$:

$$O(\log R).$$

For $R<2^{38}$, this is tiny.

---

Verification on the sample

For $n\le 10$:

$$R=\left\lfloor \frac{10-1}{4}\right\rfloor=2.$$

Then

$$2^{\operatorname{popcount}(0)} + 2^{\operatorname{popcount}(1)} + 2^{\operatorname{popcount}(2)} = 1+2+2=5.$$

Exactly the five triplets listed in the problem statement.

---

Final computation

$$\sum_{r=0}^{249999999999} 2^{\operatorname{popcount}(r)} = 997104142249036713.$$

---

Answer: 997104142249036713