Problem 242: Odd Triplets

Mathematical Development

Definition 1. For non-negative integers $a, b, c$, write $a = \sum_{i} a_i 2^i$, $b = \sum_i b_i 2^i$, $c = \sum_i c_i 2^i$ in binary. The XOR $a \oplus b \oplus c$ computes the bitwise sum modulo 2.

Theorem 1 (XOR-zero bit classification). Three non-negative integers satisfy $a \oplus b \oplus c = 0$ if and only if at every bit position $i$ the triple $(a_i, b_i, c_i)$ belongs to the set

Proof. The XOR of three bits equals zero if and only if an even number (0 or 2) of them are 1. These are precisely the four patterns listed. Since XOR operates independently at each bit position, the global condition $a \oplus b \oplus c = 0$ is equivalent to the local condition at every bit. $\blacksquare$

Lemma 1 (Bit-sum structure). If $a \oplus b \oplus c = 0$, then at each bit position $i$ the arithmetic sum $s_i = a_i + b_i + c_i \in \{0, 2\}$. Consequently:

In particular, $a + b + c$ is always even.

Proof. From the four valid patterns: $(0,0,0)$ sums to 0, and each of $(0,1,1)$, $(1,0,1)$, $(1,1,0)$ sums to 2. Writing $S = a + b + c = \sum_i s_i \cdot 2^i$ with $s_i \in \{0,2\}$, every term is divisible by 2, so $S$ is even. $\blacksquare$

Theorem 2 (Digit DP formulation). Write $N$ in binary as $N = \sum_{i=0}^{L} n_i \cdot 2^i$ with $n_i \in \{0,1\}$. We process bits from position $L$ (MSB) down to $0$ (LSB), maintaining the state $(\text{carry}, \text{tight}, \text{ord}_{ab}, \text{ord}_{bc})$ where:

At each bit position $i$, we enumerate the four patterns in $\mathcal{V}$. For pattern with bit-sum $s_i \in \{0, 2\}$, the digit of $a + b + c$ at position $i$ is $(s_i + \text{carry}) \bmod 2$, with new carry $\lfloor(s_i + \text{carry})/2\rfloor$.

Proof of correctness. We establish a bijection between valid triplets $(a, b, c)$ and accepting paths through the DP automaton.

(i) State transitions are exhaustive. At each bit, we try all four valid XOR-zero patterns, which is the complete set by Theorem 1.

(ii) Ordering is maintained exactly. If $\text{ord}_{ab} = {=}$ (meaning $a = b$ on all higher bits), the pattern must satisfy $a_i \le b_i$ to preserve $a \le b$. If $a_i < b_i$, the ordering transitions to $\text{ord}_{ab} = {<}$, after which any $(a_i, b_i)$ is permitted (since $a < b$ is already established). Analogously for $\text{ord}_{bc}$.

(iii) Sum constraint is correct. The carry-based representation computes $a + b + c$ digit by digit. Tightness tracks whether the partial sum can still equal $N$ at higher bits; once a digit of $a + b + c$ falls strictly below the corresponding digit of $N$, all subsequent bits are unconstrained.

(iv) Termination. At $i = -1$, accept if and only if $\text{carry} = 0$ (no overflow beyond the MSB). $\blacksquare$

Remark. The total state space has $|\{0,1\}| \times |\{0,1\}| \times |\{=,<\}| \times |\{=,<\}| = 16$ states per bit position. With $L + 1 \approx 40$ bit positions and 4 patterns per state, the DP evaluates at most $16 \times 4 \times 40 = 2560$ transitions.

Editorial

Count triplets (a,b,c) with 0 < a <= b <= c, a+b+c <= N, a XOR b XOR c = 0. N = 10^12, answer mod 10^9. Digit DP on the binary representation of N. XOR-zero constraint: at each bit, (a_i, b_i, c_i) in {(0,0,0),(0,1,1),(1,0,1),(1,1,0)}. State: (bit position, carry, tight, ordering of a<=b and b<=c). We enforce a <= b. We then enforce b <= c. Finally, update ordering.

Pseudocode

Enforce a <= b
Enforce b <= c
Update ordering
Compute sum digit and carry
Update tightness
if tight
else
Accept states with carry = 0

Complexity Analysis

• Time. $O(L \cdot |S| \cdot |\mathcal{V}|)$ where $L = \lceil \log_2 N \rceil \approx 40$, $|S| = 16$ states, $|\mathcal{V}| = 4$ patterns. Total: $O(2560)$ transitions — effectively constant.
• Space. $O(|S|) = O(16) = O(1)$.

Answer

