Detailed mathematical approach

Problem Summary

An odd-run composition of \(n\) is a composition \(n=p_1+p_2+\cdots+p_m\) in which every maximal block of equal adjacent parts has odd length. For example, \(2+1+1+1\) is valid because the run of 1's has length 3, while \(2+2+1\) is invalid because the run of 2's has length 2.

The problem asks for the number \(u_{100000}\) of such compositions of \(100000\), reduced modulo \(1{,}111{,}124{,}111\). The solution does not enumerate compositions. Instead it builds a generating function for allowed runs, converts that to a divisor-sum coefficient sequence, and then extracts the required coefficient by inverting a formal power series.

Mathematical Approach

Let \(u_n\) be the number of odd-run compositions of \(n\), and let

$$U(x)=\sum_{n\ge 0}u_nx^n,$$

with \(u_0=1\) for the empty composition. The derivation becomes clean once compositions are viewed as sequences of runs instead of sequences of individual parts.

Runs of a Fixed Part Size

Fix a part size \(j\ge 1\). A maximal run consisting of \(j\)'s may have length \(1,3,5,\dots\), so its contribution to the ordinary generating function is

$$R_j(x)=x^j+x^{3j}+x^{5j}+\cdots=\frac{x^j}{1-x^{2j}}.$$

An odd-run composition is therefore a sequence of such runs where two consecutive runs are not allowed to have the same part size, because otherwise they would merge into a longer run.

Smirnov Words and the Global Generating Function

A composition can be regarded as a word over the infinite alphabet \(\{1,2,3,\dots\}\), where the letter \(j\) carries weight \(x^j\). After compressing each maximal run into one symbol, we get a word with no equal adjacent letters. For such words, the standard Smirnov-word generating function with letter weights \(y_j\) is

$$S(\{y_j\})=\frac{1}{1-\sum_{j\ge 1}\frac{y_j}{1+y_j}}.$$

One way to see this is to start from unrestricted words, whose generating function is \(1/(1-\sum z_j)\), and replace a letter \(j\) by a positive run of \(j\)'s. Then \(y_j=z_j+z_j^2+z_j^3+\cdots=z_j/(1-z_j)\), so \(z_j=y_j/(1+y_j)\).

For odd-run compositions we substitute \(y_j=R_j(x)\), which gives

$$U(x)=\frac{1}{1-\sum_{j\ge 1}\frac{R_j(x)}{1+R_j(x)}}=\frac{1}{1-\sum_{j\ge 1}\frac{x^j}{1+x^j-x^{2j}}}.$$

So the whole problem is reduced to understanding the series

$$A(x)=\sum_{j\ge 1}\frac{x^j}{1+x^j-x^{2j}}.$$

Why Fibonacci Numbers Appear

The Fibonacci generating function is

$$\sum_{m\ge 1}F_m t^m=\frac{t}{1-t-t^2},\qquad F_1=F_2=1.$$

Substituting \(t=-x^j\) yields

$$\frac{x^j}{1+x^j-x^{2j}}=\sum_{m\ge 1}(-1)^{m-1}F_m x^{jm}.$$

Now collect equal powers of \(x\). Writing

$$A(x)=\sum_{n\ge 1}a_nx^n,$$

the coefficient of \(x^n\) receives one contribution from each factorization \(n=jm\). Equivalently,

$$a_n=\sum_{d\mid n}(-1)^{d-1}F_d.$$

This divisor sum is exactly the sequence constructed by the implementations before any fast polynomial work begins.

The Coefficient Recurrence

Since \(U(x)=1/(1-A(x))\), we have

$$\bigl(1-A(x)\bigr)U(x)=1.$$

Comparing coefficients gives the fundamental recurrence

$$u_0=1,\qquad u_n=\sum_{k=1}^{n}a_k\,u_{n-k}\quad(n\ge 1).$$

This already solves the problem conceptually: once the divisor-sum coefficients \(a_k\) are known, the answer sequence is determined uniquely.

Worked Example: \(n=5\)

The first divisor-sum coefficients are

$$a_1=1,\quad a_2=0,\quad a_3=3,\quad a_4=-3,\quad a_5=6.$$

Using the recurrence,

$$u_1=1,\qquad u_2=1,\qquad u_3=4,\qquad u_4=4,$$

and then

$$u_5=a_1u_4+a_2u_3+a_3u_2+a_4u_1+a_5u_0=4+0+3-3+6=10.$$

This matches direct inspection. Valid examples include \(5\), \(1+3+1\), \(2+1+2\), \(2+1+1+1\), and \(1+1+1+1+1\). Invalid examples such as \(2+2+1\) or \(1+1+3\) fail because they contain an even-length run.

How the Code Works

Building the Coefficients of \(A(x)\)

The C++, Python, and Java implementations first generate Fibonacci numbers modulo \(1{,}111{,}124{,}111\). Then, for each \(d\), they add the signed Fibonacci value \((-1)^{d-1}F_d\) to every multiple of \(d\). After this divisor sweep, the array holds \(a_1,a_2,\dots,a_n\), the coefficients of \(A(x)\).

Recovering \(U(x)=1/(1-A(x))\)

A direct use of the coefficient recurrence is quadratic, so it is only suitable for small verification cases. For the real target \(n=100000\), the implementations form the series \(B(x)=1-A(x)\) and compute its inverse modulo \(x^{n+1}\) by Newton iteration. If \(G(x)\) is correct up to degree \(m-1\), the next approximation is

$$G_{\text{new}}(x)=G(x)\bigl(2-B(x)G(x)\bigr)\pmod{x^m}.$$

Because the constant term of \(B(x)\) is 1, this inverse exists as a formal power series. Each Newton step roughly doubles the number of correct coefficients, and the coefficient of \(x^n\) in the final inverse is exactly \(u_n\).

Fast Polynomial Multiplication

The expensive part of Newton iteration is polynomial multiplication. The C++ and Java implementations evaluate these convolutions with a number-theoretic transform under three auxiliary NTT-friendly prime moduli, then recombine the results with the Chinese remainder theorem to recover coefficients modulo \(1{,}111{,}124{,}111\). The Python implementation is a thin wrapper around the same C++ computation, so all three language entries follow the same mathematical pipeline.

Complexity Analysis

Constructing the divisor-sum coefficients costs

$$\sum_{d=1}^{n}\left\lfloor\frac{n}{d}\right\rfloor=O(n\log n).$$

The fast phase is the formal power-series inversion. With FFT-style multiplication cost \(M(n)=O(n\log n)\), Newton iteration runs in \(O(M(n)\log n)\), which here is \(O(n\log^2 n)\). Memory usage is \(O(n)\) for the coefficient arrays and transform buffers.

The slower recurrence \(u_n=\sum_{k=1}^{n}a_ku_{n-k}\) is \(O(n^2)\) and appears only as a correctness check on small inputs. The actual computation for \(n=100000\) relies on the quasi-linear series inversion.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=929
2. Compositions of integers: Wikipedia - Composition (combinatorics)
3. Fibonacci numbers and their generating function: Wikipedia - Fibonacci number
4. Formal power series: Wikipedia - Formal power series
5. Generating functions: Wikipedia - Generating function
6. Number-theoretic transform: Wikipedia - Number-theoretic transform
7. Chinese remainder theorem: Wikipedia - Chinese remainder theorem