Project Euler Problem 319

Solution

Answer: 268457129

Let

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

satisfy

$x_1=2$,
$x_{i-1}<x_i$,
and for all $i,j$,

$$x_i^j<(x_j+1)^i.$$

We seek $t(n)$, the number of such sequences, for $n=10^{10}$, modulo $10^9$.

1. Mathematical analysis

The key observation is that the condition

$$x_i^j < (x_j+1)^i$$

can be rewritten as

$$x_i^{1/i} < (x_j+1)^{1/j}.$$

Thus all intervals

$$I_i=\left(x_i^{1/i},,(x_i+1)^{1/i}\right)$$

must have nonempty intersection.

Hence there exists a real number $\lambda\in(2,3)$ such that for every $i$,

$$x_i < \lambda^i < x_i+1.$$

Therefore

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

So every valid sequence corresponds uniquely to some interval of $\lambda\in(2,3)$, and the sequence changes only when $\lambda$ crosses a boundary

$$\lambda = k^{1/i}, \qquad 2^i \le k < 3^i.$$

Thus:

$$t(n) = #\left{ k^{1/i} : 1\le i\le n,, 2^i\le k<3^i \right}.$$

(Notice $\lambda=2$ itself is included via $k=2^i$.)

Canonical counting

Define the minimal denominator $d$ of a boundary value $r$ as the smallest positive integer such that $r^d\in\mathbb Z$.

Let $g(d)$ be the number of boundary points whose minimal denominator is exactly $d$.

Then

$$t(n)=\sum_{d\le n} g(d).$$

For fixed $d$, every candidate looks like

$$r = m^{1/d}, \qquad 2^d\le m<3^d.$$

Its denominator is not minimal iff $m$ is an $e$-th power for some divisor $e\mid d$, $e>1$.

By Möbius inversion:

$$g(d) = \sum_{e\mid d} \mu(e) \left(3^{d/e}-2^{d/e}\right),$$

where $\mu$ is the Möbius function.

Therefore

$$t(n) = \sum_{d\le n} \sum_{e\mid d} \mu(e) \left(3^{d/e}-2^{d/e}\right).$$

Swap summation with $d=ek$:

$$t(n) = \sum_{e\le n} \mu(e) \sum_{k\le n/e} (3^k-2^k).$$

Define

$$F(m) = \sum_{k=1}^{m}(3^k-2^k).$$

Using geometric sums:

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

So:

$$t(n) = \sum_{e\le n} \mu(e), F!\left(\left\lfloor \frac ne \right\rfloor\right).$$

This can be computed in about $O(\sqrt n)$ distinct floor-values using the summatory Möbius function (Mertens function).

2. Python implementation

from functools import lru_cache

MOD = 10**9
MOD2 = 2 * MOD

def solve(n):
    # Precompute Möbius up to a cutoff
    LIMIT = 2_000_000

    mu = [0] * (LIMIT + 1)
    mu[1] = 1

    primes = []
    composite = [False] * (LIMIT + 1)

    # Linear sieve for Möbius
    for i in range(2, LIMIT + 1):
        if not composite[i]:
            primes.append(i)
            mu[i] = -1

        for p in primes:
            v = i * p
            if v > LIMIT:
                break

            composite[v] = True

            if i % p == 0:
                mu[v] = 0
                break
            else:
                mu[v] = -mu[i]

    # Prefix Mertens values
    mertens_prefix = [0] * (LIMIT + 1)
    for i in range(1, LIMIT + 1):
        mertens_prefix[i] = mertens_prefix[i - 1] + mu[i]

    @lru_cache(None)
    def M(x):
        """Summatory Möbius function."""
        if x <= LIMIT:
            return mertens_prefix[x]

        result = 1
        l = 2

        while l <= x:
            q = x // l
            r = x // q
            result -= (r - l + 1) * M(q)
            l = r + 1

        return result

    def F(m):
        """Sum_{k=1..m} (3^k - 2^k) modulo 1e9."""
        s3 = ((pow(3, m + 1, MOD2) - 3) % MOD2) // 2
        s2 = (pow(2, m + 1, MOD) - 2) % MOD
        return (s3 - s2) % MOD

    ans = 0
    l = 1

    # Group equal floor(n / i)
    while l <= n:
        q = n // l
        r = n // q

        coeff = M(r) - M(l - 1)
        ans = (ans + coeff * F(q)) % MOD

        l = r + 1

    return ans

print(solve(10**10))

3. Code walkthrough

Linear sieve computes Möbius values $\mu(n)$.
Prefix sums build the Mertens function

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

M(x) for large $x$ uses the standard divide-and-conquer identity:

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

grouping equal quotients.

F(m) computes

$$\sum_{k=1}^{m}(3^k-2^k)$$

via geometric sums modulo $10^9$.

The main loop groups equal values of

$$\left\lfloor \frac{n}{i}\right\rfloor$$

to achieve near $O(\sqrt n)$ complexity.

4. Verification

Checks against known values:

$t(2)=5$ ✓
$t(5)=293$ ✓
$t(10)=86195$ ✓
$t(20)=5227991891$, which modulo $10^9$ is $227991891$ ✓

Running the algorithm for $n=10^{10}$ gives:

Answer: 268457129