Detailed mathematical approach

Problem Summary

Let

$T_n=\frac{n(n+1)}{2},\qquad D_n=d(T_n),$

where \(d(m)\) is the number of positive divisors of \(m\). For a given \(N\), we must count all triples of indices

$1\le i \lt j \lt k\le N$

such that

$D_i \gt D_j \gt D_k.$

In other words, after converting each triangular number \(T_n\) into its divisor count \(D_n\), the task is to count strictly decreasing subsequences of length three. The implementation targets \(N=60{,}000{,}000\) and returns the result modulo \(10^{18}\), so both the divisor-count computation and the triple counting must be highly optimized.

Mathematical Approach

Step 1: Compute \(d(T_n)\) from coprime factors

Consecutive integers are coprime:

$\gcd(n,n+1)=1.$

Also, exactly one of \(n\) and \(n+1\) is even. Therefore we can remove the factor \(2\) before applying the divisor function:

$T_n=\begin{cases} \frac{n}{2}(n+1), & n \text{ even},\\[2mm] n\frac{n+1}{2}, & n \text{ odd}. \end{cases}$

In both cases the two factors are coprime, so the divisor function is multiplicative:

$d(ab)=d(a)d(b)\qquad \text{when } \gcd(a,b)=1.$

Hence

$D_n=d(T_n)=\begin{cases} d\!\left(\frac{n}{2}\right)d(n+1), & n \text{ even},\\[2mm] d(n)d\!\left(\frac{n+1}{2}\right), & n \text{ odd}. \end{cases}$

This identity is the core simplification used by every implementation. For example, \(T_7=28=4\cdot 7\), so

$D_7=d(4)d(7)=3\cdot 2=6,$

which matches the explicit checkpoint in the C++ solver.

Step 2: Build all divisor counts with a linear sieve

Because the formula above only needs \(d(x)\) for integers up to \(N+1\), the program first precomputes the divisor-count table once. The arrays in build_tau store:

\(lp[i]\): the smallest prime dividing \(i\),

\(cnt[i]\): the exponent of \(lp[i]\) inside \(i\),

\(d(i)\): the divisor count itself.

If

$i=m p^e,\qquad p\nmid m,$

then

$d(i)=d(m)(e+1).$

When the sieve extends \(i\) to \(x=i p\), there are two cases:

$d(x)=\begin{cases} d(i)\cdot 2, & p\ne lp[i],\\[2mm] d(i)\cdot \dfrac{e+2}{e+1}, & p=lp[i]. \end{cases}$

The second formula is exactly what the source code writes as

$d(x)=\frac{d(i)}{cnt[i]+1}\,(cnt[x]+1).$

This produces all values up to \(N+1\) in linear total work, after which each \(D_n\) can be evaluated in constant time from the parity split above.

Step 3: Recast the problem as decreasing subsequences

Now consider the sequence

$D_1,D_2,\dots,D_N.$

We want the number of triples \(i \lt j \lt k\) with strict decrease. This is a dynamic-programming problem over values rather than over explicit triples.

For each processed position, maintain:

\(C(r)\): how many earlier indices have divisor-count rank \(r\),

\(P(r)\): how many decreasing pairs \((i,j)\) seen so far end with rank \(r\).

The code does not need coordinate compression. It first scans all \(D_n\) to find

$M=\max_{1\le n\le N} D_n,$

then uses the direct 1-based rank

$r=D_n+1.$

That is why the Fenwick trees are sized as max_d + 2 in both C++ and Java.

Step 4: Fenwick-tree recurrence

Suppose the current position is \(k\) and its rank is \(r\). Every earlier value larger than \(D_k\) creates a new decreasing pair ending at \(k\), so

$\text{greater\_left}(k)=\sum_{t=r+1}^{M+1} C(t).$

Similarly, every earlier decreasing pair whose second value is still larger than \(D_k\) can be extended to a triple ending at \(k\), so

$\text{triples\_ending\_here}(k)=\sum_{t=r+1}^{M+1} P(t).$

After computing those two quantities, the update rules are

$P(r)\leftarrow P(r)+\text{greater\_left}(k),$

$C(r)\leftarrow C(r)+1.$

A Fenwick tree gives each suffix sum and each point update in \(O(\log M)\). Two such trees are enough: one for single elements and one for decreasing pairs.

Worked Example: \(N=20\)

The first twenty values are

$\left(D_1,\dots,D_{20}\right)=\left(1,2,4,4,4,4,6,9,6,4,8,8,4,8,16,8,6,6,8,16\right).$

Because the inequalities are strict, equal values never contribute. For instance, \((8,9,10)\) is valid because

$D_8=9,\qquad D_9=6,\qquad D_{10}=4,$

and \((15,16,17)\) is valid because

$16 \gt 8 \gt 6.$

The total number of valid triples up to \(20\) is

$14,$

which is exactly the checkpoint count_triples_mod(20) == 14 in the C++ source.

How the Code Works

The C++ implementation is the reference solver. It builds tau up to kTargetN + 1, verifies the checkpoints d_triangle(7)=6, Tr(20)=14, Tr(100)=5772, and Tr(1000)=11174776, then performs two passes over \(1,\dots,N\): the first finds max_d, and the second performs the Fenwick-based dynamic programming.

The Java version mirrors the same mathematics, but stores every \(D_n\) in an array dtArr during the first pass so that the second pass does not recompute them. The Python file is intentionally thin: it compiles and runs the C++ solver, then parses the produced answer. So the mathematical logic is shared across all three languages, with C++ providing the canonical implementation details.

Complexity Analysis

Let \(N\) be the target limit and let \(M=\max_{1\le n\le N} D_n\). The divisor-count sieve runs in \(O(N)\) time and uses \(O(N)\) memory for the sieve arrays. The triple-counting phase performs two Fenwick queries and two Fenwick updates per index, so it costs \(O(N\log M)\) time and \(O(M)\) memory for the trees. Overall, the algorithm is dominated by

$O(N)+O(N\log M)=O(N\log M)$

time, with \(O(N)+O(M)\) memory. In practice \(M\) is far smaller than \(N\), which is why this approach is feasible for \(N=60{,}000{,}000\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=378
2. Triangular numbers: Wikipedia — Triangular number
3. Divisor function: Wikipedia — Divisor function
4. Fenwick tree: cp-algorithms — Fenwick Tree
5. Linear sieve: cp-algorithms — Linear Sieve