Detailed mathematical approach

Problem Summary

We count sequences

$$x_1,x_2,\dots,x_n$$

such that

$$x_1=2,$$

$$x_{i-1}\lt x_i\qquad (2\le i\le n),$$

and for all \(1\le i,j\le n\),

$$(x_i)^j \lt (x_j+1)^i.$$

Let \(t(n)\) be the number of such sequences. We are given

$$t(2)=5,\qquad t(5)=293,\qquad t(10)=86195,\qquad t(20)=5227991891,$$

and we must find

$$t(10^{10})\pmod{10^9}.$$

Mathematical Approach

1) The defining inequalities mean "take floors of powers of one real number".

Rewrite the condition

$$(x_i)^j \lt (x_j+1)^i$$

as

$$x_i^{1/i} \lt (x_j+1)^{1/j} \qquad \text{for all } i,j.$$

So the intervals

$$I_i=\bigl(x_i^{1/i},\ (x_i+1)^{1/i}\bigr)$$

all overlap. Therefore there exists a real number \(y\) belonging to every \(I_i\), and for that \(y\) we have

$$x_i \lt y^i \lt x_i+1,$$

hence

$$x_i=\lfloor y^i\rfloor.$$

Conversely, any \(y\in(2,3)\) defines a valid sequence by setting \(x_i=\lfloor y^i\rfloor\). The condition \(x_1=2\) is exactly \(2\le y \lt 3\), and because \(y\gt1\), the sequence is strictly increasing.

2) So \(t(n)\) is a boundary-counting problem on \(y\in[2,3)\).

As \(y\) moves through \([2,3)\), the sequence

$$\bigl(\lfloor y\rfloor,\lfloor y^2\rfloor,\dots,\lfloor y^n\rfloor\bigr)$$

changes only when some \(y^k\) crosses an integer. The change points are exactly the numbers

$$y=m^{1/k},\qquad 1\le k\le n,\qquad 2^k \lt m \lt 3^k.$$

Therefore \(t(n)\) equals

$$1+\text{(number of distinct boundary points in }(2,3)\text{ visible up to exponent }n).$$

3) Distinct roots are the real difficulty.

If we simply count all pairs \((m,k)\) with \(2^k \lt m \lt 3^k\), we overcount. For example, the same boundary might be representable both as \(m^{1/k}\) and as \(u^{1/d}\) if \(m\) is a perfect power.

To remove duplicates, define:

$$f(k)=3^k-2^k-1,$$

the number of integers strictly between \(2^k\) and \(3^k\), and

$$g(k)=\text{number of boundary points whose minimal exponent is exactly }k.$$

Every integer \(m\) counted by \(f(k)\) corresponds to a boundary whose minimal exponent divides \(k\). Hence

$$f(k)=\sum_{d\mid k} g(d).$$

4) Möbius inversion produces the primitive counts.

Applying Möbius inversion gives

$$g(k)=\sum_{d\mid k}\mu(d)\,f\!\left(\frac{k}{d}\right),$$

where \(\mu\) is the Möbius function.

Since each primitive boundary of degree \(k\) contributes exactly one new cut point once \(k\le n\), we have

$$t(n)=1+\sum_{k=1}^{n} g(k).$$

Substituting the inversion formula and swapping the order of summation yields

$$t(n)=1+\sum_{k=1}^{n} f(k)\,M\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right),$$

where

$$M(x)=\sum_{m\le x}\mu(m)$$

is the Mertens function.

This is exactly the formula implemented by the code, with

$$f(k)=3^k-2^k-1.$$

5) Worked example: why \(t(2)=5\).

For \(n=2\), only \(k=2\) contributes new boundaries, because

$$f(1)=3-2-1=0,\qquad f(2)=9-4-1=4.$$

The four boundary points are

$$\sqrt5,\ \sqrt6,\ \sqrt7,\ \sqrt8.$$

They split the interval \([2,3)\) into five parts, producing the five sequences

$$\{2,4\},\ \{2,5\},\ \{2,6\},\ \{2,7\},\ \{2,8\}.$$

So

$$t(2)=5,$$

exactly as stated.

6) Prefix sums of the coefficients.

The code needs many interval sums of

$$a_k=f(k)=3^k-2^k-1.$$

Define

$$A(m)=\sum_{k=1}^{m} a_k.$$

Using geometric-series formulas,

$$A(m)=\frac{3^{m+1}-3}{2}-(2^{m+1}-2)-m.$$

Therefore any block \([l,r]\) contributes

$$\sum_{k=l}^{r}a_k=A(r)-A(l-1).$$

Because the final modulus is \(10^9\), division by \(2\) is not invertible modulo \(10^9\). The implementation avoids trouble by first computing \(3^{m+1}\) modulo \(2\cdot10^9\), so the numerator is still even and can be safely halved.

7) Harmonic partition of the outer sum.

The quotient

$$q=\left\lfloor\frac{n}{k}\right\rfloor$$

is constant on long ranges \([l,r]\). So instead of summing one \(k\) at a time, we group all \(k\) in the same block:

$$\sum_{k=1}^{n} a_k\,M\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right) =\sum_{\text{blocks }[l,r]} \bigl(A(r)-A(l-1)\bigr)\,M(q).$$

The number of such blocks is only about \(2\sqrt n\), not \(n\).

8) Fast computation of the Mertens function.

For small values, \(\mu\) and \(M\) are precomputed with a linear sieve. For large \(x\), the code uses the classical identity

$$M(x)=1-\sum_{l=2}^{x}(r-l+1)\,M\!\left(\left\lfloor\frac{x}{l}\right\rfloor\right),$$

where each interval \([l,r]\) shares the same quotient \(\lfloor x/l\rfloor\). Memoization makes each large \(M(x)\) value get computed only once.

Algorithm

1) Use the combinatorial reformulation

$$t(n)=1+\sum_{k=1}^{n}(3^k-2^k-1)\,M\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right).$$

2) Precompute \(\mu\) and \(M\) up to about \(n^{2/3}\) with a linear sieve.

3) Compute large \(M(x)\) recursively with quotient grouping and memoization.

4) Group the outer sum into blocks of constant \(\lfloor n/k\rfloor\).

5) Use the closed form for \(A(m)\) to evaluate each block in \(O(1)\).

Complexity Analysis

The sieve runs up to roughly \(n^{2/3}\). The outer harmonic decomposition has only

$$O(\sqrt n)$$

blocks. Combined with memoized Mertens queries, this is dramatically faster than summing \(10^{10}\) terms one by one.

Checks And Final Result

The source validates

$$t(2)=5,\qquad t(5)=293,\qquad t(10)=86195,\qquad t(20)=5227991891.$$

For

$$n=10^{10},$$

the program outputs

$$268457129$$

modulo \(10^9\).

Further Reading

1. Problem page: https://projecteuler.net/problem=319
2. Möbius function: https://en.wikipedia.org/wiki/Möbius_function
3. Mertens function: https://en.wikipedia.org/wiki/Mertens_function