693. Finite Sequence Generator

Two positive integers $x$$x$ and $y$$y$ ($x>y$$x > y$) can generate a sequence in the following manner:

• $a_x=y$$a_x = y$ is the first term,

• $a_{z+1}=a_z^{2}modz$$a_{z+1} = a_z^2 \bmod z$ for $z=x,x+1,x+2,\dots$$z = x, x+1,x+2,\ldots$ and

• the generation stops when a term becomes 0 or 1.

The number of terms in this sequence is denoted $l(x,y)$$l(x,y)$.

For example, with $x=5$$x = 5$ and $y=3$$y = 3$, we get $a_5=3$$a_5 = 3$, $a_6=3^{2}mod5=4$$a_6 = 3^2 \bmod 5 = 4$, $a_7=4^{2}mod6=4$$a_7 = 4^2\bmod 6 = 4$, etc. Giving the sequence of 29 terms: $3,4,4,2,4,7,9,4,4,3,9,6,4,16,4,16,16,4,16,3,9,6,10,19,25,16,16,8,0$$3,4,4,2,4,7,9,4,4,3,9,6,4,16,4,16,16,4,16,3,9,6,10,19,25,16,16,8,0$ Hence $l(5,3)=29$$l(5,3) = 29$.

$g(x)$$g(x)$ is defined to be the maximum value of $l(x,y)$$l(x,y)$ for $y<x$$y < x$. For example, $g(5)=29$$g(5) = 29$.

Further, define $f(n)$$f(n)$ to be the maximum value of $g(x)$$g(x)$ for $x\le n$$x \le n$. For example, $f(100)=145$$f(100) = 145$ and $f(10000)=8824$$f(10\,000) = 8824$.

Find $f(3000000)$$f(3\,000\,000)$.

693. 有限序列生成器

我们可以使用两个正整数 $x$$x$、$y$$y$（$x>y$$x > y$），通过以下方式生成一个序列：

• $a_x=y$$a_x = y$。

• 当正整数 $z\ge x$$z \geq x$ 时，$a_{z+1}=a_z^{2}modz$$a_{z+1} = a_z^2 \bmod z$。

• 当其中一项为 0 或 1 时，停止生成。

记 $l(x,y)$$l(x, y)$ 为这个序列的项数。例如：$x=5$$x = 5$、$y=3$$y = 3$ 时，可以得到 $a_5=3$$a_5 = 3$，$a_6=3^{2}mod5=4$$a_6 = 3^2 \bmod 5 = 4$，$a_7=4^{2}mod6=4$$a_7 = 4^2\bmod 6 = 4$，如此往复，可以得到这个序列的 29 个项： $3,4,4,2,4,7,9,4,4,3,9,6,4,16,4,16,16,4,16,3,9,6,10,19,25,16,16,8,0$$3,4,4,2,4,7,9,4,4,3,9,6,4,16,4,16,16,4,16,3,9,6,10,19,25,16,16,8,0$，故 $l(5,3)=29$$l(5,3) = 29$。

记 $g(x)$$g(x)$ 为对于所有 $y<x$$y < x$，$l(x,y)$$l(x,y)$ 的最大值。已知：$g(5)=29$$g(5) = 29$。

记 $f(n)$$f(n)$ 为对于所有 $x\le n$$x \le n$，$g(x)$$g(x)$ 的最大值。已知：$f(100)=145$$f(100) = 145$ 且 $f(10000)=8824$$f(10\,000) = 8824$。

求 $f(3000000)$$f(3\,000\,000)$。

点 这个链接 回到源站。

点 这个链接 回到详细版题目目录。