Problem 242: Odd Triplets

Project Euler Problem 242 Solution

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

Problem Summary For each pair $(n,k)$, let $f(n,k)$ be the number of $k$-element subsets of $\{1,2,\dots,n\}$ whose element sum is odd. An odd triplet is a triplet $(n,k,f(n,k))$ in which all three entries are odd. The quantity to evaluate is $$A(N)=\#\{(n,k):1\le k\le n\le N,\ n,\ k,\ f(n,k)\text{ are all odd}\},$$ and the implementations compute $A(10^{12})$. The search space is far too large for direct enumeration, so the key is to understand only the parity of $f(n,k)$, not its exact size. Mathematical Approach The derivation starts from a straightforward combinatorial count, turns that count into a parity statement over modulo 2 arithmetic, and then collapses the whole problem to a short prefix sum involving binary popcounts. Separating odd and even elements Let $$o=\left\lceil\frac n2\right\rceil,\qquad e=\left\lfloor\frac n2\right\rfloor.$$ Any $k$-subset of $\{1,\dots,n\}$ has odd total exactly when it contains an odd number of odd elements. Therefore $$f(n,k)=\sum_{\substack{j=0\\ j\text{ odd}}}^{k}\binom{o}{j}\binom{e}{k-j}.$$ Because an odd triplet must have odd first and second coordinates, we only need $n=2m+1$ and $k=2r+1$....

Detailed mathematical approach

Problem Summary

For positive integers $n$ and $k$, $f(n,k)$ is the number of $k$-element subsets of $\{1,2,\dots,n\}$ whose elements have an odd sum. For example, $f(5,3)=4$, because the $3$-element subsets of $\{1,2,3,4,5\}$ with an odd sum are $\{1,2,4\}$, $\{1,3,5\}$, $\{2,3,4\}$ and $\{2,4,5\}$. When $n$, $k$ and $f(n,k)$ are all odd, the three numbers form an odd triplet $[n,k,f(n,k)]$. The statement says that there are exactly five odd triplets with $n\le10$, namely $[1,1,1]$, $[5,1,3]$, $[5,5,1]$, $[9,1,5]$ and $[9,9,1]$, and asks how many odd triplets there are with $n\le10^{12}$. ^[1] A triplet is determined by $n$ and $k$, and $f(n,k)=0$ for $k\gt n$. So we must count the pairs $(n,k)$ of odd numbers with $k\le n\le N$ for which $f(n,k)$ is odd; we call this number $A(N)$, so that $A(10)=5$, and we want $A(10^{12})$.

The whole solution in one sentence: swapping an element of a subset for the number two above or below it changes neither the size of the subset nor the parity of its sum, and pairing up subsets in this way shows that, for odd $n$ and $k$, $f(n,k)$ is odd exactly when $n=4t+1$, $k=4s+1$ and the binomial coefficient $\binom{t}{s}$ is odd, so the odd triplets with $n\le N$ correspond one to one to the odd entries in rows $0$ to $\lfloor(N-1)/4\rfloor$ of Pascal's triangle, and a short formula with powers of $3$ counts these in one pass over the binary digits of that last row number.

Mathematical Approach

The numbers $f(n,k)$ are huge, but only their parity matters. We look at small cases, find the parity with a pairing argument, and then count the odd triplets digit by digit in binary.

1. Small cases

Listing all subsets gives, for the odd $n\le13$, the values $f(n,1),f(n,3),\dots,f(n,n)$:

$n=1$: $1$;
$n=3$: $2,0$;
$n=5$: $3,4,1$;
$n=7$: $4,16,12,0$;
$n=9$: $5,40,66,16,1$;
$n=11$: $6,80,236,160,30,0$;
$n=13$: $7,140,651,848,365,36,1$.

Two patterns appear. For $n=3,7,11$ every value is even. For $n=1,5,9,13$ odd values occur, but only at $k=1,5,9,13$, the numbers of the form $4s+1$, and not at all of them: $n=9$ has odd values at $k=1$ and $k=9$ but not at $k=5$, while $n=13$ has them at all four places. The five odd values for $n\le9$ are the five odd triplets of the statement. The next sections explain both patterns.

2. Counting by the odd elements

