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.
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.
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\).
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\).
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\).
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.
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\).
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.
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.
Die Folge ist definiert durch
$$g(4)=13,\qquad g(n)=g(n-1)+\gcd(n,g(n-1)) \quad (n \ge 5).$$
Gesucht ist \(g(10^{15})\). Eine schrittweise Simulation ist dafür unmöglich, daher nutzt die Lösung eine starre Struktur der Rekursion und springt über lange lineare Abschnitte.
Die ersten Werte lassen sich direkt berechnen:
$$g(5)=14,\quad g(6)=16,\quad g(7)=17,\quad g(8)=18,\quad g(9)=27.$$
Bei \(n=9\) gilt also
$$g(9)=27=3 \cdot 9.$$
Damit lohnt es sich, Indizes \(a\) zu betrachten, für die
$$g(a)=3a$$
gilt. Sobald die Folge einen solchen Index erreicht, wird das spätere Verhalten stark eingeschränkt.
Angenommen, \(g(a)=3a\). Wenn die nächsten Zuwächse alle gleich \(1\) sind, dann gilt für jedes \(t \ge 1\) vor dem nächsten Sprung
$$g(a+t-1)=3a+(t-1).$$
Der nächste Zuwachs bei \(n=a+t\) ist dann
$$\gcd(a+t,g(a+t-1))=\gcd(a+t,3a+t-1).$$
Durch Subtraktion des ersten Arguments vom zweiten erhält man
$$\gcd(a+t,3a+t-1)=\gcd(a+t,2a-1).$$
Das ist die entscheidende Vereinfachung: Nach einem Index mit \(g(a)=3a\) hängt jeder spätere Zuwachs nur noch davon ab, wann \(a+t\) erstmals einen nichttrivialen Teiler mit der festen ungeraden Zahl \(2a-1\) teilt.
Sei \(p\) der kleinste Primteiler von \(2a-1\). Aus \(p \mid (2a-1)\) folgt
$$2a \equiv 1 \pmod{p}.$$
Da \(p\) ungerade ist, besitzt \(2\) ein Inverses modulo \(p\). Also gilt
$$a \equiv 2^{-1} \pmod{p},\qquad -a \equiv \frac{p-1}{2} \pmod{p}.$$
Damit ist das kleinste positive \(t\) mit \(p \mid (a+t)\)
$$t_0=\frac{p-1}{2}.$$
Kein kleineres \(t\) kann bereits einen nichttrivialen ggT erzeugen. Teilt nämlich eine Zahl \(q\) sowohl \(a+t\) als auch \(2a-1\), so besitzt \(q\) einen Primteiler, der ebenfalls \(2a-1\) teilt. Für jeden Primteiler \(q\) von \(2a-1\) ist die erste positive Lösung von \(q \mid (a+t)\) gleich \((q-1)/2\), und dieser Wert ist wegen der Minimalität von \(p\) mindestens \((p-1)/2\).
Also gilt \(\gcd(a+t,2a-1)=1\) für alle \(1 \le t \lt t_0\), und der erste nichttriviale Zuwachs tritt genau bei \(t=t_0\) auf.
Setze \(a' = a+t_0\). Dann teilt \(p\) sowohl \(a'\) als auch \(2a-1\), also ist der ggT an dieser Stelle mindestens \(p\). Andererseits sei
$$d=\gcd(a',2a-1).$$
Dann teilt \(d\) auch
$$2a'-(2a-1)=2(a+t_0)-(2a-1)=p.$$
Folglich ist \(d=p\). Der Sprung an der Stelle \(a'\) ist also genau \(p=2t_0+1\).
Vor diesem Sprung ist die Folge nur durch Einsen gewachsen, daher
$$g(a'-1)=3a+(t_0-1).$$
Nach dem Sprung ergibt sich
$$g(a')=3a+(t_0-1)+p=3a+3t_0=3(a+t_0)=3a'.$$
Damit taucht dieselbe Struktur erneut auf. Der nächste Strukturindex ist also
$$a'=a+\frac{p-1}{2},$$
wobei \(p\) der kleinste Primteiler von \(2a-1\) ist.
Liegt das Ziel \(N\) strikt vor dem nächsten Strukturindex, dann sind alle verbleibenden Zuwächse gleich \(1\). Ausgehend von \(g(a)=3a\) erhält man
$$g(N)=3a+(N-a)=N+2a.$$
Falls der nächste Strukturindex genau \(N\) ist, folgt aus dem vorigen Schritt \(g(N)=3N\). Damit ist die Rekursion vollständig bestimmt, sobald ein Strukturindex bekannt ist.
Der erste Strukturindex ist \(a=9\). Dann gilt
$$2a-1=17,$$
also ist der kleinste Primteiler \(17\), und der nächste Strukturindex liegt bei
$$9+\frac{17-1}{2}=17.$$
Die Folge ist deshalb auf dem Intervall \(10 \le n \le 16\) linear:
$$g(n)=n+18.$$
Bei \(n=17\) beträgt der Sprung \(17\), also \(g(17)=51=3 \cdot 17\). Wendet man die Regel erneut auf \(a=17\) an, so ist \(2a-1=33\) und der kleinste Primteiler gleich \(3\), also ist der nächste Strukturindex \(18\). Das passt zu den direkten Werten \(g(18)=54\), \(g(20)=60\) und \(g(21)=63\).
Die Implementierungen in C++, Python und Java behandeln zunächst den kurzen Anfangsbereich direkt, denn das Sprungmuster beginnt erst nach dem ersten Strukturindex bei \(9\). Für größere Eingaben halten sie einen aktuellen Index \(a\) mit \(g(a)=3a\), bestimmen den kleinsten Primteiler von \(2a-1\) und berechnen daraus den nächsten Index \(a+(p-1)/2\). Liegt dieser bereits hinter dem Ziel, so wird die Antwort sofort mit der linearen Formel \(g(N)=N+2a\) zurückgegeben. Andernfalls wird der Vorgang vom neuen Strukturindex aus wiederholt. Der Programmablauf ist also eine direkte Umsetzung des Beweises.
Eine naive Lösung würde für jedes \(n\) von \(5\) bis \(N\) einen ggT berechnen und ist daher für \(N=10^{15}\) unbrauchbar. Die Sprungmethode besucht nur die Strukturindizes, die von der Rekursion erzeugt werden. In diesen Implementierungen wird pro Sprung der kleinste Primteiler von \(2a-1\) per Probedivision im Muster \(2,3,6k \pm 1\) gesucht. Sind die besuchten Strukturindizes \(a_0,a_1,\dots,a_m\), dann ist der Gesamtaufwand die Summe dieser Faktorisierungskosten; der Speicherbedarf bleibt \(O(1)\). Für das eigentliche Ziel ist die Zahl der Sprünge winzig im Vergleich zu \(10^{15}\), weshalb die Berechnung praktisch sehr schnell ist.
Dizi şu şekilde tanımlanır:
$$g(4)=13,\qquad g(n)=g(n-1)+\gcd(n,g(n-1)) \quad (n \ge 5).$$
Aranan değer \(g(10^{15})\)'tir. Bu büyüklükte doğrudan adım adım ilerlemek imkansız olduğu için çözüm, bağıntının içinde tekrar eden katı bir yapıyı bulup uzun doğrusal parçaları tek sıçramada geçer.
İlk terimler doğrudan hesaplanabilir:
$$g(5)=14,\quad g(6)=16,\quad g(7)=17,\quad g(8)=18,\quad g(9)=27.$$
Böylece \(n=9\) için
$$g(9)=27=3 \cdot 9$$
elde edilir. Bu nedenle
$$g(a)=3a$$
koşulunu sağlayan indeksleri incelemek doğal hale gelir. Dizi böyle bir indekse ulaştığında sonraki davranış ciddi biçimde kısıtlanır.
\(g(a)=3a\) olduğunu varsayalım. Eğer bir süre boyunca gelen artışların hepsi \(1\) ise, sonraki sıçramadan önce her \(t \ge 1\) için
$$g(a+t-1)=3a+(t-1)$$
olur. O halde \(n=a+t\) adımındaki artış
$$\gcd(a+t,g(a+t-1))=\gcd(a+t,3a+t-1)$$
şeklindedir. İkinci argümandan birincisini çıkarırsak
$$\gcd(a+t,3a+t-1)=\gcd(a+t,2a-1)$$
elde edilir. Ana sadeleşme budur: \(g(a)=3a\) noktasından sonra bütün gelecek artışlar, \(a+t\) ile sabit tek sayı \(2a-1\)'in ne zaman ortak bir bölen paylaşacağına bağlıdır.
\(2a-1\)'in en küçük asal çarpanı \(p\) olsun. \(p \mid (2a-1)\) olduğundan
$$2a \equiv 1 \pmod{p}$$
yazılır. \(p\) tek asal olduğundan \(2\)'nin mod \(p\) altında tersi vardır; dolayısıyla
$$a \equiv 2^{-1} \pmod{p},\qquad -a \equiv \frac{p-1}{2} \pmod{p}.$$
Buna göre \(p \mid (a+t)\) olacak en küçük pozitif \(t\)
$$t_0=\frac{p-1}{2}$$
olur. Bundan daha küçük bir \(t\), önemsiz olmayan bir EBOB veremez. Gerçekten de bir \(q\) hem \(a+t\)'yi hem de \(2a-1\)'i bölüyorsa, \(q\)'nun asal bölenlerinden biri de \(2a-1\)'i böler. \(2a-1\)'in her asal böleni için \(q \mid (a+t)\) denkleminin ilk pozitif çözümü \((q-1)/2\)'dir ve \(p\) en küçük asal olduğundan bu değer en az \((p-1)/2\) olur.
Demek ki \(1 \le t \lt t_0\) için \(\gcd(a+t,2a-1)=1\) ve ilk gerçek sıçrama tam olarak \(t=t_0\) anında gerçekleşir.
\(a' = a+t_0\) olsun. Bu durumda \(p\), hem \(a'\) hem de \(2a-1\) sayısını böler; dolayısıyla bu adımdaki EBOB en az \(p\)'dir. Öte yandan
$$d=\gcd(a',2a-1)$$
dersek, \(d\) aynı zamanda
$$2a'-(2a-1)=2(a+t_0)-(2a-1)=p$$
sayısını da böler. O halde \(d=p\). Yani \(a'\) noktasındaki artış tam olarak \(p=2t_0+1\)'dir.
Bu sıçramadan önce dizi yalnızca birer birer artmıştır; bu yüzden
$$g(a'-1)=3a+(t_0-1).$$
Sıçrama eklendiğinde
$$g(a')=3a+(t_0-1)+p=3a+3t_0=3(a+t_0)=3a'$$
elde edilir. Böylece aynı yapı yeniden oluşur. Sonraki yapı indeksi
$$a'=a+\frac{p-1}{2}$$
olur; burada \(p\), \(2a-1\)'in en küçük asal çarpanıdır.
Hedef \(N\), bir sonraki yapı indeksinden küçükse, kalan bütün artışlar \(1\)'dir. \(g(a)=3a\)'dan başlayarak
$$g(N)=3a+(N-a)=N+2a$$
sonucu çıkar. Eğer bir sonraki yapı indeksi tam olarak \(N\) ise, önceki adımdan \(g(N)=3N\) gelir. Böylece bir yapı indeksi bilindiğinde bağıntı tamamen çözülmüş olur.
İlk yapı indeksi \(a=9\)'dur. Bu durumda
$$2a-1=17$$
olur; en küçük asal çarpan da \(17\)'dir. O halde sonraki yapı indeksi
$$9+\frac{17-1}{2}=17$$
olarak bulunur. Bu nedenle dizi \(10 \le n \le 16\) aralığında doğrusaldır:
$$g(n)=n+18.$$
\(n=17\) için sıçrama büyüklüğü \(17\) olur ve \(g(17)=51=3 \cdot 17\) elde edilir. Kuralı \(a=17\) için tekrar uygularsak \(2a-1=33\) ve en küçük asal çarpan \(3\) çıkar; dolayısıyla sonraki yapı indeksi \(18\)'dir. Bu da doğrudan hesaplanan \(g(18)=54\), \(g(20)=60\) ve \(g(21)=63\) değerleriyle uyuşur.
C++, Python ve Java implementasyonları önce kısa başlangıç aralığını doğrudan hesaplar; çünkü sıçrama düzeni ancak \(9\)'daki ilk yapı indeksinden sonra başlar. Daha büyük girdilerde, \(g(a)=3a\) koşulunu sağlayan güncel \(a\) tutulur, \(2a-1\) sayısı yalnızca en küçük asal çarpanı bulunacak kadar ayrıştırılır ve bundan sonraki indeks \(a+(p-1)/2\) olarak hesaplanır. Eğer bu yeni indeks hedefin ötesindeyse cevap doğrudan \(g(N)=N+2a\) formülüyle verilir. Değilse süreç yeni yapı indeksinden itibaren tekrarlanır. Yani kod, yukarıdaki ispatın birebir çevrilmiş halidir.
Naif yaklaşım, \(5\)'ten \(N\)'ye kadar her sayı için bir EBOB hesabı yapar; \(N=10^{15}\) için bu olanaksızdır. Sıçrama yöntemi ise sadece bağıntının ürettiği yapı indekslerini ziyaret eder. Bu implementasyonlarda her sıçramada \(2a-1\)'in en küçük asal çarpanı, standart \(2,3,6k \pm 1\) deneme bölmesi ile bulunur. Ziyaret edilen yapı indeksleri \(a_0,a_1,\dots,a_m\) ise toplam iş yükü bu çarpan aramalarının toplamıdır; bellek kullanımı ise \(O(1)\) kalır. Gerçek hedef için sıçrama sayısı \(10^{15}\) ile kıyaslanamayacak kadar küçüktür, bu yüzden yöntem pratikte çok hızlıdır.
La sucesión está definida por
$$g(4)=13,\qquad g(n)=g(n-1)+\gcd(n,g(n-1)) \quad (n \ge 5).$$
Debemos calcular \(g(10^{15})\). Una simulación término a término es inviable, así que la solución detecta una estructura rígida dentro de la recurrencia y salta sobre tramos lineales muy largos.
Los primeros valores se obtienen sin dificultad:
$$g(5)=14,\quad g(6)=16,\quad g(7)=17,\quad g(8)=18,\quad g(9)=27.$$
En \(n=9\) aparece
$$g(9)=27=3 \cdot 9.$$
Por eso conviene estudiar los índices \(a\) que satisfacen
$$g(a)=3a.$$
Una vez que la sucesión alcanza uno de esos índices, el comportamiento posterior queda muy restringido.
Supongamos que \(g(a)=3a\). Si los incrementos siguientes son todos iguales a \(1\), entonces para cualquier \(t \ge 1\) antes del próximo salto se tiene
$$g(a+t-1)=3a+(t-1).$$
El incremento en \(n=a+t\) vale
$$\gcd(a+t,g(a+t-1))=\gcd(a+t,3a+t-1).$$
Restando el primer argumento del segundo obtenemos
$$\gcd(a+t,3a+t-1)=\gcd(a+t,2a-1).$$
Esa es la simplificación central: después de llegar a \(g(a)=3a\), todos los incrementos futuros dependen solamente de cuándo \(a+t\) comparte por primera vez un divisor no trivial con el número impar fijo \(2a-1\).
Sea \(p\) el menor factor primo de \(2a-1\). Como \(p \mid (2a-1)\), se cumple
$$2a \equiv 1 \pmod{p}.$$
Dado que \(p\) es impar, \(2\) es invertible módulo \(p\), y por tanto
$$a \equiv 2^{-1} \pmod{p},\qquad -a \equiv \frac{p-1}{2} \pmod{p}.$$
Así, el menor \(t\) positivo para el cual \(p \mid (a+t)\) es
$$t_0=\frac{p-1}{2}.$$
Ningún \(t\) menor puede producir un máximo común divisor no trivial. En efecto, si un número \(q\) divide a la vez \(a+t\) y \(2a-1\), entonces algún factor primo de \(q\) también divide a \(2a-1\). Para cada primo \(q\) que divide a \(2a-1\), la primera solución positiva de \(q \mid (a+t)\) es \((q-1)/2\), y ese valor es al menos \((p-1)/2\) porque \(p\) es el menor de esos primos.
Por lo tanto, \(\gcd(a+t,2a-1)=1\) para todo \(1 \le t \lt t_0\), y el primer incremento distinto de \(1\) ocurre exactamente cuando \(t=t_0\).
Definamos \(a' = a+t_0\). Entonces \(p\) divide tanto a \(a'\) como a \(2a-1\), de modo que el gcd en ese paso es al menos \(p\). Por otra parte, si
$$d=\gcd(a',2a-1),$$
entonces \(d\) también divide
$$2a'-(2a-1)=2(a+t_0)-(2a-1)=p.$$
Luego \(d=p\). El salto en \(a'\) es exactamente \(p=2t_0+1\).
Antes de ese salto, la sucesión solo ha aumentado de uno en uno, así que
$$g(a'-1)=3a+(t_0-1).$$
Al sumar el salto se obtiene
$$g(a')=3a+(t_0-1)+p=3a+3t_0=3(a+t_0)=3a'.$$
La misma estructura vuelve a aparecer. El siguiente índice estructural es entonces
$$a'=a+\frac{p-1}{2},$$
donde \(p\) es el menor factor primo de \(2a-1\).
Si el objetivo \(N\) cae estrictamente antes del siguiente índice estructural, todos los incrementos restantes son \(1\). Partiendo de \(g(a)=3a\), se obtiene
$$g(N)=3a+(N-a)=N+2a.$$
Si el siguiente índice estructural coincide exactamente con \(N\), entonces el paso anterior da \(g(N)=3N\). Con eso la recurrencia queda completamente determinada una vez conocido un índice estructural.
El primer índice estructural es \(a=9\). Entonces
$$2a-1=17,$$
de modo que el menor factor primo es \(17\), y el siguiente índice estructural es
$$9+\frac{17-1}{2}=17.$$
Por consiguiente, la sucesión es lineal en el intervalo \(10 \le n \le 16\):
$$g(n)=n+18.$$
En \(n=17\) el salto vale \(17\), así que \(g(17)=51=3 \cdot 17\). Si repetimos la regla desde \(a=17\), ahora \(2a-1=33\) y el menor factor primo es \(3\), por lo que el siguiente índice estructural es \(18\). Esto coincide con los valores directos \(g(18)=54\), \(g(20)=60\) y \(g(21)=63\).
Las implementaciones en C++, Python y Java evalúan primero el pequeño tramo inicial de forma directa, porque el patrón de saltos solo aparece después del primer índice estructural en \(9\). Para entradas mayores mantienen un índice actual \(a\) que cumple \(g(a)=3a\), factorizan \(2a-1\) solo hasta obtener su menor factor primo y calculan el siguiente índice \(a+(p-1)/2\). Si ese índice ya queda por encima del objetivo, la respuesta sale inmediatamente de la fórmula lineal \(g(N)=N+2a\). En caso contrario, el proceso se repite desde el nuevo índice estructural. La implementación no introduce heurísticas: traduce exactamente la demostración anterior.
Una simulación ingenua realiza una evaluación de gcd para cada entero entre \(5\) y \(N\), lo cual es imposible para \(N=10^{15}\). El método con saltos visita solo los índices estructurales generados por la recurrencia. En estas implementaciones, cada salto encuentra el menor factor primo de \(2a-1\) mediante división de prueba con el patrón estándar \(2,3,6k \pm 1\). Si los índices visitados son \(a_0,a_1,\dots,a_m\), el trabajo total es la suma de esos costes de factorización, mientras que la memoria permanece en \(O(1)\). Para el valor real del problema, el número de saltos es minúsculo comparado con \(10^{15}\), y por eso el cálculo resulta rápido en la práctica.
数列定义为
$$g(4)=13,\qquad g(n)=g(n-1)+\gcd(n,g(n-1)) \quad (n \ge 5).$$
目标是求 \(g(10^{15})\)。如果逐项递推，规模完全不可接受，因此真正的关键是找出递推中的固定结构，然后跨越很长的线性区间。
前几项可以直接算出：
$$g(5)=14,\quad g(6)=16,\quad g(7)=17,\quad g(8)=18,\quad g(9)=27.$$
于是当 \(n=9\) 时有
$$g(9)=27=3 \cdot 9.$$
因此应当重点研究满足
$$g(a)=3a$$
的下标 \(a\)。一旦序列到达这样的下标，后面的行为就会变得非常规则。
设 \(g(a)=3a\)。如果接下来若干步的增量都等于 \(1\)，那么在下一次跳跃之前，对任意 \(t \ge 1\) 都有
$$g(a+t-1)=3a+(t-1).$$
于是当 \(n=a+t\) 时，增量为
$$\gcd(a+t,g(a+t-1))=\gcd(a+t,3a+t-1).$$
把第二个参数减去第一个参数，可得
$$\gcd(a+t,3a+t-1)=\gcd(a+t,2a-1).$$
这一步是整个解法的核心。只要达到 \(g(a)=3a\)，之后的增量就只取决于 \(a+t\) 何时第一次与固定奇数 \(2a-1\) 具有非平凡公因子。
设 \(p\) 为 \(2a-1\) 的最小质因子。因为 \(p \mid (2a-1)\)，所以
$$2a \equiv 1 \pmod{p}.$$
\(p\) 是奇素数，因此 \(2\) 在模 \(p\) 意义下可逆，于是
$$a \equiv 2^{-1} \pmod{p},\qquad -a \equiv \frac{p-1}{2} \pmod{p}.$$
所以满足 \(p \mid (a+t)\) 的最小正整数 \(t\) 为
$$t_0=\frac{p-1}{2}.$$
更小的 \(t\) 不可能产生非平凡 gcd。原因是，如果某个 \(q\) 同时整除 \(a+t\) 和 \(2a-1\)，那么 \(q\) 的某个质因子也整除 \(2a-1\)。对 \(2a-1\) 的任意质因子 \(q\) 来说，使 \(q \mid (a+t)\) 成立的最小正解都是 \((q-1)/2\)，而由于 \(p\) 是最小质因子，这个值一定不小于 \((p-1)/2\)。
因此，对所有 \(1 \le t \lt t_0\)，都有 \(\gcd(a+t,2a-1)=1\)，第一次真正的跳跃恰好发生在 \(t=t_0\)。
令 \(a' = a+t_0\)。此时 \(p\) 同时整除 \(a'\) 和 \(2a-1\)，因此这一步的 gcd 至少为 \(p\)。另一方面，若记
$$d=\gcd(a',2a-1),$$
则 \(d\) 还整除
$$2a'-(2a-1)=2(a+t_0)-(2a-1)=p.$$
所以只能有 \(d=p\)。也就是说，在 \(a'\) 处的跳跃大小恰好是 \(p=2t_0+1\)。
在此之前，序列每一步只增加 \(1\)，因此
$$g(a'-1)=3a+(t_0-1).$$
把跳跃加上去之后得到
$$g(a')=3a+(t_0-1)+p=3a+3t_0=3(a+t_0)=3a'.$$
于是同样的结构重新出现。下一个这样的下标就是
$$a'=a+\frac{p-1}{2},$$
其中 \(p\) 是 \(2a-1\) 的最小质因子。
如果目标 \(N\) 严格落在下一个结构性下标之前，那么剩余的增量全部都是 \(1\)。从 \(g(a)=3a\) 出发，立即得到
$$g(N)=3a+(N-a)=N+2a.$$
如果下一个结构性下标恰好等于 \(N\)，那么由上一节可知 \(g(N)=3N\)。因此，只要知道一个结构性下标，整个递推过程就完全确定了。
第一个结构性下标是 \(a=9\)。此时
$$2a-1=17,$$
所以最小质因子就是 \(17\)，下一个结构性下标为
$$9+\frac{17-1}{2}=17.$$
因此在区间 \(10 \le n \le 16\) 上，数列是线性的：
$$g(n)=n+18.$$
到 \(n=17\) 时，跳跃大小为 \(17\)，于是 \(g(17)=51=3 \cdot 17\)。再从 \(a=17\) 重复这一规则，此时 \(2a-1=33\)，最小质因子是 \(3\)，所以下一个结构性下标是 \(18\)。这与直接计算得到的 \(g(18)=54\)、\(g(20)=60\)、\(g(21)=63\) 完全一致。
C++、Python 和 Java 实现都会先直接处理前面很短的一段，因为跳跃结构要到第一个结构性下标 \(9\) 之后才出现。对于更大的输入，实现维护当前满足 \(g(a)=3a\) 的下标 \(a\)，只把 \(2a-1\) 分解到足以得到最小质因子的程度，然后据此算出下一个下标 \(a+(p-1)/2\)。如果这个下一个下标已经超过目标，那么答案就直接由线性公式 \(g(N)=N+2a\) 给出；否则就从新的结构性下标继续迭代。因此，实现并不是经验性跳跃，而是对上面证明的直接翻译。
朴素方法需要从 \(5\) 到 \(N\) 对每个整数都计算一次 gcd，对 \(N=10^{15}\) 来说完全不可行。跳跃方法只访问递推真正产生的那些结构性下标。在这些实现中，每一步都用标准的 \(2,3,6k \pm 1\) 试除模式求出 \(2a-1\) 的最小质因子。若访问到的下标为 \(a_0,a_1,\dots,a_m\)，总工作量就是这些分解成本之和，而额外空间始终是 \(O(1)\)。对于题目的实际目标，跳跃次数与 \(10^{15}\) 相比极其微小，因此运行非常快。
Последовательность задается формулами
$$g(4)=13,\qquad g(n)=g(n-1)+\gcd(n,g(n-1)) \quad (n \ge 5).$$
Нужно вычислить \(g(10^{15})\). Пошаговая симуляция на таком диапазоне невозможна, поэтому решение ищет жесткую структуру внутри рекурсии и перескакивает через длинные линейные участки.
Первые значения легко посчитать напрямую:
$$g(5)=14,\quad g(6)=16,\quad g(7)=17,\quad g(8)=18,\quad g(9)=27.$$
При \(n=9\) получаем
$$g(9)=27=3 \cdot 9.$$
Поэтому естественно изучать индексы \(a\), для которых
$$g(a)=3a.$$
Как только последовательность попадает в такую точку, дальнейшее поведение оказывается почти полностью определенным.
Предположим, что \(g(a)=3a\). Если следующие приращения равны \(1\), то до ближайшего скачка для любого \(t \ge 1\) имеем
$$g(a+t-1)=3a+(t-1).$$
Тогда приращение в точке \(n=a+t\) равно
$$\gcd(a+t,g(a+t-1))=\gcd(a+t,3a+t-1).$$
Вычитая первый аргумент из второго, получаем
$$\gcd(a+t,3a+t-1)=\gcd(a+t,2a-1).$$
Это главный переход: после индекса с условием \(g(a)=3a\) будущие приращения зависят только от того, когда число \(a+t\) впервые получит нетривиальный общий делитель с фиксированным нечетным числом \(2a-1\).
Пусть \(p\) — наименьший простой делитель числа \(2a-1\). Тогда
$$2a \equiv 1 \pmod{p}.$$
Так как \(p\) нечетное простое, число \(2\) обратимо по модулю \(p\), следовательно
$$a \equiv 2^{-1} \pmod{p},\qquad -a \equiv \frac{p-1}{2} \pmod{p}.$$
Значит, минимальное положительное \(t\), для которого \(p \mid (a+t)\), равно
$$t_0=\frac{p-1}{2}.$$
Никакое меньшее \(t\) не может дать нетривиальный gcd. Действительно, если число \(q\) делит и \(a+t\), и \(2a-1\), то некоторый простой делитель числа \(q\) также делит \(2a-1\). Для любого простого делителя \(q\) числа \(2a-1\) первое положительное решение сравнения \(q \mid (a+t)\) равно \((q-1)/2\), а это значение не меньше \((p-1)/2\), поскольку \(p\) минимален.
Следовательно, для всех \(1 \le t \lt t_0\) выполняется \(\gcd(a+t,2a-1)=1\), и первый нетривиальный шаг происходит ровно при \(t=t_0\).
Положим \(a' = a+t_0\). Тогда \(p\) делит и \(a'\), и \(2a-1\), так что gcd в этой точке не меньше \(p\). С другой стороны, если
$$d=\gcd(a',2a-1),$$
то \(d\) делит также число
$$2a'-(2a-1)=2(a+t_0)-(2a-1)=p.$$
Поэтому \(d=p\). Значит, скачок в точке \(a'\) имеет величину ровно \(p=2t_0+1\).
До этого скачка последовательность росла только на единицу, поэтому
$$g(a'-1)=3a+(t_0-1).$$
После добавления скачка получаем
$$g(a')=3a+(t_0-1)+p=3a+3t_0=3(a+t_0)=3a'.$$
Тем самым та же структурная связь возникает снова. Следующий структурный индекс равен
$$a'=a+\frac{p-1}{2},$$
где \(p\) — наименьший простой делитель числа \(2a-1\).
Если целевой индекс \(N\) лежит строго до следующего структурного индекса, то все оставшиеся приращения равны \(1\). Начиная с \(g(a)=3a\), получаем
$$g(N)=3a+(N-a)=N+2a.$$
Если следующий структурный индекс совпадает с \(N\), то из предыдущего шага следует \(g(N)=3N\). Значит, как только найден один структурный индекс, рекурсия полностью контролируется.
Первый структурный индекс — \(a=9\). Тогда
$$2a-1=17,$$
и наименьший простой делитель равен \(17\). Следовательно, следующий структурный индекс равен
$$9+\frac{17-1}{2}=17.$$
Поэтому на интервале \(10 \le n \le 16\) последовательность линейна:
$$g(n)=n+18.$$
При \(n=17\) скачок равен \(17\), так что \(g(17)=51=3 \cdot 17\). Если повторить правило из точки \(a=17\), то теперь \(2a-1=33\), а наименьший простой делитель равен \(3\), значит следующий структурный индекс — \(18\). Это совпадает с прямыми значениями \(g(18)=54\), \(g(20)=60\) и \(g(21)=63\).
Реализации на C++, Python и Java сначала напрямую обрабатывают короткий начальный участок, потому что схема со скачками появляется только после первого структурного индекса \(9\). Для больших входных данных они поддерживают текущий индекс \(a\), удовлетворяющий условию \(g(a)=3a\), раскладывают число \(2a-1\) лишь настолько, чтобы найти его наименьший простой делитель, и вычисляют следующий индекс \(a+(p-1)/2\). Если этот индекс уже больше цели, ответ сразу получается из линейной формулы \(g(N)=N+2a\). Иначе процесс повторяется из нового структурного индекса. То есть реализация буквально повторяет доказанную выше математику.
Наивный алгоритм выполнял бы вычисление gcd для каждого целого числа от \(5\) до \(N\), что невозможно при \(N=10^{15}\). Метод скачков посещает только структурные индексы, действительно возникающие в рекурсии. В этих реализациях на каждом шаге наименьший простой делитель числа \(2a-1\) ищется пробным делением по стандартной схеме \(2,3,6k \pm 1\). Если посещенные индексы равны \(a_0,a_1,\dots,a_m\), то суммарная работа равна сумме стоимостей этих факторизаций, а память остается \(O(1)\). Для реального целевого значения число скачков ничтожно мало по сравнению с \(10^{15}\), поэтому метод работает быстро.
المتتالية معرفة بالعلاقة
$$g(4)=13,\qquad g(n)=g(n-1)+\gcd(n,g(n-1)) \quad (n \ge 5).$$
المطلوب هو حساب \(g(10^{15})\). المحاكاة المباشرة حدًا بعد حد غير ممكنة بهذا الحجم، لذلك تعتمد الفكرة على استخراج بنية ثابتة داخل العلاقة ثم القفز فوق مقاطع خطية طويلة.
يمكن حساب القيم الأولى مباشرة:
$$g(5)=14,\quad g(6)=16,\quad g(7)=17,\quad g(8)=18,\quad g(9)=27.$$
وعند \(n=9\) نحصل على
$$g(9)=27=3 \cdot 9.$$
لذلك يصبح من الطبيعي دراسة المؤشرات \(a\) التي تحقق
$$g(a)=3a.$$
بمجرد أن تصل المتتالية إلى مثل هذا الموضع، يصبح السلوك اللاحق مقيدًا بشدة.
افترض أن \(g(a)=3a\). إذا كانت الزيادات التالية كلها تساوي \(1\)، فعند أي \(t \ge 1\) قبل القفزة التالية يكون
$$g(a+t-1)=3a+(t-1).$$
وعندئذ تكون الزيادة عند \(n=a+t\) هي
$$\gcd(a+t,g(a+t-1))=\gcd(a+t,3a+t-1).$$
وبطرح الوسيط الأول من الثاني نحصل على
$$\gcd(a+t,3a+t-1)=\gcd(a+t,2a-1).$$
وهذه هي الخطوة الحاسمة: بعد الوصول إلى موضع يحقق \(g(a)=3a\)، تصبح كل الزيادات اللاحقة مرتبطة فقط باللحظة التي يشارك فيها \(a+t\) قاسمًا غير بديهي مع العدد الفردي الثابت \(2a-1\).
ليكن \(p\) أصغر عامل أولي للعدد \(2a-1\). بما أن \(p \mid (2a-1)\)، فإن
$$2a \equiv 1 \pmod{p}.$$
ولأن \(p\) عدد أولي فردي، فإن \(2\) قابل للعكس بترديد \(p\)، وبالتالي
$$a \equiv 2^{-1} \pmod{p},\qquad -a \equiv \frac{p-1}{2} \pmod{p}.$$
إذن أصغر \(t\) موجب يحقق \(p \mid (a+t)\) هو
$$t_0=\frac{p-1}{2}.$$
ولا يمكن لأي قيمة أصغر من ذلك أن تعطي قاسمًا مشتركًا غير بديهي. فإذا كان هناك عدد \(q\) يقسم كلًا من \(a+t\) و\(2a-1\)، فإن أحد عوامله الأولية يقسم أيضًا \(2a-1\). ولكل عامل أولي \(q\) من عوامل \(2a-1\)، فإن أول حل موجب للشرط \(q \mid (a+t)\) هو \((q-1)/2\)، وهذا لا يقل عن \((p-1)/2\) لأن \(p\) هو الأصغر بينها.
لذلك نحصل على \(\gcd(a+t,2a-1)=1\) لكل \(1 \le t \lt t_0\)، وتحدث أول قفزة حقيقية بالضبط عند \(t=t_0\).
ضع \(a' = a+t_0\). عند هذه النقطة يقسم \(p\) كلًا من \(a'\) و\(2a-1\)، ولذلك يكون القاسم المشترك الأكبر على الأقل \(p\). ومن جهة أخرى إذا كتبنا
$$d=\gcd(a',2a-1),$$
فإن \(d\) يقسم أيضًا العدد
$$2a'-(2a-1)=2(a+t_0)-(2a-1)=p.$$
إذن لا بد أن يكون \(d=p\). أي إن مقدار القفزة عند \(a'\) يساوي تمامًا \(p=2t_0+1\).
وقبل هذه القفزة كانت المتتالية تزداد بمقدار \(1\) فقط في كل مرة، ولهذا
$$g(a'-1)=3a+(t_0-1).$$
وبعد إضافة القفزة نحصل على
$$g(a')=3a+(t_0-1)+p=3a+3t_0=3(a+t_0)=3a'.$$
وبذلك تعود البنية نفسها مرة أخرى. المؤشر البنيوي التالي هو
$$a'=a+\frac{p-1}{2},$$
حيث إن \(p\) هو أصغر عامل أولي للعدد \(2a-1\).
إذا كان الهدف \(N\) يقع قبل المؤشر البنيوي التالي بشكل صارم، فإن جميع الزيادات المتبقية تساوي \(1\). انطلاقًا من \(g(a)=3a\) نحصل على
$$g(N)=3a+(N-a)=N+2a.$$
أما إذا كان المؤشر البنيوي التالي يساوي \(N\) تمامًا، فإن الخطوة السابقة تعطي \(g(N)=3N\). وهكذا تصبح العلاقة كلها محددة بمجرد معرفة مؤشر بنيوي واحد.
أول مؤشر بنيوي هو \(a=9\). عندئذ
$$2a-1=17,$$
ومن ثم فإن أصغر عامل أولي هو \(17\)، والمؤشر البنيوي التالي يساوي
$$9+\frac{17-1}{2}=17.$$
لذلك تكون المتتالية خطية على المجال \(10 \le n \le 16\):
$$g(n)=n+18.$$
وعند \(n=17\) يكون مقدار القفزة \(17\)، ولذلك \(g(17)=51=3 \cdot 17\). وإذا أعدنا تطبيق القاعدة من \(a=17\)، نجد أن \(2a-1=33\) وأصغر عامل أولي له هو \(3\)، فيكون المؤشر البنيوي التالي هو \(18\). وهذا يطابق القيم المباشرة \(g(18)=54\) و\(g(20)=60\) و\(g(21)=63\).
تنفيذات C++ وPython وJava تعالج أولًا المدى القصير في البداية مباشرة، لأن نمط القفز لا يظهر إلا بعد أول مؤشر بنيوي عند \(9\). بعد ذلك تحتفظ بقيمة حالية \(a\) تحقق \(g(a)=3a\)، ثم تفكك العدد \(2a-1\) بالقدر اللازم فقط للحصول على أصغر عامل أولي، ومنها تحسب المؤشر التالي \(a+(p-1)/2\). فإذا كان هذا المؤشر التالي أكبر من الهدف، تعيد النتيجة فورًا من الصيغة الخطية \(g(N)=N+2a\). وإلا تكرر العملية من المؤشر البنيوي الجديد. أي إن التنفيذ هو ترجمة مباشرة للبرهان السابق.
الحل الساذج يحتاج إلى حساب gcd لكل عدد من \(5\) حتى \(N\)، وهذا غير ممكن عندما يكون \(N=10^{15}\). أما طريقة القفز فتزور فقط المؤشرات البنيوية التي تولدها العلاقة فعلًا. في هذه التنفيذات يتم إيجاد أصغر عامل أولي للعدد \(2a-1\) في كل خطوة بواسطة القسمة التجريبية وفق النمط القياسي \(2,3,6k \pm 1\). إذا كانت المؤشرات المزارة هي \(a_0,a_1,\dots,a_m\)، فإن الكلفة الكلية تساوي مجموع كلف هذه التحليلات، بينما تبقى الذاكرة \(O(1)\). وبالنسبة إلى الهدف الفعلي في المسألة، فإن عدد القفزات ضئيل جدًا مقارنة بـ \(10^{15}\)، ولذلك يكون التنفيذ سريعًا عمليًا.