Problem 909: L-expressions I
View on Project EulerProject Euler Problem 909 Solution
EulerSolve provides an optimized solution for Project Euler Problem 909, L-expressions I, with C++, Python, Java, and a step-by-step mathematical explanation.
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\)....
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
- Problem page: https://projecteuler.net/problem=909
- Function composition: Wikipedia - Function composition
- Polynomial: Wikipedia - Polynomial
- Pronic number: Wikipedia - Pronic number
- Arbitrary-precision arithmetic: Wikipedia - Arbitrary-precision arithmetic
- Modular arithmetic: Wikipedia - Modular arithmetic
Problem 909 source code
C++
#include <cassert>
#include <cstdint>
#include <iostream>
namespace {
using u64 = std::uint64_t;
using u128 = __uint128_t;
u128 T(const u128 n) {
return n * (n + 1);
}
u128 H(const u128 n) {
const u128 m = n * n * (n + 1);
return m * (m + 1);
}
u128 U(const u128 n) {
const u128 h = H(n);
return h * (h + 1);
}
u64 to_u64(const u128 x) {
return static_cast<u64>(x);
}
void validate() {
assert(to_u64(T(1)) == 2);
assert(to_u64(H(1)) == 6);
assert(to_u64(H(2)) == 156);
assert(to_u64(U(1)) == 42);
}
} // namespace
int main() {
validate();
constexpr u64 kMod = 1'000'000'000ULL;
const u128 n = U(1);
const u128 value = U(n);
const u64 answer = static_cast<u64>(value % kMod);
std::cout << answer << '\n';
return 0;
}
Python
def solve():
T = lambda n: n * (n + 1)
H = lambda n: T(n * n * (n + 1))
U = lambda n: T(H(n))
n = U(1)
value = U(n)
ans = value % 1000000000
return str(ans)
if __name__ == "__main__":
print(solve())
Java
import java.math.BigInteger;
public class Euler909 {
static BigInteger T(BigInteger n) {
return n.multiply(n.add(BigInteger.ONE));
}
static BigInteger H(BigInteger n) {
BigInteger m = n.multiply(n).multiply(n.add(BigInteger.ONE));
return m.multiply(m.add(BigInteger.ONE));
}
static BigInteger U(BigInteger n) {
BigInteger h = H(n);
return h.multiply(h.add(BigInteger.ONE));
}
public static String solve() {
BigInteger n = U(BigInteger.ONE);
BigInteger value = U(n);
long answer = value.remainder(BigInteger.valueOf(1000000000L)).longValue();
return Long.toString(answer);
}
public static void main(String[] args) {
System.out.println(solve());
}
}