The binomial coefficient $\binom ab$ is the number of ways to choose $b$ of $a$ objects, and the numbers $\binom a0,\binom a1,\dots,\binom aa$ form row $a$ of Pascal's triangle, whose top row is row $0$. ^[2] A sum is odd exactly when it has an odd number of odd terms, because even terms do not change the parity. The set $\{1,\dots,n\}$ contains $o=\lceil n/2\rceil$ odd and $e=\lfloor n/2\rfloor$ even numbers, and choosing $2i+1$ odd and $k-2i-1$ even elements gives

$$f(n,k)=\sum_{i\ge0}\binom{o}{2i+1}\binom{e}{k-2i-1},$$

with $\binom ab=0$ when $b\lt0$ or $b\gt a$. For $n=5$ we have $o=3$ and $e=2$, and

$$f(5,3)=\binom31\binom22+\binom33\binom20=3+1=4.$$

The sum is exact, but for large $n$ its terms are enormous and it hides the parity; the C++ program uses it only in its checks.

3. Swapping partners

Fix an odd $n$ and pair every number $a\le n-2$ that leaves the remainder $1$ or $2$ on division by $4$ with $a+2$: the pairs are $\{1,3\}$, $\{2,4\}$, $\{5,7\}$, $\{6,8\}$ and so on. The two numbers of a pair differ by $2$, so they have the same parity. Exactly one number is left without a partner: $n$ itself when $n=4t+1$, and $n-1$ when $n=4t+3$.

Now let $B$ be a $k$-subset with an odd sum. If $B$ contains exactly one number of some pair, let $P$ be the first such pair, ordered by their smaller numbers, and let $\varphi(B)$ be $B$ with that number replaced by its partner; otherwise let $\varphi(B)=B$. The swap keeps the size and changes the sum by $\pm2$, so $\varphi(B)$ is again a $k$-subset with an odd sum. It changes nothing outside $P$, and $\varphi(B)$ still contains exactly one number of $P$, so $P$ is again the first such pair and a second swap undoes the first: $\varphi(\varphi(B))=B$. A map that undoes itself in this way is an involution. The subsets that $\varphi$ moves fall into disjoint couples $\{B,\varphi(B)\}$, so they are even in number: the number of elements of a finite set and the number of fixed points of an involution on it have the same parity. ^[3]

Hence $f(n,k)$ has the same parity as the number of fixed subsets, the $k$-subsets with odd sum that contain both numbers or neither number of every pair. For $n=5$ and $k=3$ the pairs are $\{1,3\}$ and $\{2,4\}$, and $5$ has no partner. The subsets $\{1,2,4\}$ and $\{2,3,4\}$ form a couple, swapped in the pair $\{1,3\}$, while $\{1,3,5\}$ and $\{2,4,5\}$ are fixed; both $f(5,3)=4$ and the number $2$ of fixed subsets are even.

4. Only $n=4t+1$ can work

A whole pair $\{a,a+2\}$ adds two elements and the even amount $2a+2$ to the sum. A fixed subset consists of whole pairs, possibly together with the number without a partner, so its sum is odd exactly when it contains that lone number and the lone number is odd.

If $n=4t+3$, the lone number $4t+2$ is even, no fixed subset has an odd sum, and $f(4t+3,k)$ is even for every $k$. This explains the rows $n=3,7,11$.

If $n=4t+1$, there are $2t$ pairs and the lone number $4t+1$ is odd. A fixed subset with odd sum consists of $4t+1$ and some $r$ of the $2t$ pairs; it has $2r+1$ elements, and there are $\binom{2t}{r}$ ways to choose the pairs. So $f(4t+1,k)$ is even for even $k$, and

$$f(4t+1,\,2r+1)\equiv\binom{2t}{r}\pmod 2.$$

For $n=13$, that is $t=3$, the right-hand side runs through row $6$ of Pascal's triangle, $1,6,15,20,15,6,1$, with odd entries at $r=0,2,4,6$, which are the places $k=1,5,9,13$ found in Section 1. For example, the fixed $5$-subsets with odd sum consist of $13$ and $2$ of the $6$ pairs; there are $15$ of them, and $f(13,5)=651$ is odd, as predicted.

5. Odd binomial coefficients

The same trick decides when a binomial coefficient $\binom Mr$ is odd. Pair $1$ with $2$, $3$ with $4$, and so on, so that $M$ stays alone when $M$ is odd, and swap inside the first pair that an $r$-subset of $\{1,\dots,M\}$ meets in exactly one number. This is again an involution, and its fixed points are the unions of whole pairs, possibly with the lone number. For even $r=2s$ they are the $\binom{\lfloor M/2\rfloor}{s}$ unions of $s$ pairs. For odd $r=2s+1$ they must contain the lone number, so there are $\binom{\lfloor M/2\rfloor}{s}$ of them when $M$ is odd and none when $M$ is even. Therefore

