Detailed mathematical approach

Problem Summary

The implementations show that Problem 909 is not solved by generating L-expressions one by one. Instead, the entire counting question has already been compressed into a short chain of integer maps. If we introduce

$P(x)=x(x+1),\qquad A(n)=n^2(n+1),\qquad B(n)=P(A(n)),$

then the outer counting map is

$F(n)=P(B(n)),$

and the required value is simply

$F(F(1)) \bmod 10^9.$

So the real mathematical task is to understand this nested algebra, evaluate it exactly, and only then keep the last nine digits.

Mathematical Approach

The common pattern in the closed form is the same adjacent-product transform \(x \mapsto x(x+1)\), used twice on top of a cubic input. That turns the original counting problem into a fixed arithmetic evaluation.

The repeated adjacent-product map

Start from

$P(x)=x(x+1).$

This is the product of two consecutive integers, so for every integer \(x\) it is even. The next input is

$A(n)=n^2(n+1)=n^3+n^2,$

which feeds the same map once to form

$B(n)=P(A(n))=A(n)(A(n)+1).$

Applying the same construction one more time gives

$F(n)=P(B(n))=B(n)(B(n)+1).$

The whole problem is therefore a double self-application of the single outer map \(F\), starting from \(1\).

Collapsing the count into a closed form

Substituting the definitions removes any remaining combinatorial state:

$B(n)=n^2(n+1)\bigl(n^2(n+1)+1\bigr),$

$F(n)=n^2(n+1)\bigl(n^2(n+1)+1\bigr)\left(n^2(n+1)\bigl(n^2(n+1)+1\bigr)+1\right).$

Once this expression is known, there is nothing left to search or enumerate. The original counting problem has already been symbolically reduced to exact integer arithmetic.

The degree growth explains the scale of the numbers. The input \(A(n)\) has degree 3, the middle quantity \(B(n)\) has degree 6, and the outer quantity \(F(n)\) has degree 12. The values grow quickly, but the number of algebraic steps never grows.

Structural invariants

The formulas immediately imply several useful invariants. Both \(B(n)\) and \(F(n)\) are again of the form \(y(y+1)\), so they are always even nonnegative integers when \(n\ge 0\). The computation is exact from start to finish; there is no cancellation, approximation, or modular simplification inside the nested maps. Because the answer is just one exact integer reduced modulo \(10^9\), the modular reduction can be postponed safely until the very end.

Worked evaluation

The checkpoint values used by the implementations make the nesting transparent:

$P(1)=1\cdot 2=2,$

$A(1)=1^2(1+1)=2,$

$B(1)=P(2)=2\cdot 3=6,$

$A(2)=2^2(2+1)=12,\qquad B(2)=P(12)=12\cdot 13=156.$

From this,

$F(1)=P(B(1))=6\cdot 7=42.$

That value becomes the input for the second pass. Evaluating the same outer map at \(42\) gives

$A(42)=42^2\cdot 43=75852,$

$B(42)=75852\cdot 75853=5753601756,$

$F(42)=5753601756\cdot 5753601757=33103933172399885292.$

Therefore

$F(F(1)) \bmod 10^9 = F(42) \bmod 10^9 = 399885292.$

How the Code Works

Shared evaluation pipeline

The C++, Python, and Java implementations all follow the same sequence. They first verify a few small checkpoint identities from the closed form, including the values at \(1\) and \(2\). They then evaluate the outer map at \(1\) to obtain \(42\). Finally they evaluate the same outer map again at \(42\) and reduce the exact result modulo \(10^9\).

Because the mathematics is already closed-form, there is no expression generation, no search tree, no memoization, and no dynamic programming table. The implementation is simply a direct transcription of the nested formulas.

Exact integer arithmetic

The only real implementation concern is numeric range. The exact value

$33103933172399885292$

is larger than the maximum signed 64-bit integer, so ordinary signed 64-bit arithmetic is not enough. The C++ implementation uses unsigned 128-bit arithmetic, while the Python and Java implementations rely on arbitrary-precision integers. In every language the modulus is applied only after the exact product has been formed.

Complexity Analysis

At the algorithmic level, the computation performs a fixed number of additions and multiplications, so it runs in \(O(1)\) time and uses \(O(1)\) extra space. There is no dependence on a growing combinatorial state space because that work has already been collapsed into the formulas.

If one counts bit operations, the cost is still tiny: it is dominated by a constant number of multiplications on integers with \(\Theta(\log F(42))\) bits. In practice this is negligible compared with any method that would attempt to enumerate L-expressions directly.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=909
2. Function composition: Wikipedia - Function composition
3. Polynomial: Wikipedia - Polynomial
4. Pronic number: Wikipedia - Pronic number
5. Arbitrary-precision arithmetic: Wikipedia - Arbitrary-precision arithmetic
6. Modular arithmetic: Wikipedia - Modular arithmetic