Problem 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 | … |
| g(n) | 13 | 14 | 16 | 17 | 18 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 51 | 54 | 55 | 60 | … |
You are given that g(1 000) = 2524 and g(1 000 000) = 2624152.
Find g(1015).
最大公约数序列
序列g(n)按如下方式定义：
g(4) = 13，
g(n) = g(n-1) + gcd(n, g(n-1))，若n > 4。
序列最初始的一些项是：
| n | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | … |
| g(n) | 13 | 14 | 16 | 17 | 18 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 51 | 54 | 55 | 60 | … |
已知g(1 000) = 2524以及g(1 000 000) = 2624152。
求g(1015)。