$$\binom{M}{r}\equiv\binom{\lfloor M/2\rfloor}{\lfloor r/2\rfloor}\pmod 2,$$

except that $\binom Mr$ is even whenever $r$ is odd and $M$ is even. Halving with rounding down removes the last binary digit, and the exception says that the last digit of $r$ must not be larger than that of $M$. Repeating this until $M=0$, where $\binom0r$ is odd only for $r=0$, gives Lucas's theorem for the prime $2$: $\binom Mr$ is odd exactly when $M$ has a binary digit $1$ wherever $r$ has one. ^[4] We then call $r$ a binary submask of $M$. For example $6=110_2$, and its submasks $0$, $2=10_2$, $4=100_2$ and $6$ are exactly the places of the odd entries of row $6$. Each digit $1$ of $M$ may be kept or dropped in a submask, so row $M$ contains $2^{w(M)}$ odd entries, where $w(M)$ is the number of ones in the binary representation of $M$, also called its binary weight or popcount. ^[5] This count was already known to J. W. L. Glaisher in 1899. ^[6]

6. Which triplets are odd

Apply this to Section 4. The number $2t$ ends with the binary digit $0$, so $\binom{2t}{r}$ is even for odd $r$, and for $r=2s$ the rule of Section 5 gives $\binom{2t}{2s}\equiv\binom ts\pmod 2$. Since $k=2r+1=4s+1$, Sections 3 to 5 prove the following.

Claim. For odd $n$ and odd $k$, $f(n,k)$ is odd exactly when $n=4t+1$ and $k=4s+1$, where $0\le s\le t$ and $s$ is a binary submask of $t$, that is, $\binom ts$ is odd.

For $n\le10$ we have $t\le2$. Here $t=0$ allows $s=0$, $t=1$ allows $s=0,1$, and $t=2=10_2$ allows $s=0$ and $s=2$ but not $s=1$. This gives the pairs $(n,k)=(1,1)$, $(5,1)$, $(5,5)$, $(9,1)$ and $(9,9)$ of the statement, and explains why $f(9,5)=66$ is even. For $t=3=11_2$ every $s\le3$ is a submask, which is the row $n=13$ of Section 1.

7. An exact formula as a check

The values of Section 1 can also be checked without listing subsets. Multiply out the product of the factors $1+x$ for the even numbers and $1-x$ for the odd numbers up to $n$. As in the binomial theorem, ^[2] each subset contributes $x$ to the power of its size, with the sign $+$ for an even sum and $-$ for an odd one, because it takes one factor $-1$ from each odd element. So the coefficient of $x^k$ is the number of $k$-subsets with even sum minus $f(n,k)$, and these two numbers add up to $\binom nk$. For $n=2m+1$ the product is $(1-x)^{m+1}(1+x)^m$${}=(1-x)(1-x^2)^m$, whose coefficient of $x^{2r+1}$ is $-(-1)^r\binom mr$. Hence

$$f(2m+1,\,2r+1)=\frac12\left(\binom{2m+1}{2r+1}+(-1)^r\binom{m}{r}\right),$$

for example $f(13,5)=\frac12(1287+15)=651$. To read off parities from this formula one would need both binomial coefficients modulo $4$, which the pairing avoids.

8. Odd triplets are odd entries of Pascal's triangle

By the claim, $[4t+1,4s+1,f(4t+1,4s+1)]$ is an odd triplet exactly when $\binom ts$ is odd, and $4t+1\le N$ means $t\le T$ with

$$T=\left\lfloor\frac{N-1}{4}\right\rfloor.$$

So the odd triplets with $n\le N$ correspond one to one to the odd entries in rows $0$ to $T$ of Pascal's triangle. For $N=10$ we get $T=2$, and the rows $1$; $1,1$; $1,2,1$ contain five odd entries, one for each odd triplet of the statement. Counting the odd entries row by row with Section 5 gives

$$A(N)=S(T),\qquad S(T)=\sum_{t=0}^{T}2^{w(t)},$$

