Project Euler 443

题目

GCD sequence

Let \(g(n)\) be a sequence defined as follows:

\(g(4) = 13\),

\(g(n) = g(n-1) + \gcd(n, g(n-1))\), for \(n > 4\).

The first few values are:

\(n\)

\(4\)

\(5\)

\(6\)

\(7\)

\(8\)

\(9\)

\(10\)

\(11\)

\(12\)

\(13\)

\(14\)

\(15\)

\(16\)

\(17\)

\(18\)

\(19\)

\(20\)

\(\dots\)

\(g(n)\)

\(13\)

\(14\)

\(16\)

\(17\)

\(18\)

\(27\)

\(28\)

\(29\)

\(30\)

\(31\)

\(32\)

\(33\)

\(34\)

\(51\)

\(54\)

\(55\)

\(60\)

\(\dots\)

You are given that \(g(1000) = 2524\) and \(g(1000000) = 2624152\).

Find \(g(10^{15})\).

解决方案

令\(N=10^{15}\)，将\(g\)中的前一部分项打印出来，发现对于绝大多数\(n\)，都满足\(g(n)=g(n-1)+1\)。

因此，我们考虑枚举出所有满足\(\gcd(n,g(n-1))>1\)的所有\(n\)，并找到这些\(n\)中最大的一个使得\(n\le N\)，那么\(g(N)=g(n)+N-n.\)

假设目前我们已经知道了某个\(n\)和它的函数值\(g\)，那么转为求下一个最小的\(n'\)使得\(\gcd(n',g(n'-1))>1,n'>n\)，那么在\(d=n+1,n+2,\dots,n'-1\)之前，都满足\(\gcd(d,g(d-1))=1\)。

那么对于一对\(n,g\)，问题转化成求一个最小的\(k\)，使得\(\gcd(n+k+1,g+k)>1\).根据辗转相除的性质，可以写为\(\gcd(g+k,g-n-1)>1\).

可以发现，\(g-n-1\)是一个常数。因此我们将\(g-n-1\)进行分解，并枚举每个质因数\(p_i\)，并求出最小的\(k_i\)使得\(g+k_i\)是\(p_i\)的倍数，最终\(k\)是这些\(k_i\)中最小的一个。

令\(n'=n+k+1\)，那么\(g'=n+k+\gcd(n+k+1,g+k)\)，得到了一组新的\(n',g(n)\)值，由此迭代直到\(N\)处。

代码

from tools import factorization, gcd

N = 10 ** 15
n = 4
g = 13
while True:
    p_list = [u[0] for u in factorization(g - n - 1)]
    nxt = min((g + p - 1) // p * p for p in p_list)
    k = nxt - g
    np = n + k + 1
    if np > N:
        g += N - n
        break
    g = nxt + gcd(np, nxt)
    n = np
print(g)