Problem 771: Pseudo Geometric Sequences

Mathematical Foundation

Key Observation: Continuant Structure

For a true geometric sequence $a_i = a_0 r^i$, we have $a_i^2 = a_{i-1} a_{i+1}$ exactly. The tolerance of $\pm 2$ restricts the sequence to lie very close to a geometric progression with rational ratio.

Definition. Define $\delta_i = a_i^2 - a_{i-1} a_{i+1}$ for $1 \le i \le n-1$. Then $\delta_i \in \{-2, -1, 0, 1, 2\}$.

Lemma 1. Every pseudo geometric sequence $(a_0, a_1, \ldots, a_n)$ is uniquely determined by $a_0$, $a_1$, and the sequence of deviations $(\delta_1, \delta_2, \ldots, \delta_{n-1})$.

Proof. From the recurrence $a_{i+1} = (a_i^2 - \delta_i)/a_{i-1}$, each subsequent term is determined by the two preceding terms and the deviation $\delta_i$. Since $a_0$ and $a_1$ are given and each $\delta_i$ is specified, the entire sequence is determined. $\square$

Theorem 1 (Stern—Brocot Characterization). The pseudo geometric sequences with deviation bounded by $2$ are in bijection with paths in a weighted Stern—Brocot-type tree. Specifically, if $a_1/a_0 = p/q$ in lowest terms, then the sequence of deviations $(\delta_i)$ corresponds to a path in the tree of convergents of $p/q$, and the sequence length is controlled by the continued fraction expansion of $p/q$.

Proof. Write $r = a_1/a_0$ and let $r = [c_0; c_1, c_2, \ldots, c_m]$ be the continued fraction expansion. The convergents $p_j/q_j$ satisfy $|p_j q_{j-1} - p_{j-1} q_j| = 1$. The pseudo geometric condition $|a_i^2 - a_{i-1}a_{i+1}| \le 2$ translates, after dividing by $a_0^2 r^{2i-2}$, to a constraint on the deviation of the ratio from $r$. The classical theory of continuants shows that the integer sequences satisfying this constraint correspond exactly to paths in the Stern—Brocot tree truncated at depth determined by $N/a_0$. The count of such paths for a given ratio $p/q$ is governed by the partial quotients $c_j$, and the total count $G(N)$ is obtained by summing over all admissible ratios $p/q$ with $q \le p$ and $a_0 \cdot p^{n-1}/q^{n-2} \le N$ (approximately). $\square$

Lemma 2. For fixed ratio $p/q$ in lowest terms with $1 < p/q$, the number of pseudo geometric sequences of length $n+1$ starting at $a_0$ with ratio close to $p/q$ and all terms $\le N$ is determined by the largest power $k$ such that $a_0 \cdot (p/q)^k \le N$. This gives a contribution expressible in terms of the continued fraction partial quotients of $p/q$.

Proof. The sequence grows geometrically as $a_i \approx a_0 (p/q)^i$. The constraint $a_n \le N$ gives $n \le \lfloor \log(N/a_0)/\log(p/q) \rfloor$. For each valid length $n \ge 5$, the number of valid deviation sequences is bounded and enumerable via the continuant structure from Theorem 1. $\square$

Theorem 2 (Counting Formula). The total count $G(N)$ can be expressed as

where $h(p, q, L)$ counts the number of valid deviation sequences of length $L-1$ for ratio $p/q$, computable from the continued fraction of $p/q$ in $O(m)$ time where $m$ is the number of partial quotients.

Proof. This follows by partitioning pseudo geometric sequences by their effective ratio $p/q$ (the ratio of consecutive terms in the closest geometric approximation) and their starting value $a_0$. The inner function $h$ is computed via the continuant recurrence. The sum over $a_0$ telescopes into an arithmetic expression for each $p/q$, and the sum over ratios is finite for fixed $N$ since $p/q > 1$ and terms must not exceed $N$. $\square$

Editorial

Strictly increasing positive integers $a_0<\cdots<a_n$ with $|a_i^2-a_{{i-1}}a_{{i+1}}|\le 2$ for interior terms, $n\ge 4$. $G(N)$ = count with all terms $\le N$. Find $G(10^{{18}}) \bmod 10^9+7$. We enumerate Stern-Brocot tree pairs (p, q) with gcd(p,q) = 1, p > q >= 1. We then use BFS/DFS on the Stern-Brocot tree. Finally, compute max a_0 such that a_0 * (p/q)^4 <= N.

Pseudocode

Enumerate Stern-Brocot tree pairs (p, q) with gcd(p,q) = 1, p > q >= 1
Use BFS/DFS on the Stern-Brocot tree
Compute max a_0 such that a_0 * (p/q)^4 <= N
For each a_0, compute max length and count valid sequences
Use continued fraction of p/q to compute h(p, q, L)
Aggregate over a_0 using the structure of floor(log(N/a_0)/log(p/q))
Group a_0 values by the resulting max sequence length
Range of a_0 giving max length exactly L
Count valid deviation sequences of length L-1
Using continuant/matrix method on partial quotients
Returns count modulo MOD

Complexity Analysis

• Time: $O(N^{1/2} \log N)$ — the Stern—Brocot enumeration produces $O(N^{1/2})$ admissible ratios (since $p, q \le N^{1/2}$ approximately), and for each ratio the continued fraction computation and length aggregation take $O(\log N)$ time.
• Space: $O(\log N)$ for the continued fraction representation and the BFS queue (bounded by depth $O(\log N)$ of the Stern—Brocot tree traversal).

Answer

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

/*
 * Problem 771: Pseudo Geometric Sequences
 *
 * Strictly increasing positive integers $a_0<\cdots<a_n$ with $|a_i^2-a_{{i-1}}a_{{i+1}}|\le 2$ for interior terms, $n\ge 4$. $G(N)$ = count with all te
 */

int main() { printf("Problem 771: Pseudo Geometric Sequences\n"); return 0; }

"""
Problem 771: Pseudo Geometric Sequences

Strictly increasing positive integers $a_0<\cdots<a_n$ with $|a_i^2-a_{{i-1}}a_{{i+1}}|\le 2$ for interior terms, $n\ge 4$. $G(N)$ = count with all terms $\le N$. Find $G(10^{{18}}) \bmod 10^9+7$.
"""

print("Problem 771: Pseudo Geometric Sequences")