Problem 771

Pseudo Geometric Sequences

We define a pseudo-geometric sequence to be a finite sequence $a_{0}, a_{1}, \dots, a_{n}$ of positive integers, satisfying the following conditions:

$n \geq 4$ , i.e. the sequence has at least 5 terms.
$0 < a_{0} < a_{1} < \dots < a_{n}$ , i.e. the sequence is strictly increasing.
$| a_{i}^{2} - a_{i - 1} a_{i + 1} | \leq 2$ for $1 \leq i \leq n - 1$ .

Let $G (N)$ be the number of different pseudo-geometric sequences whose terms do not exceed $N$ .

For example, $G (6) = 4$ , as the following $4$ sequences give a complete list:

$1, 2, 3, 4, 5 1, 2, 3, 4, 6 2, 3, 4, 5, 6 1, 2, 3, 4, 5, 6$

Also, $G (10) = 26$ , $G (100) = 4710$ and $G (1000) = 496805$ .

Find $G (10^{18})$ . Give your answer modulo $1 000 000 007$ .

伪等比数列

我们定义满足如下条件的有限正整数数列 $a_{0}, a_{1}, \dots, a_{n}$ 为伪等比数列：

$n \geq 4$ ，即数列至少有5项。
$0 < a_{0} < a_{1} < \dots < a_{n}$ ，即数列严格递增。
对于 $1 \leq i \leq n - 1$ ，均有 $| a_{i}^{2} - a_{i - 1} a_{i + 1} | \leq 2$ 。

记 $G (N)$ 为各项均不超过 $N$ 的不同伪等比数列的总数。

例如， $G (6) = 4$ ，这 $4$ 种数列如下所示：

$1, 2, 3, 4, 5 1, 2, 3, 4, 6 2, 3, 4, 5, 6 1, 2, 3, 4, 5, 6$

此外还已知 $G (10) = 26$ ， $G (100) = 4710$ 以及 $G (1000) = 496805$ 。

求 $G (10^{18})$ ，并将你的答案对 $1 000 000 007$ 取余。