Detailed mathematical approach

Problem Summary

The target quantity for Problem 739 is evaluated modulo \(M=10^9+7\) for \(n=10^8\). After simplifying the repeated-summation construction, the required value can be written as a single weighted sum of Lucas numbers:

$f(n)=\sum_{t=1}^{r} T_t\,L_{t+1}\pmod{M},\qquad r=n-1.$

The real difficulty is the size of \(r\). A direct quadratic summation is hopeless, and even an \(O(n)\) scan becomes too slow if it performs one modular exponentiation per term. The successful approach is to stream the coefficients backward, update Lucas values in lockstep, and batch the modular inverses.

Mathematical Approach

The solution combines Lucas-number identities, a ballot-number coefficient sequence, and blockwise modular inversion.

Step 1: Start from Lucas Numbers

The Lucas sequence satisfies \(L_0=2\), \(L_1=1\), and

$L_{k+1}=L_k+L_{k-1}.$

The implementations do not build this sequence from the beginning. Instead, they first obtain the Fibonacci pair \((F_k,F_{k+1})\) by fast doubling and then use

$L_k=F_{k-1}+F_{k+1}=2F_{k+1}-F_k.$

That gives the starting values \(L_r\) and \(L_{r+1}\) in \(O(\log n)\) time, which is small compared with the main scan.

Step 2: Identify the Weight Sequence

The required sum uses coefficients \(T_t\) generated backward from the endpoint:

$T_r=1,$

$T_{t-1}=T_t\cdot \frac{(t-1)(2r-t)}{t(r-t+1)}\qquad (2\le t\le r).$

This is not an arbitrary recurrence. It is exactly the ratio of ballot-number, or Catalan-triangle, coefficients. A closed form is

$T_t=\frac{t}{r}\binom{2r-t-1}{r-1}=\binom{2r-t-1}{r-1}-\binom{2r-t-1}{r}.$

So the repeated-summation problem collapses to a Lucas sum with very structured combinatorial weights.

Step 3: Turn the Sum into a Backward Stream

Because both the coefficients and the Lucas sequence admit backward updates, the whole computation can be done in one descending pass \(t=r,r-1,\dots,1\). Rearranging the Lucas recurrence gives

$L_{t-1}=L_{t+1}-L_t\pmod{M}.$

During the scan, one term contributes

$T_tL_{t+1}\pmod{M},$

then the coefficient is multiplied by the rational step factor above, and the Lucas pair is shifted backward by one index. No table of all coefficients or all Lucas numbers is needed.

Step 4: Worked Example for \(n=8\)

For \(n=8\), we have \(r=7\). Starting from \(T_7=1\), the recurrence yields

$T_7=1,\quad T_6=6,\quad T_5=20,\quad T_4=48,\quad T_3=90,\quad T_2=132,\quad T_1=132.$

The required Lucas values are

$L_2=3,\quad L_3=4,\quad L_4=7,\quad L_5=11,\quad L_6=18,\quad L_7=29,\quad L_8=47.$

Therefore

$f(8)=132\cdot 3+132\cdot 4+90\cdot 7+48\cdot 11+20\cdot 18+6\cdot 29+1\cdot 47=2663,$

which matches the sample check used by the implementations.

Step 5: Remove Per-Term Modular Inversions

The denominator in the coefficient update is

$d_t=t(r-t+1).$

Since \(r=10^8-1\lt M\), both factors are nonzero modulo \(M\), so every \(d_t\) is invertible. Computing each inverse separately would be far too expensive. Instead, the denominators are grouped into blocks. For one block \(d_1,\dots,d_m\), a single inverse of the total product is enough:

$d_i^{-1}=\left(\prod_{j=1}^{m} d_j\right)^{-1}\prod_{j\ne i} d_j \pmod{M}.$

This replaces \(m\) costly modular exponentiations by one exponentiation plus \(O(m)\) multiplications.

How the Code Works

The C++, Python, and Java implementations all follow the same plan. First they compute the Lucas starting pair with fast doubling under modulo \(M\). Then they process the coefficient recurrence from high \(t\) down to low \(t\) in fixed-size blocks, materializing the denominators \(t(r-t+1)\) for the current block and batch-inverting them.

Inside each block, the implementation adds the current contribution \(T_tL_{t+1}\), updates the coefficient using the precomputed inverse for that step, and moves the Lucas pair backward using \(L_{t-1}=L_{t+1}-L_t\). This streaming design keeps the memory footprint small while still reproducing the validation checkpoints \(f(8)=2663\) and \(f(20)=742296999\).

Complexity Analysis

Fast doubling costs \(O(\log n)\) time. The main scan visits each \(t\) once, so the total work is \(O(n)\) modular multiplications. Batch inversion keeps the number of modular exponentiations proportional to the number of blocks rather than the number of terms. With block size \(B\), the memory usage is \(O(B)\), and the total runtime is linear in \(n\) apart from the tiny logarithmic startup cost.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=739
2. Lucas numbers: Wikipedia — Lucas number
3. Fast doubling for Fibonacci numbers: cp-algorithms — Fibonacci numbers
4. Ballot-number background: Wikipedia — Bertrand's ballot theorem
5. Modular inverses: Wikipedia — Modular multiplicative inverse