Detailed mathematical approach

Problem Summary

For each \(n\), the bottles form a triangular stack with

$T_n=\frac{n(n+1)}2$

positions. A bottle can only be chosen when no bottle above it is still present. If an exposed bottle is chosen, its contribution is the number of still-active downward paths that start at that bottle. Let \(f_n\) be the total weighted count over all legal fall histories of the \(n\)-row triangle. The task is to compute

$\sum_{n=1}^{10000} f_n \pmod{M},\qquad M=1{,}000{,}000{,}033.$

The exact state recursion is far too large for \(n=10000\), so the solution uses a closed product formula and keeps the brute-force recursion only as a small verification tool.

Mathematical Approach

The implementation rests on two viewpoints: an exact recurrence on active bottle sets, and a closed product formula that collapses the same weighted process into a one-pass modular computation.

Step 1: Model the stack as a triangular partial order

Label the bottles by rows \(1,2,\dots,n\), with row \(r\) containing \(r\) bottles. A bottle in row \(r\) depends on the two bottles immediately above it, so the legal states form a directed acyclic graph. For any active set \(S\), let \(\max(S)\) be the exposed bottles, meaning the bottles in \(S\) that have no active parent.

Define \(F(S)\) to be the weighted number of legal ways to remove all bottles in \(S\). If \(u\in\max(S)\), let \(\pi_S(u)\) be the number of directed paths that start at \(u\) and stay entirely inside the active set \(S\). Then the exact recurrence is

$F(\varnothing)=1,\qquad F(S)=\sum_{u\in\max(S)} \pi_S(u)\,F(S\setminus\{u\}).$

For the full \(n\)-row triangle \(P_n\), the desired quantity is simply

$f_n=F(P_n).$

This recurrence is what the exact verifier evaluates for very small \(n\).

Step 2: Compute the local path weight of one exposed bottle

Suppose an exposed bottle sits at the top of a complete subtriangle of height \(h\). Every step downward has two geometric choices, left or right, as long as the next bottle exists. Therefore the total number of active downward paths starting from that bottle is

$1+2+2^2+\cdots+2^{h-1}=2^h-1.$

It is convenient to denote this path factor by

$W_h=2^h-1.$

The first values are \(W_1=1\), \(W_2=3\), \(W_3=7\), \(W_4=15\). These are exactly the numerators that appear in the fast formula.

Step 3: Count legal removal orders with staircase hook lengths

If we temporarily ignore the weights \(\pi_S(u)\) and only ask for legal removal orders, we are counting linear extensions of the triangular precedence poset. This is the staircase shape of size \(T_n\).

A bottle with \(h\) rows available beneath it has shifted hook length

$H_h=2h-1.$

There are \(n-h+1\) bottles of height \(h\), so the product of all hook lengths is

$\prod_{h=1}^{n} (2h-1)^{\,n-h+1}.$

Hence the unweighted number of legal orders is

$L_n=\frac{T_n!}{\prod_{h=1}^{n}(2h-1)^{\,n-h+1}}.$

The odd factors \(1,3,5,\dots,2n-1\) are the denominators seen in the final closed form.

Step 4: Combine the path weights with the hook factors

The weighted process replaces each height-\(h\) hook contribution by the ratio

$R_h=\frac{W_h}{H_h}=\frac{2^h-1}{2h-1}.$

Since height \(h\) occurs \(n-h+1\) times in the triangle, the total weighted count becomes

$f_n=T_n!\prod_{h=1}^{n}\left(\frac{2^h-1}{2h-1}\right)^{n-h+1}.$

This is the key formula used by the fast arithmetic loop. It matches the exact recursion on all small cases checked by the verifier.

Step 5: Rewrite the product into a streaming recurrence

Define the running ratio product

$Q_n=\prod_{h=1}^{n} R_h=\prod_{h=1}^{n}\frac{2^h-1}{2h-1}.$

Then

$\prod_{k=1}^{n} Q_k=\prod_{h=1}^{n} R_h^{\,n-h+1},$

so the closed form can be written as

$f_n=T_n!\prod_{k=1}^{n}Q_k.$

Because \(T_n=T_{n-1}+n\), we also get the incremental relation

$f_n=f_{n-1}\left(\prod_{t=T_{n-1}+1}^{T_n} t\right)Q_n.$

This is exactly why the implementation only needs running products rather than a large table of states.

Worked Example: \(n=3\)

For three rows we have

$T_3=\frac{3\cdot 4}{2}=6.$

The height multiplicities are:

$h=1\text{ appears }3\text{ times},\qquad h=2\text{ appears }2\text{ times},\qquad h=3\text{ appears }1\text{ time}.$

The corresponding ratios are

$R_1=\frac{2^1-1}{1}=1,\qquad R_2=\frac{2^2-1}{3}=1,\qquad R_3=\frac{2^3-1}{5}=\frac75.$

Therefore

$f_3=6!\cdot R_1^3 R_2^2 R_3=720\cdot \frac75=1008.$

The exact small-state recursion also produces \(1008\), so this example shows the agreement between the structural recurrence and the closed product formula.

How the Code Works

The C++, Python, and Java implementations iterate from \(n=1\) to \(10000\) and maintain only a few running quantities. First they update \(2^n \bmod M\), which yields the numerator \(2^n-1\). Then they divide by \(2n-1\) in modular arithmetic using a modular inverse, so the current ratio \(R_n\) is obtained without ever leaving the modulus.

Next the implementation updates two nested products: the prefix product \(Q_n\), and the product of all prefixes \(\prod_{k=1}^{n}Q_k\). In parallel it extends the factorial \(T_n!\) by multiplying the next \(n\) integers, because the triangular number grows from \(T_{n-1}\) to \(T_n\) by exactly \(n\) new positions. Multiplying the triangular factorial by the accumulated prefix product gives \(f_n\), and that value is added to the final sum modulo \(M\).

The C++ implementation also performs a separate exact verification for tiny \(n\). It represents active bottle sets by bitmasks, enumerates the exposed choices, computes the active path count for each choice, and memoizes the recurrence with arbitrary-precision integers. The first several values from that exact recursion are compared against the fast formula before the large \(n\) loop is trusted.

Complexity Analysis

The fast path runs in \(O(N\log M)\) time for \(N=10000\), because each step performs one modular inverse by binary exponentiation. The arithmetic state itself is constant-size, so the streaming formula needs only \(O(1)\) extra memory apart from any optional storage used for checking intermediate values.

The exact verifier is exponential in the number of bottles, which is why it is restricted to very small triangles. Its role is validation, not production computation.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=726
2. Hook-length formula: Wikipedia — Hook-length formula
3. Young tableau and staircase shapes: Wikipedia — Young tableau
4. Directed acyclic graph: Wikipedia — Directed acyclic graph
5. Modular multiplicative inverse: Wikipedia — Modular multiplicative inverse