for instance $A(10)=2^0+2^1+2^1=5$. The values $S(0),S(1),S(2),\dots$ are $1,3,5,9,11,15,19,27,\dots$; they are the numbers of odd entries in the first rows of Pascal's triangle, listed in the OEIS as A006046, with $S(T)$ at index $T+1$. ^[7] Colouring the odd entries black draws an approximation of the Sierpiński triangle, ^[8] whose black cells we are counting. For $N=10^{12}$ the sum still has $T+1=250\,000\,000\,000$ terms, so we add them in blocks.

9. Complete blocks give powers of 3

The $2^b$ numbers $0\le t\lt2^b$ are the strings of $b$ binary digits, and $2^{w(t)}$ is the product of a factor $1$ for every digit $0$ and a factor $2$ for every digit $1$. Multiplying out $(1+2)^b$, one factor for each digit, produces each of these products exactly once, so

$$S(2^b-1)=\sum_{t=0}^{2^b-1}2^{w(t)}=(1+2)^b=3^b.$$

For $b=2$ this is $1+2+2+4=9$. Geometrically, by Section 5 the rows $2^b$ to $2^{b+1}-1$ hold two copies of the rows $0$ to $2^b-1$ modulo $2$, at the left and right ends: the self-similarity of the Sierpiński triangle, a figure of dimension $\log_23\approx1.585$. ^[8] Accordingly $S(T)$ grows roughly like $T^{1.585}$. ^[6]

10. One pass over the binary digits

Let the binary ones of $T$ stand at the positions $b_1\gt b_2\gt\dots\gt b_w$, counted from $0$ at the right, so that $w=w(T)$. Every $t\lt T$ agrees with $T$ above the highest position where the two differ, and there $T$ has a $1$ and $t$ a $0$, so that position is one of the $b_i$. The numbers $t$ whose first difference lies at $b_i$ have the $i-1$ higher ones of $T$, a $0$ at position $b_i$ and any $b_i$ lower digits, so by Section 9 they contribute $2^{i-1}3^{b_i}$. The number $t=T$ contributes $2^w$. Therefore

$$S(T)=2^{w}+\sum_{i=1}^{w}2^{i-1}\,3^{b_i}.$$

Worked example. For $N=100$ we get $T=24=11000_2$, so $w=2$, $b_1=4$ and $b_2=3$:

$$A(100)=S(24)=3^4+2\cdot3^3+2^2=81+54+4=139.$$

The three terms count $t=0,\dots,15$, then $t=16,\dots,23$, and finally $t=24$, and a direct count of the odd values $f(n,k)$ for $n\le100$ also gives $139$. In the same way $T=249=11111001_2$ gives $A(1000)=5793$. The formula takes one step per binary digit of $T$.

11. The size of the numbers

For $N=10^{12}$ we have $T=249\,999\,999\,999$, a number with $38$ binary digits, $22$ of them ones. Since $S$ increases, $S(T)\lt S(2^{38}-1)=3^{38}$, and $3^{38}\approx1.35\cdot10^{18}$ is below $2^{63}\approx9.2\cdot10^{18}$, so the count fits into a signed 64-bit integer. The formula of Section 10 needs one step per digit, whereas adding the terms of Section 8 one by one would take $2.5\cdot10^{11}$ steps, and testing all pairs $(n,k)$ of odd numbers about $1.25\cdot10^{23}$.

How the Code Works

The C++ program ^[9] starts in main with the bound $N=10^{12}$ and its checks switched on. parse_arguments accepts, among other options, --n= followed by a decimal bound and --skip-checkpoints; an unknown argument, or a bound that does not fit into 64 bits, ends the program with exit code $1$. Then run_checkpoints makes four checks:

f_exact(5, 3) must be $4$; this function evaluates the sum of Section 2 with exact binomial coefficients from binom_exact.
count_odd_triplets_bruteforce(10) must be $5$; it applies f_is_odd_direct to all pairs of odd numbers $k\le n\le10$.
For all $125\,751$ pairs of odd numbers $k\le n\le1001$, f_is_odd_direct and f_is_odd_formula must agree. The first takes the parity of the sum of Section 2 term by term, and binom_is_odd(n, k) applies Lucas's theorem as the bit test (k & ~n) == 0. The second is Section 4: it answers no unless $n$ and $k$ are odd, $k\le n$ and $m=(n-1)/2$ is even, so that $n=4t+1$ and $m=2t$, and then it returns binom_is_odd(m, (k-1)/2), the parity of $\binom{2t}{r}$. Both rely on Lucas's theorem, so this check tests Sections 3 and 4.
For every $x\le200\,000$, weighted_popcount_prefix_sum(x) must equal a running sum of $2^{w(x)}$, formed with the builtin __builtin_popcountll. ^[10]

