Problem 319: Bounded Sequences

Mathematical Foundation

Definition. For real $\alpha \ge 2$, the sequence $(\lfloor\alpha\rfloor, \lfloor\alpha^2\rfloor, \ldots, \lfloor\alpha^n\rfloor)$ is the $\alpha$-floor sequence of length $n$. Let $t(n)$ count the distinct $\alpha$-floor sequences for $\alpha \in [2,3)$.

Lemma 1 (Counting Function $g$). Define $G(v, m) = \sum_{j=1}^{m} v^j = v \cdot \frac{v^m - 1}{v - 1}$ and $g(m) = G(3, m) - G(2, m)$. Then $g(m)$ counts, with appropriate multiplicity, the total number of integer sequences of length $m$ consistent with some $\alpha \in [2,3)$ (before applying Mobius inversion to account for primitivity).

Proof. For each position $j$, the number of possible values of $\lfloor\alpha^j\rfloor$ as $\alpha$ ranges over $[2,3)$ is bounded by $3^j - 2^j$ (the interval $[2^j, 3^j)$ contains that many integers). The function $G(v,m)$ sums geometric series counting lattice points under power curves. The difference $g(m) = G(3,m) - G(2,m)$ aggregates these counts. $\square$

Theorem 1 (Mobius Inversion Formula). The count of distinct sequences is:

where $\mu$ is the Mobius function.

Proof. A sequence of length $n$ arising from $\alpha \in [2,3)$ may coincide with a sequence of length $d | n$ extended periodically (in terms of the $\alpha$-intervals). The inclusion-exclusion via Mobius inversion removes these overcounts:

Lemma 2 (Matrix Exponentiation for $G(v,m)$). $G(v,m) \bmod M$ is computable in $O(\log m)$ via:

so $G(v, m) = v \cdot [\text{matrix}^m]_{0,1}$.

Proof. By induction on $m$. The base case $m = 1$ gives $\begin{pmatrix} v & 1 \\ 0 & 1 \end{pmatrix}^1 = \begin{pmatrix} v & 1 \\ 0 & 1 \end{pmatrix}$, and $G(v,1) = v \cdot 1 = v$. For the inductive step, multiplying on the right by $\begin{pmatrix} v & 1 \\ 0 & 1 \end{pmatrix}$:

The identity $v^m + \frac{v^m-1}{v-1} = \frac{v^{m+1}-1}{v-1}$ is verified algebraically. $\square$

Theorem 2 (Efficient Summation via Mertens Function). Since $\lfloor n/k \rfloor$ takes only $O(\sqrt{n})$ distinct values, group terms:

where $M(x) = \sum_{i=1}^{x} \mu(i)$ is the Mertens function and $[k_1, k_2]$ is the range of $k$ with $\lfloor n/k \rfloor = q$.

Proof. Regrouping the sum by distinct values of $\lfloor n/k \rfloor$ and using partial sums of $\mu$. $\square$

Lemma 3 (Mertens Function Computation). $M(n)$ satisfies:

Sieve $\mu(k)$ for $k \le n^{2/3}$; compute $M$ recursively with memoization for larger arguments. Total time: $O(n^{2/3})$.

Proof. From $\sum_{d|n}\mu(d) = [n=1]$, summing over $n$: $\sum_{k=1}^{n} M(\lfloor n/k \rfloor) = 1$. Isolating $k=1$: $M(n) = 1 - \sum_{k=2}^{n} M(\lfloor n/k \rfloor)$. The hyperbolic summation trick (grouping by distinct values of $\lfloor n/k \rfloor$) combined with sieving up to $n^{2/3}$ gives $O(n^{2/3})$ complexity. $\square$

Verification. $G(3,10) = 3(3^{10}-1)/2 = 88572$, $G(2,10) = 2(2^{10}-1) = 2046$, $g(10) = 86526$.

Editorial