/*
 * Project Euler Problem 242: Odd Triplets
 *
 * Count triplets (a,b,c) with 0 < a <= b <= c, a+b+c <= N, a^b^c = 0.
 * N = 10^12, answer mod 10^9.
 *
 * Digit DP on the binary representation of N.
 * Valid bit patterns: (0,0,0), (0,1,1), (1,0,1), (1,1,0).
 * State: (bit position, carry, tight, ordering).
 */

#include <bits/stdc++.h>
using namespace std;

static const long long MOD = 1000000000LL;

int bits[50];
int nbits;
map<tuple<int,int,int,int>, long long> memo;

int patterns[4][3] = {{0,0,0},{0,1,1},{1,0,1},{1,1,0}};

long long solve(int pos, int carry, int tight, int order) {
    if (pos < 0)
        return carry == 0 ? 1 : 0;

    auto key = make_tuple(pos, carry, tight, order);
    auto it = memo.find(key);
    if (it != memo.end()) return it->second;

    long long result = 0;
    int n_bit = bits[pos];

    for (int p = 0; p < 4; p++) {
        int ai = patterns[p][0], bi = patterns[p][1], ci = patterns[p][2];

        bool a_eq_b = (order == 0 || order == 1);
        bool b_eq_c = (order == 0 || order == 2);

        if (a_eq_b && ai > bi) continue;
        if (b_eq_c && bi > ci) continue;

        bool new_a_lt_b = (order == 2 || order == 3) || (ai < bi);
        bool new_b_lt_c = (order == 1 || order == 3) || (bi < ci);

        int new_order;
        if (!new_a_lt_b && !new_b_lt_c) new_order = 0;
        else if (!new_a_lt_b && new_b_lt_c) new_order = 1;
        else if (new_a_lt_b && !new_b_lt_c) new_order = 2;
        else new_order = 3;

        int s = ai + bi + ci + carry;
        int sum_bit = s % 2;
        int new_carry = s / 2;

        int new_tight;
        if (tight) {
            if (sum_bit > n_bit) continue;
            new_tight = (sum_bit == n_bit) ? 1 : 0;
        } else {
            new_tight = 0;
        }

        result = (result + solve(pos - 1, new_carry, new_tight, new_order)) % MOD;
    }

    memo[key] = result;
    return result;
}

int main() {
    ios_base::sync_with_stdio(false);

    long long N_val = 1000000000000LL;
    nbits = 0;
    long long tmp = N_val;
    while (tmp > 0) {
        bits[nbits++] = tmp & 1;
        tmp >>= 1;
    }

    long long ans = solve(nbits - 1, 0, 1, 0);
    ans = (ans - 1 + MOD) % MOD;
    cout << ans << endl;
    return 0;
}

"""
Project Euler Problem 242: Odd Triplets

Count triplets (a,b,c) with 0 < a <= b <= c, a+b+c <= N, a XOR b XOR c = 0.
N = 10^12, answer mod 10^9.

Digit DP on the binary representation of N.
XOR-zero constraint: at each bit, (a_i, b_i, c_i) in {(0,0,0),(0,1,1),(1,0,1),(1,1,0)}.
State: (bit position, carry, tight, ordering of a<=b and b<=c).
"""

import functools

MOD = 10**9
N = 10**12

bits = []
tmp = N
while tmp > 0:
    bits.append(tmp & 1)
    tmp >>= 1
nbits = len(bits)

patterns = [(0, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0)]


@functools.lru_cache(maxsize=None)
def solve(pos, carry, tight, order):
    if pos < 0:
        return 1 if carry == 0 else 0

    result = 0
    n_bit = bits[pos]

    for ai, bi, ci in patterns:
        a_eq_b = order in (0, 1)
        b_eq_c = order in (0, 2)

        if a_eq_b and ai > bi:
            continue
        if b_eq_c and bi > ci:
            continue

        new_a_lt_b = (order in (2, 3)) or (ai < bi)
        new_b_lt_c = (order in (1, 3)) or (bi < ci)

        new_order = 0
        if not new_a_lt_b and new_b_lt_c:
            new_order = 1
        elif new_a_lt_b and not new_b_lt_c:
            new_order = 2
        elif new_a_lt_b and new_b_lt_c:
            new_order = 3

        s = ai + bi + ci + carry
        sum_bit = s % 2
        new_carry = s // 2

        if tight:
            if sum_bit > n_bit:
                continue
            new_tight = 1 if sum_bit == n_bit else 0
        else:
            new_tight = 0

        result += solve(pos - 1, new_carry, new_tight, new_order)

    return result % MOD


ans = solve(nbits - 1, 0, 1, 0)
ans = (ans - 1) % MOD
print(ans)