A failed check is reported on the error stream and ends the program with exit code $1$; otherwise a confirmation line is printed. solve then returns $0$ for $N=0$, and otherwise computes $\lfloor(N-1)/2\rfloor$, the largest $m$ with $2m+1\le N$, halves it to $T=\lfloor(N-1)/4\rfloor$, because only even $m$ contribute, and returns weighted_popcount_prefix_sum(T). That function is Section 10 as a loop: it visits bit $=63,62,\dots,0$, and at every digit $1$ of its argument it adds 1 << ones_so_far times pow3[bit], the term $2^{i-1}3^{b_i}$, and then increases ones_so_far; after the loop it adds $2^w$. powers_of_three builds the table $3^0,\dots,3^{64}$ once. The powers, the terms and the sum are kept in u128, an alias of GCC's unsigned 128-bit type __uint128_t, ^[10] while the bound and the arguments of the binomial coefficients are 64-bit u64 values. Since $3^{64}\lt2^{128}$, the table and the prefix sum for every 64-bit argument fit, and to_string_u128 writes the result in decimal.

The Python program does the same in a function solve with a nested weighted_popcount_prefix_sum, the bound fixed at $10^{12}$ and the same list of $65$ powers of $3$; Python integers have unlimited precision. ^[11] The Java program has the same structure in weightedPopcountPrefixSum and solve, with the powers in a static long array pow3. From $3^{40}$ on these entries exceed $2^{63}-1$ and wrap around, since Java's integer operators do not signal overflow; ^[11] this is harmless here because $T\lt2^{38}$, so the loop reads only $3^0,\dots,3^{37}$, and $S(T)\lt3^{38}$ fits into a long. Neither the Python nor the Java program runs the checks of the C++ version.

Complexity and Verification

Counting each arithmetic operation as one step, the method of Section 10 needs one step per binary digit of $T$ and a table of as many powers of $3$, that is, $O(\log N)$ time and memory. The published routines fix the number of positions at $64$: they always make $64$ passes over a table of $65$ powers, a constant amount of work for every 64-bit bound. The checks of the C++ program cost more: the parity comparison makes about $1.6\cdot10^7$ passes of the loop in f_is_odd_direct, and the prefix check about $1.3\cdot10^7$ loop passes. In tests on a desktop computer each of the three programs finished in well under a second, the C++ program including its checks.

Beyond these built-in checks, the following was verified for this article. Listing all subsets for every odd $n\le19$ reproduces Section 1 and agrees with Sections 2 and 7 for every odd $k$. A count that adds the numbers $1,2,\dots,n$ one at a time, keeping for every size the numbers of subsets with even and with odd sum, agrees with Section 7 for every odd $n\le299$. Done modulo $2$, this count uses neither the pairing nor Lucas's theorem; it confirms the claim of Section 6 for every $n\le10\,000$ and gives $A(N)=S(\lfloor(N-1)/4\rfloor)$ for every $N\le10\,000$, for instance $A(10\,000)=204\,993$. Three evaluations of $S(T)$ agree for every $T\lt5000$, for $2000$ random $T\lt2^{62}$ and at $T=249\,999\,999\,999$: the formula of Section 10, the recursion $S(2^b+x)=3^b+2S(x)$ for $0\le x\lt2^b$, since $2^b+y$ has one binary one more than $y\lt2^b$, and a count of the $t\le T$ by their number of ones; the first two also match a direct summation for every $T\lt2^{20}$. The three programs print the same number, which agrees with these evaluations, and the C++ program with --n= reproduces $A(N)$ for $N=13$, $100$, $1000$ and $10\,000$. None of these checks is part of the published solutions.

Footnotes and References

The references below supply the background facts used above. The pairing argument for the parity of $f(n,k)$, the description of the odd triplets, the exact formula of Section 7 and the binary formula for $S(T)$ are derived explicitly in this article.