t(n) = number of sequences (x_1, …, x_n) where x_i = floor(alpha^i) for some alpha in [2, 3). Formula: t(n) = sum_{k=1}^{n} mu(k) * g(floor(n/k)) where g(m) = G(3,m) - G(2,m), G(v,m) = v * (v^m - 1) / (v - 1) Uses Mobius function prefix sums (Mertens function) and matrix exponentiation. We sieve mu(k) for k <= n^(2/3), compute prefix sums M(k). We then iterate over large arguments, compute M(x) recursively with memoization. Finally, sum all contributions modulo MOD.

Pseudocode

Input: n = 10^10, MOD = 10^9
Output: t(n) mod MOD
Sieve mu(k) for k <= n^(2/3), compute prefix sums M(k)
For large arguments, compute M(x) recursively with memoization:
Enumerate distinct values q = floor(n/k):
Sum all contributions modulo MOD
Return result

Complexity Analysis

• Time: $O(n^{2/3})$ for Mertens function computation. $O(\sqrt{n} \cdot \log n)$ for matrix exponentiations over $O(\sqrt{n})$ distinct values. Total: $O(n^{2/3})$.
• Space: $O(n^{2/3})$ for the sieve and memoization table.

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 319: Bounded Sequences
 *
 * t(n) = sum_{k=1}^{n} mu(k) * g(floor(n/k))
 * where g(m) = G(3,m) - G(2,m), G(v,m) = v*(v^m - 1)/(v-1)
 *
 * Uses:
 * - Sieve for Mobius function prefix sums up to LMT
 * - Mertens function via recursive formula with memoization for large values
 * - Matrix exponentiation for G(v,m) mod MOD
 *
 * Answer: 268457129
 */

typedef long long i64;

const i64 N = 10000000000LL; // 10^10
const i64 MOD = 1000000000LL; // 10^9
const int LMT = 10000000;     // 10^7

i64 mu_prefix[LMT + 1]; // prefix sum of Mobius function
map<i64, i64> memo_mertens;

// Compute Mertens function M(n) = sum_{k=1}^{n} mu(k), modulo MOD
i64 mertens(i64 n) {
    if (n <= LMT) return mu_prefix[n];
    if (memo_mertens.count(n)) return memo_mertens[n];
    i64 ret = 1; // M(1) = mu(1) = 1
    for (i64 i = 2, j; i <= n; i = j) {
        j = n / (n / i) + 1;
        ret = (ret + MOD - (j - i) % MOD * mertens(n / i) % MOD) % MOD;
    }
    return memo_mertens[n] = ret;
}

// 2x2 matrix multiplication mod MOD
typedef i64 mat[2][2];

void matmul(mat a, mat b, mat c) {
    mat t;
    memset(t, 0, sizeof(mat));
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                t[i][k] = (t[i][k] + a[i][j] % MOD * (b[j][k] % MOD)) % MOD;
    memcpy(c, t, sizeof(mat));
}

// G(v, x) = v * (v^x - 1) / (v - 1) mod MOD, via matrix exponentiation
// [v 1; 0 1]^x has entry [0][1] = (v^x - 1)/(v - 1)
i64 G(int v, i64 x) {
    if (x == 0) return 0;
    mat A, B;
    A[0][0] = v; A[0][1] = 1;
    A[1][0] = 0; A[1][1] = 1;
    memset(B, 0, sizeof(B));
    B[0][0] = B[1][1] = 1; // identity
    for (i64 e = x; e; e >>= 1) {
        if (e & 1) matmul(B, A, B);
        matmul(A, A, A);
    }
    return (i64)v % MOD * (B[0][1] % MOD) % MOD;
}

i64 g(i64 x) {
    return (G(3, x) - G(2, x) + MOD) % MOD;
}

