Detailed mathematical approach

Problem Summary

The sequence is defined by

$g(4)=13,\qquad g(n)=g(n-1)+\gcd(n,g(n-1)) \quad (n \ge 5).$

We need the value of \(g(10^{15})\). A direct simulation is impossible at that scale, so the solution looks for a rigid pattern inside the recurrence and then jumps over long linear stretches.

Mathematical Approach

Step 1: Find the first structural index

The first few values are easy to compute directly:

$g(5)=14,\quad g(6)=16,\quad g(7)=17,\quad g(8)=18,\quad g(9)=27.$

At \(n=9\) we obtain

$g(9)=27=3 \cdot 9.$

This suggests studying indices \(a\) for which

$g(a)=3a.$

Once the sequence reaches such an index, the later behavior becomes highly constrained.

Step 2: Show that the sequence is linear until the next jump

Assume \(g(a)=3a\). If the next increments are all \(1\), then for any \(t \ge 1\) before the next jump,

$g(a+t-1)=3a+(t-1).$

The increment at \(n=a+t\) is therefore

$\gcd(a+t,g(a+t-1))=\gcd(a+t,3a+t-1).$

Subtracting the first argument from the second gives

$\gcd(a+t,3a+t-1)=\gcd(a+t,2a-1).$

That is the key simplification: after reaching \(g(a)=3a\), the future increments depend only on when \(a+t\) first shares a nontrivial divisor with the fixed odd number \(2a-1\).

Step 3: Use the smallest prime factor of \(2a-1\)

Let \(p\) be the smallest prime factor of \(2a-1\). Since \(p \mid (2a-1)\), we have

$2a \equiv 1 \pmod{p}.$

Because \(p\) is odd, \(2\) is invertible modulo \(p\), so

$a \equiv 2^{-1} \pmod{p},\qquad -a \equiv \frac{p-1}{2} \pmod{p}.$

Hence the smallest positive \(t\) such that \(p \mid (a+t)\) is

$t_0=\frac{p-1}{2}.$

No smaller \(t\) can produce a nontrivial gcd. Indeed, if some \(q\) divides both \(a+t\) and \(2a-1\), then \(q\) has a prime divisor that also divides \(2a-1\). For every prime divisor \(q\) of \(2a-1\), the first positive solution of \(q \mid (a+t)\) is \((q-1)/2\), and this is at least \((p-1)/2\) because \(p\) is the smallest such prime.

Therefore \(\gcd(a+t,2a-1)=1\) for every \(1 \le t \lt t_0\), and the first non-unit increment happens exactly at \(t=t_0\).

Step 4: Prove that the same structure returns

Set \(a' = a+t_0\). Then \(p\) divides both \(a'\) and \(2a-1\), so the gcd at this step is at least \(p\). On the other hand, if

$d=\gcd(a',2a-1),$

then \(d\) also divides

$2a'-(2a-1)=2(a+t_0)-(2a-1)=p.$

So \(d=p\). The jump at \(a'\) is exactly \(p=2t_0+1\).

Before that jump, the sequence has only increased by ones, so

$g(a'-1)=3a+(t_0-1).$

After adding the jump,

$g(a')=3a+(t_0-1)+p=3a+3t_0=3(a+t_0)=3a'.$

Thus the same structural relation appears again. The next such index is

$a'=a+\frac{p-1}{2},$

where \(p\) is the smallest prime factor of \(2a-1\).

Step 5: Closed form inside one segment

If a target \(N\) lies strictly before the next structural index, then all remaining increments are \(1\). Starting from \(g(a)=3a\), we get

$g(N)=3a+(N-a)=N+2a.$

If the next structural index is exactly \(N\), then the previous step gives \(g(N)=3N\). This completely determines the recurrence once one structural index is known.

Worked Example

The first structural index is \(a=9\). Then

$2a-1=17,$

so the smallest prime factor is \(17\), and the next structural index is

$9+\frac{17-1}{2}=17.$

Therefore the sequence is linear on the interval \(10 \le n \le 16\):

$g(n)=n+18.$

At \(n=17\) the jump is \(17\), so \(g(17)=51=3 \cdot 17\). Repeating the rule from \(a=17\), we have \(2a-1=33\) and the smallest prime factor is \(3\), so the next structural index is \(18\). This matches the direct values \(g(18)=54\), \(g(20)=60\), and \(g(21)=63\).

How the Code Works

The C++, Python, and Java implementations handle the short initial range directly, because the jump pattern starts only after the first structural index at \(9\). For larger inputs they keep the current index \(a\) satisfying \(g(a)=3a\), factor \(2a-1\) just far enough to obtain its smallest prime factor, and compute the next index \(a+(p-1)/2\). If that next index is already beyond the target, the answer is returned from the linear formula \(g(N)=N+2a\). Otherwise the process repeats from the new structural index. The implementations are therefore not guessing; they are a direct translation of the proof above.

Complexity Analysis

A naive solution performs one gcd evaluation for every integer from \(5\) up to \(N\), which is infeasible for \(N=10^{15}\). The jump method visits only the structural indices generated by the recurrence. In these implementations, each jump finds the smallest prime factor of \(2a-1\) by trial division using the standard \(2,3,6k \pm 1\) pattern. If the visited structural indices are \(a_0,a_1,\dots,a_m\), the total work is the sum of those factor-search costs, while the memory usage stays \(O(1)\). For the actual target, the number of jumps is tiny compared with \(10^{15}\), which is why the computation is fast in practice.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=443
2. Greatest common divisor: Wikipedia — Greatest common divisor
3. Modular arithmetic: Wikipedia — Modular arithmetic
4. Integer factorization: Wikipedia — Integer factorization