Project Euler 242 — Odd Triplets. The official statement defines f(n, k) as the number of k-element subsets of {1, 2, …, n} with an odd sum of elements, gives f(5, 3) = 4, calls [n, k, f(n, k)] an odd-triplet when all three values are odd, lists the five odd-triplets with n ≤ 10 and asks for the number of odd-triplets with n ≤ 10¹².
Wikipedia — Binomial theorem. C(n, k) counts the ways to choose k elements from an n-element set and is the k-th entry of row n of Pascal's triangle, counted from row 0; the expansion of (x + y)ⁿ has one term for each choice of x or y from each factor.
Wikipedia — Involution (mathematics). An involution is a function that is its own inverse; the number of fixed points of an involution on a finite set has the same parity as the number of elements of the set.
Wikipedia — Lucas's theorem. For a prime p, C(m, n) is congruent modulo p to the product of the binomial coefficients of the base-p digits; for p = 2, C(m, n) is odd exactly when the positions of the ones in the binary expansion of n are a subset of those in the expansion of m. The theorem appeared in 1878 in papers by Édouard Lucas.
Wikipedia — Hamming weight. For a string of bits, the Hamming weight is the number of ones, also called the population count or popcount.
Wikipedia — Gould's sequence. The sequence counts the odd numbers in row n of Pascal's triangle, 2 to the power of the number of ones in the binary representation of n, a fact already known to J. W. L. Glaisher in 1899; its partial sums grow roughly like n^1.585.
OEIS A006046 — Total number of odd entries in first n rows of Pascal's triangle. The entry gives a(n) as the sum of 2^wt(i) over 0 ≤ i ≤ n − 1, with wt(i) the number of ones in the binary expansion of i, and a(2ⁿ) = 3ⁿ; in the notation of this article, S(T) = a(T + 1).
Wikipedia — Sierpiński triangle. Pascal's triangle with 2ⁿ rows, with odd numbers coloured black and even numbers white, approximates the Sierpiński triangle, which consists of three half-size copies of itself and has Hausdorff dimension log 3 / log 2 ≈ 1.585.
C++ — Euler242.cpp. The linked immutable revision, with f_is_odd_direct, f_is_odd_formula, weighted_popcount_prefix_sum and run_checkpoints, is the implementation record for this article.
GCC manual — 128-bit Integers describes __int128 and unsigned __int128, and GCC manual — Bit Operation Builtins describes __builtin_popcountll, which returns the number of 1-bits of an unsigned long long.
Java Language Specification, §4.2.2 — Integer Operations states that the integer operators do not indicate overflow or underflow in any way; §4.2.1 gives the range of long, −2⁶³ to 2⁶³ − 1. Python — numeric types states that integers have unlimited precision.

Problem 242 source code

C++

#include <algorithm>
#include <atomic>
#include <cstdint>
#include <iostream>
#include <limits>
#include <string>
#include <thread>
#include <vector>