int main() {
    // Sieve Mobius function and compute prefix sums
    vector<int> mu_val(LMT + 1, 0);
    vector<bool> is_composite(LMT + 1, false);
    vector<int> primes;
    mu_val[1] = 1;

    for (int i = 2; i <= LMT; i++) {
        if (!is_composite[i]) {
            primes.push_back(i);
            mu_val[i] = -1;
        }
        for (int j = 0; j < (int)primes.size() && (i64)i * primes[j] <= LMT; j++) {
            int t = i * primes[j];
            is_composite[t] = true;
            if (i % primes[j] == 0) {
                mu_val[t] = 0;
                break;
            } else {
                mu_val[t] = -mu_val[i];
            }
        }
    }

    mu_prefix[0] = 0;
    for (int i = 1; i <= LMT; i++)
        mu_prefix[i] = (mu_prefix[i - 1] + mu_val[i] % MOD + MOD) % MOD;

    // Compute t(N) = sum_{k=1}^{N} mu(k) * g(floor(N/k))
    // Group by distinct values of floor(N/k)
    i64 ans = 0;
    i64 prev_mertens = 0; // M(0) = 0
    for (i64 i = 1, j; i <= N; i = j) {
        j = N / (N / i) + 1;
        i64 cur_mertens = mertens(j - 1);
        i64 block_mu_sum = (cur_mertens - prev_mertens + MOD) % MOD;
        ans = (ans + block_mu_sum % MOD * g(N / i) % MOD) % MOD;
        prev_mertens = cur_mertens;
    }

    cout << ans % MOD << endl;
    return 0;
}

"""
Problem 319: Bounded Sequences

t(n) = number of sequences (x_1, ..., x_n) where x_i = floor(alpha^i)
for some alpha in [2, 3).

Formula: t(n) = sum_{k=1}^{n} mu(k) * g(floor(n/k))
where g(m) = G(3,m) - G(2,m), G(v,m) = v * (v^m - 1) / (v - 1)

Uses Mobius function prefix sums (Mertens function) and matrix exponentiation.

Answer: 268457129
"""

import sys
sys.setrecursionlimit(200000)

MOD = 10**9
N = 10**10
LMT = 10**7

def solve():
    # Sieve Mobius function up to LMT
    mu_val = [0] * (LMT + 1)
    mu_val[1] = 1
    is_composite = [False] * (LMT + 1)
    primes = []

    for i in range(2, LMT + 1):
        if not is_composite[i]:
            primes.append(i)
            mu_val[i] = -1
        for p in primes:
            if i * p > LMT:
                break
            is_composite[i * p] = True
            if i % p == 0:
                mu_val[i * p] = 0
                break
            else:
                mu_val[i * p] = -mu_val[i]

    # Prefix sums of Mobius function mod MOD
    mu_prefix = [0] * (LMT + 1)
    for i in range(1, LMT + 1):
        mu_prefix[i] = (mu_prefix[i - 1] + mu_val[i]) % MOD

    # Memoized Mertens function for large values
    memo = {}

    def mertens(n):
        if n <= LMT:
            return mu_prefix[n]
        if n in memo:
            return memo[n]
        ret = 1  # M(1) = 1
        i = 2
        while i <= n:
            j = n // (n // i) + 1
            ret = (ret + MOD - (j - i) % MOD * mertens(n // i) % MOD) % MOD
            i = j
        memo[n] = ret
        return ret

    # Matrix exponentiation for G(v, x) = v * (v^x - 1) / (v - 1) mod MOD
    def mat_mul(A, B):
        return [
            [(A[0][0] * B[0][0] + A[0][1] * B[1][0]) % MOD,
             (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % MOD],
            [(A[1][0] * B[0][0] + A[1][1] * B[1][0]) % MOD,
             (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % MOD]
        ]

    def G(v, x):
        if x == 0:
            return 0
        A = [[v, 1], [0, 1]]
        B = [[1, 0], [0, 1]]  # identity
        e = x
        while e > 0:
            if e & 1:
                B = mat_mul(B, A)
            A = mat_mul(A, A)
            e >>= 1
        return v * B[0][1] % MOD

    def g(x):
        return (G(3, x) - G(2, x) + MOD) % MOD

    # Compute t(N) = sum_{k=1}^{N} mu(k) * g(floor(N/k))
    ans = 0
    prev_m = 0
    i = 1
    while i <= N:
        j = N // (N // i) + 1
        cur_m = mertens(j - 1)
        block_sum = (cur_m - prev_m + MOD) % MOD
        ans = (ans + block_sum * g(N // i)) % MOD
        prev_m = cur_m
        i = j

    print(ans)

if __name__ == "__main__":
    solve()