namespace {

using u64 = std::uint64_t;
using u128 = __uint128_t;

constexpr u64 kDefaultLimit = 1'000'000'000'000ULL;

struct Options {
    u64 limit = kDefaultLimit;
    bool run_checkpoints = true;
    bool allow_multithreading = true;
    unsigned requested_threads = 0U;
};

std::string to_string_u128(u128 value) {
    if (value == 0) {
        return "0";
    }

    std::string result;
    while (value > 0) {
        const int digit = static_cast<int>(value % 10);
        result.push_back(static_cast<char>('0' + digit));
        value /= 10;
    }

    std::reverse(result.begin(), result.end());
    return result;
}

bool parse_u64_after_prefix(const std::string& arg, const char* prefix, u64& value) {
    const std::string p(prefix);
    if (arg.rfind(p, 0) != 0U) {
        return false;
    }

    const std::string tail = arg.substr(p.size());
    if (tail.empty()) {
        return false;
    }

    u64 parsed = 0ULL;
    for (const char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        const u64 digit = static_cast<u64>(c - '0');
        if (parsed > (std::numeric_limits<u64>::max() - digit) / 10ULL) {
            return false;
        }
        parsed = parsed * 10ULL + digit;
    }

    value = parsed;
    return true;
}

bool parse_unsigned_after_prefix(const std::string& arg,
                                 const char* prefix,
                                 unsigned& value) {
    u64 parsed = 0ULL;
    if (!parse_u64_after_prefix(arg, prefix, parsed)) {
        return false;
    }
    if (parsed > static_cast<u64>(std::numeric_limits<unsigned>::max())) {
        return false;
    }
    value = static_cast<unsigned>(parsed);
    return true;
}

bool parse_arguments(const 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 (arg == "--single-thread") {
            options.allow_multithreading = false;
            continue;
        }

        u64 parsed_u64 = 0ULL;
        if (parse_u64_after_prefix(arg, "--n=", parsed_u64)) {
            options.limit = parsed_u64;
            continue;
        }

        unsigned parsed_unsigned = 0U;
        if (parse_unsigned_after_prefix(arg, "--threads=", parsed_unsigned)) {
            options.requested_threads = parsed_unsigned;
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return true;
}

unsigned choose_thread_count(const bool allow_multithreading,
                             const unsigned requested_threads,
                             const std::size_t workload) {
    if (!allow_multithreading || workload < 8ULL) {
        return 1U;
    }

    unsigned threads = requested_threads;
    if (threads == 0U) {
        threads = std::thread::hardware_concurrency();
        if (threads == 0U) {
            threads = 1U;
        }
    }

    return std::max(1U, std::min<unsigned>(threads, static_cast<unsigned>(workload)));
}

bool binom_is_odd(const u64 n, const u64 k) {
    return k <= n && ((k & ~n) == 0ULL);
}

u128 binom_exact(const u64 n, u64 k) {
    if (k > n) {
        return 0;
    }
    if (k > n - k) {
        k = n - k;
    }

    u128 value = 1;
    for (u64 i = 1; i <= k; ++i) {
        value = (value * static_cast<u128>(n - k + i)) / static_cast<u128>(i);
    }
    return value;
}

u128 f_exact(const u64 n, const u64 k) {
    const u64 odd_count = (n + 1ULL) / 2ULL;
    const u64 even_count = n / 2ULL;

    u128 total = 0;
    for (u64 odd_taken = 1ULL; odd_taken <= k && odd_taken <= odd_count; odd_taken += 2ULL) {
        const u64 even_taken = k - odd_taken;
        if (even_taken > even_count) {
            continue;
        }
        total += binom_exact(odd_count, odd_taken) * binom_exact(even_count, even_taken);
    }
    return total;
}

bool f_is_odd_direct(const u64 n, const u64 k) {
    if (k > n) {
        return false;
    }

    const u64 odd_count = (n + 1ULL) / 2ULL;
    const u64 even_count = n / 2ULL;

    bool parity = false;
    for (u64 odd_taken = 1ULL; odd_taken <= k && odd_taken <= odd_count; odd_taken += 2ULL) {
        const u64 even_taken = k - odd_taken;
        if (even_taken > even_count) {
            continue;
        }

        if (binom_is_odd(odd_count, odd_taken) && binom_is_odd(even_count, even_taken)) {
            parity = !parity;
        }
    }
    return parity;
}

bool f_is_odd_formula(const u64 n, const u64 k) {
    if ((n & 1ULL) == 0ULL || (k & 1ULL) == 0ULL || k > n) {
        return false;
    }

    const u64 m = (n - 1ULL) / 2ULL;
    if ((m & 1ULL) != 0ULL) {
        return false;
    }

    const u64 r = (k - 1ULL) / 2ULL;
    return binom_is_odd(m, r);
}

u64 count_odd_triplets_bruteforce(const u64 limit) {
    u64 total = 0;
    for (u64 n = 1ULL; n <= limit; n += 2ULL) {
        for (u64 k = 1ULL; k <= n; k += 2ULL) {
            if (f_is_odd_direct(n, k)) {
                ++total;
            }
        }
    }
    return total;
}

const std::vector<u128>& powers_of_three() {
    static const std::vector<u128> table = [] {
        std::vector<u128> values(65, 0);
        values[0] = 1;
        for (std::size_t i = 1; i < values.size(); ++i) {
            values[i] = values[i - 1] * static_cast<u128>(3);
        }
        return values;
    }();
    return table;
}

u128 weighted_popcount_prefix_sum(const u64 n) {
    const auto& pow3 = powers_of_three();

    u128 result = 0;
    unsigned ones_so_far = 0U;

    for (int bit = 63; bit >= 0; --bit) {
        if (((n >> bit) & 1ULL) == 0ULL) {
            continue;
        }

        result += (static_cast<u128>(1) << ones_so_far) * pow3[static_cast<std::size_t>(bit)];
        ++ones_so_far;
    }

    result += (static_cast<u128>(1) << ones_so_far);
    return result;
}

u128 solve(const u64 limit) {
    if (limit == 0ULL) {
        return 0;
    }

    // n = 2m+1 and only even m contribute, so m = 2t.
    const u64 m_max = (limit - 1ULL) / 2ULL;
    const u64 t_max = m_max / 2ULL;
    return weighted_popcount_prefix_sum(t_max);
}

bool run_checkpoints(const Options& options) {
    bool ok = true;

    if (f_exact(5, 3) != static_cast<u128>(4)) {
        std::cerr << "Checkpoint failed: f(5,3) should be 4.\n";
        ok = false;
    }

    const u64 sample_count = count_odd_triplets_bruteforce(10ULL);
    if (sample_count != 5ULL) {
        std::cerr << "Checkpoint failed: odd-triplets up to n=10 should be 5.\n";
        ok = false;
    }

    const u64 parity_check_max_n = 1001ULL;
    const std::size_t workload = static_cast<std::size_t>((parity_check_max_n + 1ULL) / 2ULL);
    const unsigned thread_count =
        choose_thread_count(options.allow_multithreading, options.requested_threads, workload);

    std::atomic<bool> parity_ok(true);
    std::atomic<u64> next_n(1ULL);

    auto worker = [&]() {
        while (parity_ok.load(std::memory_order_relaxed)) {
            const u64 n = next_n.fetch_add(2ULL, std::memory_order_relaxed);
            if (n > parity_check_max_n) {
                break;
            }

            for (u64 k = 1ULL; k <= n; k += 2ULL) {
                if (f_is_odd_direct(n, k) != f_is_odd_formula(n, k)) {
                    parity_ok.store(false, std::memory_order_relaxed);
                    return;
                }
            }
        }
    };

    std::vector<std::thread> pool;
    pool.reserve(thread_count);
    for (unsigned i = 0U; i < thread_count; ++i) {
        pool.emplace_back(worker);
    }
    for (auto& th : pool) {
        th.join();
    }

    if (!parity_ok.load()) {
        std::cerr << "Checkpoint failed: parity identity mismatch.\n";
        ok = false;
    }

    u128 running = 0;
    constexpr u64 kPrefixCheckMax = 200000ULL;
    for (u64 x = 0ULL; x <= kPrefixCheckMax; ++x) {
        running += (static_cast<u128>(1) << __builtin_popcountll(x));
        if (weighted_popcount_prefix_sum(x) != running) {
            std::cerr << "Checkpoint failed: weighted prefix mismatch at x=" << x << ".\n";
            ok = false;
            break;
        }
    }

    if (ok) {
        std::cout << "Checkpoints passed (threads=" << thread_count << ").\n";
    }

    return ok;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }

    if (options.run_checkpoints && !run_checkpoints(options)) {
        return 1;
    }

    const u128 answer = solve(options.limit);
    std::cout << "Answer: " << to_string_u128(answer) << '\n';
    return 0;
}

Python

def solve():
    limit = 1000000000000
    
    # Precompute powers of 3
    pow3 = [1] * 65
    for i in range(1, 65):
        pow3[i] = pow3[i-1] * 3
        
    def weighted_popcount_prefix_sum(n):
        result = 0
        ones_so_far = 0
        
        for bit in range(63, -1, -1):
            if ((n >> bit) & 1) == 0:
                continue
                
            result += (1 << ones_so_far) * pow3[bit]
            ones_so_far += 1
            
        result += (1 << ones_so_far)
        return result
        
    m_max = (limit - 1) // 2
    t_max = m_max // 2
    
    ans = weighted_popcount_prefix_sum(t_max)
    return str(ans)

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

Java

public class Euler242 {
    static long[] pow3 = new long[65];
    static {
        pow3[0] = 1;
        for (int i = 1; i < 65; i++) {
            pow3[i] = pow3[i - 1] * 3;
        }
    }

    static long weightedPopcountPrefixSum(long n) {
        long result = 0;
        int onesSoFar = 0;

        for (int bit = 63; bit >= 0; --bit) {
            if (((n >> bit) & 1) == 0) {
                continue;
            }

            result += (1L << onesSoFar) * pow3[bit];
            onesSoFar++;
        }

        result += (1L << onesSoFar);
        return result;
    }

    public static String solve() {
        long limit = 1_000_000_000_000L;
        long mMax = (limit - 1) / 2;
        long tMax = mMax / 2;

        long ans = weightedPopcountPrefixSum(tMax);
        return String.valueOf(ans);
    }

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