The sequence is defined by
$$u_{0}=-1,\qquad u_{n+1}=f(u_n),\qquad f(x)=\lfloor 2^{30.403243784-x^2}\rfloor\cdot10^{-9}.$$
We are asked for \(u_n+u_{n+1}\) when \(n\) is very large. The important point is that this is not a symbolic closed-form problem; it is a discrete dynamical-system problem with a heavily quantized update rule.
The entire solution comes from understanding what the floor and the factor \(10^{-9}\) do to the orbit. They turn a nonlinear recurrence into a bounded map on a finite grid, and for the given initial value that orbit rapidly falls onto an attracting 2-cycle.
Because \(x^2\ge 0\), the exponent \(30.403243784-x^2\) is never larger than \(30.403243784\). Therefore
$$0\le f(x)\le \lfloor 2^{30.403243784}\rfloor\cdot10^{-9}=1.420000000.$$
So after the first iteration, every term of the sequence lies in the compact interval \([0,1.42]\).
Even more importantly, the floor forces every value onto the grid
$$\{k\cdot10^{-9}:0\le k\le 1{,}420{,}000{,}000\}.$$
That means the recurrence is not wandering through a continuum of real numbers. It is moving through a finite set of decimal values spaced exactly \(10^{-9}\) apart.
Once a deterministic map sends a finite set into itself, every orbit must eventually repeat. In other words, for some indices \(m<n\) we must have \(u_m=u_n\), and from that point onward the sequence becomes periodic.
For this problem, the solutions do not try to classify every possible eventual cycle of \(f\). They only need the orbit starting from \(u_0=-1\). Numerically, that orbit very quickly approaches a cycle of length 2.
It is useful to introduce the two-step map
$$g(x)=f(f(x)).$$
If the late orbit alternates between two values \(a\) and \(b\), then
$$a=f(b),\qquad b=f(a),\qquad g(a)=a,\qquad g(b)=b.$$
So the two-cycle of \(f\) appears as fixed points of the even-step recurrence \(u_{n+2}=g(u_n)\).
Starting from \(u_0=-1\), the first few terms are
$$u_1=0.710000000,\qquad u_2=1.001242148,\qquad u_3=0.708777686,\qquad u_4=1.002446415.$$
Continuing a little farther gives
$$u_5=0.707593212,\qquad u_6=1.003612800,\qquad u_7=0.706446531,\qquad u_8=1.004741400.$$
This already shows the pattern that the implementations exploit: the odd subsequence moves downward, the even subsequence moves upward, and the orbit is being squeezed toward an alternating pair rather than toward a single fixed point.
After a modest burn-in, the late terms are
$$u_{1000}=1.029461839,\qquad u_{1001}=0.681175878,\qquad u_{1002}=1.029461839.$$
So to the required output precision the recurrence has settled on the 2-cycle
$$1.029461839\longleftrightarrow 0.681175878.$$
If \(u_n\) alternates between \(a\) and \(b\) for large \(n\), then the parity of \(n\) only swaps the order of the pair. In either case,
$$u_n+u_{n+1}=a+b.$$
For the present orbit, the stabilized value is therefore
$$1.029461839+0.681175878=1.710637717.$$
This is why the implementations do not need to detect the cycle explicitly. A sufficiently late consecutive pair already contains the final answer.
The C++, Python, and Java implementations all use the same update rule: square the current value, subtract from \(30.403243784\), raise 2 to that power, take the floor, and multiply by \(10^{-9}\). No algebraic simplification is attempted, because the floor is the crucial feature of the problem.
The implementations start from \(u=-1\) and repeatedly apply the map. The Python and Java versions use 1000 iterations, while the C++ version defaults to 100000 and allows that count to be adjusted. All of those choices are comfortably large compared with the very fast observed approach to the 2-cycle.
After the burn-in phase, the implementation computes one more value \(v=f(u)\) and returns \(u+v\). That sum is exactly what the mathematics above predicts: once \(u\) is a late term on the attracting 2-cycle, \(u\) and \(v\) are the two alternating states whose sum is independent of parity.
The C++ version also includes sanity checks. One verifies the first nontrivial value \(f(-1)=0.710000000\); another verifies that a long run gives the stabilized sum \(1.710637717\). These checks match the underlying dynamical picture.
If the recurrence is iterated \(N\) times, the running time is \(O(N)\). Each step performs one exponentiation, one floor operation, and a small amount of arithmetic.
The memory usage is \(O(1)\), because the implementation only keeps the current value and then one additional iterate for the final sum. No history table, cycle-detection structure, or memoization is required.
Die Folge ist definiert durch
$$u_{0}=-1,\qquad u_{n+1}=f(u_n),\qquad f(x)=\lfloor 2^{30.403243784-x^2}\rfloor\cdot10^{-9}.$$
Gesucht ist \(u_n+u_{n+1}\) für sehr großes \(n\). Der Kern des Problems ist nicht eine geschlossene Formel für \(u_n\), sondern das Langzeitverhalten einer nichtlinearen, durch die Abrundung stark quantisierten Iteration.
Die Lösung entsteht aus zwei Beobachtungen: Erstens ist die Abbildung beschränkt, zweitens liefert der Floor nur Werte auf einem feinen Dezimalgitter. Dadurch wird die Rekursion zu einem diskreten dynamischen System mit endlich vielen Zuständen, und für den Startwert \(u_0=-1\) läuft die Bahn schnell in einen attraktiven 2-Zyklus.
Da stets \(x^2\ge 0\) gilt, ist der Exponent \(30.403243784-x^2\) niemals größer als \(30.403243784\). Also folgt
$$0\le f(x)\le \lfloor 2^{30.403243784}\rfloor\cdot10^{-9}=1.420000000.$$
Schon ab \(u_1\) liegt die gesamte Folge also im Intervall \([0,1.42]\).
Wichtiger noch: Durch den Floor kann \(f(x)\) nur Werte der Form
$$k\cdot10^{-9}\qquad (0\le k\le 1{,}420{,}000{,}000)$$
annehmen. Die Iteration bewegt sich damit nicht auf einem Kontinuum von reellen Zahlen, sondern auf einer endlichen Menge äquidistanter Dezimalwerte.
Eine deterministische Abbildung von einer endlichen Menge in sich selbst erzeugt auf jeder Bahn irgendwann eine Wiederholung. Es gibt also Indizes \(m<n\) mit \(u_m=u_n\), und ab dort ist die Folge periodisch.
Für diese Aufgabe müssen die Implementierungen nicht alle möglichen Perioden klassifizieren. Relevant ist nur die Bahn mit Startwert \(-1\), und diese nähert sich numerisch sehr schnell einem Zyklus der Länge 2.
Dazu ist die Zweischritt-Abbildung
$$g(x)=f(f(x))$$
nützlich. Wenn die späte Bahn zwischen zwei Werten \(a\) und \(b\) pendelt, dann gilt
$$a=f(b),\qquad b=f(a),\qquad g(a)=a,\qquad g(b)=b.$$
Der 2-Zyklus von \(f\) erscheint also als Fixpunktstruktur der geraden Teilfolge \(u_{n+2}=g(u_n)\).
Beginnend mit \(u_0=-1\) erhält man die ersten Terme
$$u_1=0.710000000,\qquad u_2=1.001242148,\qquad u_3=0.708777686,\qquad u_4=1.002446415.$$
Noch etwas weiter gerechnet:
$$u_5=0.707593212,\qquad u_6=1.003612800,\qquad u_7=0.706446531,\qquad u_8=1.004741400.$$
Man sieht bereits das charakteristische Muster: Die ungeraden Glieder wandern nach unten, die geraden nach oben. Die Folge strebt also nicht zu einem einzelnen Fixpunkt, sondern wird zwischen zwei Grenzwerten eingeklemmt.
Nach einer kurzen Einschwingphase liegen späte Terme bei
$$u_{1000}=1.029461839,\qquad u_{1001}=0.681175878,\qquad u_{1002}=1.029461839.$$
Damit ist auf der geforderten Ausgabegenauigkeit der 2-Zyklus
$$1.029461839\longleftrightarrow 0.681175878$$
erreicht.
Wenn die Folge für große \(n\) zwischen \(a\) und \(b\) alterniert, dann vertauscht die Parität von \(n\) nur die Reihenfolge der beiden Werte. In beiden Fällen gilt
$$u_n+u_{n+1}=a+b.$$
Für die konkrete Bahn ergibt das
$$1.029461839+0.681175878=1.710637717.$$
Genau deshalb genügt es, zwei aufeinanderfolgende späte Werte zu summieren. Eine explizite Zykluserkennung ist nicht notwendig.
Die C++-, Python- und Java-Implementierungen benutzen exakt die gegebene Vorschrift: aktuelles \(u\) quadrieren, von \(30.403243784\) abziehen, \(2\) hoch diesen Wert nehmen, abrunden und mit \(10^{-9}\) multiplizieren. Gerade die Abrundung ist der wesentliche mathematische Mechanismus, deshalb wird hier nichts symbolisch vereinfacht.
Alle Implementierungen starten mit \(u=-1\) und wenden die Abbildung viele Male an. Python und Java verwenden 1000 Schritte; die C++-Version nutzt standardmäßig 100000 Schritte und erlaubt eine andere Iterationszahl. Diese Werte liegen deutlich oberhalb dessen, was für neun korrekte Nachkommastellen nötig ist.
Nach der Einschwingphase wird noch ein weiterer Wert \(v=f(u)\) berechnet und anschließend \(u+v\) ausgegeben. Mathematisch ist das genau die Summe der beiden alternierenden Zustände des attraktiven 2-Zyklus.
Die C++-Implementierung enthält zusätzlich Plausibilitätsprüfungen: einmal für den ersten nichttrivialen Wert \(f(-1)=0.710000000\) und einmal für die stabilisierte Summe \(1.710637717\). Beide Tests passen präzise zum beschriebenen dynamischen Verhalten.
Bei \(N\) Iterationen beträgt die Laufzeit \(O(N)\). Jeder Schritt enthält eine Potenzberechnung, eine Floor-Operation und einige wenige elementare Rechenoperationen.
Der Speicherbedarf ist \(O(1)\), weil nur der aktuelle Wert und danach noch ein zusätzlicher Folgewert gespeichert werden. Weder eine Historie noch eine explizite Zyklusdetektion sind erforderlich.
Dizi şu şekilde tanımlanır:
$$u_{0}=-1,\qquad u_{n+1}=f(u_n),\qquad f(x)=\lfloor 2^{30.403243784-x^2}\rfloor\cdot10^{-9}.$$
İstenen büyüklük, \(n\) çok büyükken \(u_n+u_{n+1}\) toplamıdır. Bu soru kapalı form bulma sorusu değil; floor işlemi nedeniyle ayrıklaşmış bir dinamik sistemin uzun vadeli davranışını anlama sorusudur.
Çözümün özü, yinelemeyi iki açıdan okumaktır: Harita hem sınırlıdır hem de çıktıyı \(10^{-9}\) aralıklı bir ızgaraya zorlar. Böylece gerçek sayılar üzerinde serbestçe dolaşan bir süreç değil, sonlu sayıda durum arasında ilerleyen bir sistem elde ederiz. Verilen başlangıç değeri için bu yörünge hızlı biçimde çekici bir 2-döngüye oturur.
\(x^2\ge 0\) olduğundan üs \(30.403243784-x^2\) en fazla \(30.403243784\) olabilir. Dolayısıyla
$$0\le f(x)\le \lfloor 2^{30.403243784}\rfloor\cdot10^{-9}=1.420000000.$$
Yani ilk adımdan sonra bütün terimler \([0,1.42]\) aralığındadır.
Daha da önemlisi, floor yüzünden her çıktı şu kümeden gelir:
$$\{k\cdot10^{-9}:0\le k\le 1{,}420{,}000{,}000\}.$$
Başka bir deyişle, süreç sürekli bir reel aralıkta değil, araları tam olarak \(10^{-9}\) olan sonlu bir ondalık kafeste hareket eder.
Deterministik bir fonksiyon sonlu bir kümeyi yine kendisine gönderiyorsa, herhangi bir başlangıçtan çıkan yörünge sonunda mutlaka bir değeri tekrar ziyaret eder. O andan sonra dizi periyodik hale gelir.
Bu problemde çözümler bütün olası periyotları sınıflandırmaya çalışmaz. Yalnızca \(u_0=-1\) başlangıcından çıkan yörünge gerekir ve bu yörünge sayısal olarak çok hızlı biçimde uzunluğu 2 olan bir döngüye yaklaşır.
İki adımlı dönüşümü
$$g(x)=f(f(x))$$
olarak tanımlarsak, geç aşamadaki iki değer \(a\) ve \(b\) için
$$a=f(b),\qquad b=f(a),\qquad g(a)=a,\qquad g(b)=b$$
olur. Yani \(f\)'in 2-döngüsü, \(u_{n+2}=g(u_n)\) bağıntısında sabit nokta gibi görünür.
\(u_0=-1\) ile başlayınca ilk birkaç terim şöyledir:
$$u_1=0.710000000,\qquad u_2=1.001242148,\qquad u_3=0.708777686,\qquad u_4=1.002446415.$$
Biraz daha ilerleyince
$$u_5=0.707593212,\qquad u_6=1.003612800,\qquad u_7=0.706446531,\qquad u_8=1.004741400$$
elde edilir. Burada kritik davranış hemen görülür: tek indeksli terimler aşağı inerken çift indeksli terimler yukarı çıkar. Dizi tek bir sabit noktaya değil, iki değer arasında gidip gelen bir yapıya sıkışmaktadır.
Daha geç bir aşamada ise
$$u_{1000}=1.029461839,\qquad u_{1001}=0.681175878,\qquad u_{1002}=1.029461839$$
olur. Böylece gereken hassasiyet düzeyinde 2-döngü
$$1.029461839\longleftrightarrow 0.681175878$$
olarak okunur.
Geç terimler \(a\) ve \(b\) arasında gidip geliyorsa, \(n\)'nin tek ya da çift olması yalnızca bu iki değerin sırasını değiştirir. Her durumda
$$u_n+u_{n+1}=a+b$$
olur. Bu problem için sabitlenen toplam
$$1.029461839+0.681175878=1.710637717$$
değeridir. Bu yüzden kodun ayrıca döngü tespiti yapmasına gerek yoktur; yeterince geç iki komşu terim doğrudan cevabı verir.
C++, Python ve Java uygulamaları aynı güncelleme kuralını kullanır: mevcut değerin karesi alınır, \(30.403243784\)'ten çıkarılır, 2 bu üssün kuvveti olarak hesaplanır, floor uygulanır ve sonuç \(10^{-9}\) ile çarpılır. Problemdeki asıl yapı floor ile oluştuğu için sembolik sadeleştirme yapılmaz.
Uygulamalar \(u=-1\) ile başlar ve fonksiyonu art arda uygular. Python ve Java sürümleri 1000 iterasyon yapar; C++ sürümü varsayılan olarak 100000 iterasyon kullanır ve bu sayı değiştirilebilir. Bu değerlerin hepsi, dokuz ondalık basamakta kararlı sonuca ulaşmak için fazlasıyla yeterlidir.
Uzun iterasyondan sonra bir kez daha \(v=f(u)\) hesaplanır ve çıktı olarak \(u+v\) verilir. Matematiksel olarak bu, çekici 2-döngünün iki durumunun toplamıdır.
C++ sürümünde ek olarak iki sağlamlık kontrolü vardır: biri ilk anlamlı değer olan \(f(-1)=0.710000000\), diğeri ise uzun iterasyondan sonra elde edilen \(1.710637717\) toplamı içindir. Bunlar, yukarıda açıklanan dinamik resmi doğrular.
Yineleme \(N\) kez uygulanırsa zaman karmaşıklığı \(O(N)\) olur. Her adımda bir üs alma işlemi, bir floor ve birkaç aritmetik işlem yapılır.
Bellek kullanımı \(O(1)\)'dir; çünkü yalnızca güncel değer ve son toplam için bir sonraki değer tutulur. Geçmiş terimleri saklamaya, ayrı bir döngü tespit yapısına ya da önbelleğe ihtiyaç yoktur.
La sucesión está definida por
$$u_{0}=-1,\qquad u_{n+1}=f(u_n),\qquad f(x)=\lfloor 2^{30.403243784-x^2}\rfloor\cdot10^{-9}.$$
Hay que determinar \(u_n+u_{n+1}\) cuando \(n\) es muy grande. No se trata de encontrar una fórmula cerrada para todos los términos, sino de entender el comportamiento asintótico de una iteración no lineal con cuantización decimal.
La idea central es que la función está acotada y, además, el operador piso obliga a que cada valor caiga sobre una rejilla de paso \(10^{-9}\). Eso convierte el problema en un sistema dinámico discreto sobre un conjunto finito de estados. Para el valor inicial dado, la órbita entra rápidamente en un ciclo atractivo de longitud 2.
Como \(x^2\ge 0\), el exponente \(30.403243784-x^2\) nunca supera \(30.403243784\). Por tanto,
$$0\le f(x)\le \lfloor 2^{30.403243784}\rfloor\cdot10^{-9}=1.420000000.$$
Así, desde la primera iteración todos los términos quedan dentro del intervalo \([0,1.42]\).
Además, debido al piso, la imagen de \(f\) está contenida en
$$\{k\cdot10^{-9}:0\le k\le 1{,}420{,}000{,}000\}.$$
La órbita ya no recorre un continuo de números reales, sino un conjunto finito de valores decimales separados exactamente por \(10^{-9}\).
Cuando una función determinista envía un conjunto finito en sí mismo, toda órbita debe repetir algún estado tarde o temprano. En consecuencia, la sucesión se vuelve periódica a partir de cierto momento.
En este problema no hace falta clasificar todos los ciclos posibles de \(f\). Solo importa la órbita que parte de \(u_0=-1\), y esa órbita se acerca muy deprisa, de forma numérica, a un ciclo de periodo 2.
Conviene introducir la aplicación de dos pasos
$$g(x)=f(f(x)).$$
Si los términos tardíos alternan entre \(a\) y \(b\), entonces
$$a=f(b),\qquad b=f(a),\qquad g(a)=a,\qquad g(b)=b.$$
Es decir, el 2-ciclo de \(f\) aparece como un par de puntos fijos de la recurrencia \(u_{n+2}=g(u_n)\).
Partiendo de \(u_0=-1\), los primeros términos son
$$u_1=0.710000000,\qquad u_2=1.001242148,\qquad u_3=0.708777686,\qquad u_4=1.002446415.$$
Un poco más adelante obtenemos
$$u_5=0.707593212,\qquad u_6=1.003612800,\qquad u_7=0.706446531,\qquad u_8=1.004741400.$$
Ya se aprecia el patrón relevante: la subsecuencia impar desciende y la subsecuencia par asciende. La dinámica no se dirige a un único punto fijo, sino a una pareja alternante.
Tras un número moderado de iteraciones, aparecen los valores tardíos
$$u_{1000}=1.029461839,\qquad u_{1001}=0.681175878,\qquad u_{1002}=1.029461839.$$
Por tanto, con la precisión pedida, la sucesión ha alcanzado el 2-ciclo
$$1.029461839\longleftrightarrow 0.681175878.$$
Si para \(n\) grande la órbita alterna entre \(a\) y \(b\), la paridad de \(n\) solo invierte el orden. En ambos casos se cumple
$$u_n+u_{n+1}=a+b.$$
En este problema, la cantidad estabilizada es
$$1.029461839+0.681175878=1.710637717.$$
Por eso basta con tomar dos términos consecutivos muy avanzados. No hace falta detectar formalmente el ciclo: la suma ya está fijada.
Las implementaciones en C++, Python y Java aplican exactamente la recurrencia dada: elevan 2 al exponente \(30.403243784-u^2\), toman el piso y multiplican por \(10^{-9}\). No se intenta una simplificación algebraica, porque el piso es precisamente la característica que produce la discretización del sistema.
Todas las versiones comienzan en \(u=-1\) y repiten la transformación muchas veces. Python y Java usan 1000 iteraciones; C++ usa 100000 por defecto y permite cambiar ese número. En todos los casos, el margen es más que suficiente para fijar la respuesta a nueve decimales.
Después de la fase de estabilización, la implementación calcula un valor extra \(v=f(u)\) y devuelve \(u+v\). Matemáticamente, eso coincide con la suma de los dos estados del ciclo atractivo.
La versión en C++ añade comprobaciones sencillas: una confirma que \(f(-1)=0.710000000\) y otra confirma que una ejecución larga produce la suma estabilizada \(1.710637717\). Ambas verificaciones reflejan exactamente la estructura matemática de la órbita.
Si se realizan \(N\) iteraciones, el tiempo total es \(O(N)\). Cada paso necesita una exponenciación, una operación de piso y unas pocas operaciones aritméticas elementales.
El consumo de memoria es \(O(1)\), porque solo se mantiene el valor actual y luego un valor adicional para formar la suma final. No se almacenan términos anteriores ni se usa ninguna estructura especial para detectar ciclos.
数列定义为
$$u_{0}=-1,\qquad u_{n+1}=f(u_n),\qquad f(x)=\lfloor 2^{30.403243784-x^2}\rfloor\cdot10^{-9}.$$
要求的是当 \(n\) 很大时的 \(u_n+u_{n+1}\)。这个问题的重点并不是把 \(u_n\) 写成闭式，而是分析一个带有取整操作的非线性递推在长时间迭代后的行为。
真正起决定作用的是两件事：一是映射 \(f\) 的值域是有界的，二是取整加上乘以 \(10^{-9}\) 以后，所有输出都落在一个非常细的十进制格点上。这样一来，递推不再是在实数连续区间里自由移动，而是在一个有限状态集合上做确定性的迭代。对于题目给定的初值 \(u_0=-1\)，这条轨道会很快进入一个吸引性的 2 周期。
因为始终有 \(x^2\ge 0\)，所以指数 \(30.403243784-x^2\) 不会超过 \(30.403243784\)。因此
$$0\le f(x)\le \lfloor 2^{30.403243784}\rfloor\cdot10^{-9}=1.420000000.$$
这说明从第一步开始，整个数列就被限制在区间 \([0,1.42]\) 内。
更关键的是，取整使得 \(f(x)\) 只能取如下形式的值：
$$\{k\cdot10^{-9}:0\le k\le 1{,}420{,}000{,}000\}.$$
也就是说，递推并不是在无穷多个任意实数之间变化，而是在步长恰好为 \(10^{-9}\) 的有限十进制格点上跳动。
一个确定性函数如果把有限集合映到自身，那么从任何初始状态出发，轨道迟早会重复某个值。一旦重复出现，之后的行为就会进入周期。
在这道题里，并不需要对 \(f\) 的所有可能周期做完整分类。实现真正关心的只是从 \(u_0=-1\) 出发的那一条轨道，而这条轨道从数值上看会很快靠近一个长度为 2 的周期。
为此可以引入两步映射
$$g(x)=f(f(x)).$$
如果后期轨道在两个值 \(a\) 和 \(b\) 之间交替，那么就有
$$a=f(b),\qquad b=f(a),\qquad g(a)=a,\qquad g(b)=b.$$
于是，\(f\) 的 2 周期就等价于两步递推 \(u_{n+2}=g(u_n)\) 中的固定点结构。
从 \(u_0=-1\) 开始，前几项是
$$u_1=0.710000000,\qquad u_2=1.001242148,\qquad u_3=0.708777686,\qquad u_4=1.002446415.$$
继续往后算，可以得到
$$u_5=0.707593212,\qquad u_6=1.003612800,\qquad u_7=0.706446531,\qquad u_8=1.004741400.$$
这里已经能清楚看到问题的核心结构：奇数下标子序列在下降，偶数下标子序列在上升。也就是说，轨道不是向单个固定点收敛，而是在两个极限值之间被“夹住”。
经过不算很长的预热以后，后期的项变成
$$u_{1000}=1.029461839,\qquad u_{1001}=0.681175878,\qquad u_{1002}=1.029461839.$$
因此在题目要求的输出精度下，递推已经稳定在 2 周期
$$1.029461839\longleftrightarrow 0.681175878$$
上。
如果大 \(n\) 时 \(u_n\) 在 \(a\) 与 \(b\) 之间交替，那么 \(n\) 的奇偶性只会交换它们的顺序，而不会改变相邻两项之和。因此
$$u_n+u_{n+1}=a+b.$$
对本题而言，这个稳定值就是
$$1.029461839+0.681175878=1.710637717.$$
这就是为什么实现只需要取两个足够靠后的相邻项。哪怕没有显式写出“循环检测”，答案也已经被这对后期数值固定下来了。
C++、Python 和 Java 实现都严格按照题目中的公式更新当前值：先算 \(u^2\)，从 \(30.403243784\) 中减掉，再计算 \(2\) 的该次幂，取 floor，最后乘以 \(10^{-9}\)。这里没有做代数化简，因为取整正是问题最本质的部分。
所有实现都从 \(u=-1\) 开始，不断重复应用 \(f\)。Python 和 Java 使用 1000 次迭代；C++ 默认使用 100000 次，并允许调整。相对于轨道靠近 2 周期的速度来说，这些步数都绰绰有余，足以保证九位小数上的稳定输出。
在预热结束后，实现再计算一个额外值 \(v=f(u)\)，然后输出 \(u+v\)。这正对应于数学分析中的后期两状态之和。
C++ 版本还加入了简单的校验：一个确认第一步 \(f(-1)=0.710000000\)，另一个确认长时间迭代后的稳定和为 \(1.710637717\)。这些检查与上面的动力系统分析完全一致。
如果总共迭代 \(N\) 次，时间复杂度就是 \(O(N)\)。每一步只包含一次指数运算、一次取整和少量基本算术。
空间复杂度是 \(O(1)\)，因为实现只保存当前值，以及最后求和时额外的下一项。它不需要保存整个历史轨道，也不需要额外的周期检测表。
Последовательность задаётся формулами
$$u_{0}=-1,\qquad u_{n+1}=f(u_n),\qquad f(x)=\lfloor 2^{30.403243784-x^2}\rfloor\cdot10^{-9}.$$
Нужно найти \(u_n+u_{n+1}\) при очень большом \(n\). Это не задача на вывод явной формулы для всех членов, а задача на исследование предельного поведения нелинейной рекуррентной схемы с жёсткой квантовкой из-за функции пола.
Решение строится вокруг двух свойств отображения \(f\): оно ограничено сверху, а его значения всегда лежат на сетке с шагом \(10^{-9}\). Поэтому рекурсия фактически работает не на непрерывном множестве вещественных чисел, а на конечном наборе состояний. Для начального значения \(u_0=-1\) орбита быстро попадает в притягивающий цикл длины 2.
Поскольку \(x^2\ge 0\), показатель \(30.403243784-x^2\) не может превышать \(30.403243784\). Следовательно,
$$0\le f(x)\le \lfloor 2^{30.403243784}\rfloor\cdot10^{-9}=1.420000000.$$
Значит, уже после первого шага вся последовательность остаётся внутри отрезка \([0,1.42]\).
Кроме того, из-за округления вниз все значения имеют вид
$$\{k\cdot10^{-9}:0\le k\le 1{,}420{,}000{,}000\}.$$
Иными словами, динамика идёт по конечной десятичной решётке, а не по сплошному континууму.
Если детерминированная функция переводит конечное множество в себя, любая орбита рано или поздно повторит уже встречавшееся состояние. После этого дальнейшее поведение становится периодическим.
Для данной задачи не требуется аналитически перечислять все возможные циклы. Нужна только орбита, стартующая из \(u_0=-1\), и численно видно, что она очень быстро приближается к 2-циклу.
Удобно рассмотреть двухшаговое отображение
$$g(x)=f(f(x)).$$
Если на поздних шагах последовательность чередует значения \(a\) и \(b\), то выполняется
$$a=f(b),\qquad b=f(a),\qquad g(a)=a,\qquad g(b)=b.$$
Тем самым 2-цикл исходной функции превращается в фиксированные точки рекурсии \(u_{n+2}=g(u_n)\).
При старте с \(u_0=-1\) первые члены таковы:
$$u_1=0.710000000,\qquad u_2=1.001242148,\qquad u_3=0.708777686,\qquad u_4=1.002446415.$$
Ещё несколько шагов дают
$$u_5=0.707593212,\qquad u_6=1.003612800,\qquad u_7=0.706446531,\qquad u_8=1.004741400.$$
Уже здесь хорошо видно характерное поведение: нечётная подпоследовательность идёт вниз, чётная вверх. Орбита не стремится к одной неподвижной точке, а зажимается между двумя предельными значениями.
После умеренного числа шагов получаем поздние значения
$$u_{1000}=1.029461839,\qquad u_{1001}=0.681175878,\qquad u_{1002}=1.029461839.$$
Значит, с требуемой точностью рекурсия уже находится на цикле
$$1.029461839\longleftrightarrow 0.681175878.$$
Если для больших \(n\) последовательность чередует \(a\) и \(b\), то чётность \(n\) лишь меняет порядок этих двух чисел. Поэтому всегда
$$u_n+u_{n+1}=a+b.$$
В нашем случае стабилизированная сумма равна
$$1.029461839+0.681175878=1.710637717.$$
Именно поэтому реализации не нужно явно распознавать цикл. Достаточно взять два соседних достаточно поздних члена.
Реализации на C++, Python и Java буквально повторяют определение \(f\): берут квадрат текущего значения, вычитают его из \(30.403243784\), вычисляют степень двойки, затем применяют floor и умножают на \(10^{-9}\). Здесь ничего не упрощается символически, потому что именно floor создаёт дискретную структуру задачи.
Все версии стартуют с \(u=-1\) и многократно применяют отображение. В Python и Java используется 1000 итераций; в C++ по умолчанию 100000, причём это число можно менять. Все эти значения намного превосходят реальное число шагов, нужное для стабилизации ответа до девяти знаков после запятой.
После прогрева вычисляется ещё одно значение \(v=f(u)\), после чего печатается \(u+v\). С точки зрения математики это и есть сумма двух состояний притягивающего 2-цикла.
В версии на C++ есть и простые проверки: одна подтверждает, что \(f(-1)=0.710000000\), другая подтверждает стабилизированную сумму \(1.710637717\). Эти проверки согласуются с описанной выше динамикой.
Если выполнить \(N\) итераций, то время работы равно \(O(N)\). На каждом шаге выполняются одна экспонента, одна операция floor и несколько элементарных арифметических действий.
Память имеет порядок \(O(1)\), потому что хранится только текущее значение и затем ещё один следующий член для финальной суммы. Никакая таблица истории или отдельный механизм обнаружения циклов не требуются.
المتتالية معرّفة بالعلاقات
$$u_{0}=-1,\qquad u_{n+1}=f(u_n),\qquad f(x)=\lfloor 2^{30.403243784-x^2}\rfloor\cdot10^{-9}.$$
المطلوب هو قيمة \(u_n+u_{n+1}\) عندما يكون \(n\) كبيرًا جدًا. جوهر المسألة ليس إيجاد صيغة مغلقة لكل حد، بل فهم السلوك النهائي لتكرار غير خطي تحكمه عملية أخذ الجزء الصحيح.
الفكرة الأساسية أن الدالة \(f\) محصورة من الأعلى، وأن عملية الجزء الصحيح تجعل كل قيمة تقع على شبكة عشرية خطوةُها \(10^{-9}\). لذلك لا تتحرك المتتالية داخل مجال مستمر من الأعداد الحقيقية، بل داخل مجموعة منتهية من الحالات. ومع القيمة الابتدائية \(u_0=-1\) تهبط هذه المداراة بسرعة إلى دورة جاذبة طولها 2.
بما أن \(x^2\ge 0\)، فإن الأس \(30.403243784-x^2\) لا يمكن أن يكون أكبر من \(30.403243784\). ومن ثم
$$0\le f(x)\le \lfloor 2^{30.403243784}\rfloor\cdot10^{-9}=1.420000000.$$
وهذا يعني أن جميع الحدود بعد أول تكرار تبقى داخل المجال \([0,1.42]\).
والأهم من ذلك أن \(f(x)\) لا تأخذ إلا قيمًا من الشكل
$$\{k\cdot10^{-9}:0\le k\le 1{,}420{,}000{,}000\}.$$
أي أن التكرار يتحرك على شبكة عشرية منتهية، لا على متصل حقيقي كامل.
إذا كانت لدينا دالة حتمية ترسل مجموعة منتهية إلى نفسها، فكل مدار لا بد أن يزور حالة سابقة في مرحلة ما. ومن تلك اللحظة يصبح السلوك دوريًا.
في هذه المسألة لا تحتاج الحلول إلى تصنيف جميع الدورات الممكنة للدالة \(f\). المطلوب فقط هو المدار الذي يبدأ من \(u_0=-1\)، وهذا المدار يقترب عدديًا بسرعة شديدة من دورة طولها 2.
ومن المفيد تعريف التحويل ذي الخطوتين
$$g(x)=f(f(x)).$$
فإذا كانت القيم المتأخرة تتناوب بين \(a\) و\(b\)، فإن
$$a=f(b),\qquad b=f(a),\qquad g(a)=a,\qquad g(b)=b.$$
وهكذا تظهر دورة \(f\) الثنائية على أنها نقاط ثابتة لتحويل الخطوتين \(u_{n+2}=g(u_n)\).
إذا بدأنا من \(u_0=-1\)، فإن الحدود الأولى هي
$$u_1=0.710000000,\qquad u_2=1.001242148,\qquad u_3=0.708777686,\qquad u_4=1.002446415.$$
وبالاستمرار قليلًا نحصل على
$$u_5=0.707593212,\qquad u_6=1.003612800,\qquad u_7=0.706446531,\qquad u_8=1.004741400.$$
يتضح هنا النمط الذي تعتمد عليه الشيفرات: الحدود ذات الفهارس الفردية تنخفض، بينما الحدود ذات الفهارس الزوجية ترتفع. إذن المتتالية لا تتجه إلى نقطة ثابتة واحدة، بل تنضغط نحو زوج متناوب من القيم.
وبعد مرحلة قصيرة نسبيًا من التهيئة تصبح الحدود المتأخرة
$$u_{1000}=1.029461839,\qquad u_{1001}=0.681175878,\qquad u_{1002}=1.029461839.$$
ومن ثم، عند دقة الإخراج المطلوبة، تكون المتتالية قد استقرت على الدورة الثنائية
$$1.029461839\longleftrightarrow 0.681175878.$$
إذا كانت القيم الكبيرة تتناوب بين \(a\) و\(b\)، فإن كون \(n\) زوجيًا أو فرديًا لا يغيّر إلا ترتيب هاتين القيمتين. وفي كلتا الحالتين يكون
$$u_n+u_{n+1}=a+b.$$
وفي هذه المسألة نحصل على
$$1.029461839+0.681175878=1.710637717.$$
لهذا السبب يكفي أخذ حدين متتاليين متأخرين جدًا. لا حاجة إلى كشف الدورة صراحة ما دامت هذه القيم المتأخرة قد ثبّتت المجموع المطلوب.
تنفّذ تطبيقات C++ وPython وJava القاعدة نفسها حرفيًا: تُربّع القيمة الحالية، ثم تُطرح من \(30.403243784\)، ثم يُحسب \(2\) مرفوعًا إلى هذه القوة، ثم يُؤخذ الجزء الصحيح، وأخيرًا تُضرب النتيجة في \(10^{-9}\). لا توجد محاولة لتبسيط جبري، لأن عملية الجزء الصحيح هي العنصر البنيوي الأهم في المسألة.
تبدأ جميع التطبيقات من \(u=-1\) وتكرر التحويل مرات كثيرة. نسخة Python ونسخة Java تستخدمان 1000 تكرار، بينما تستخدم نسخة C++ افتراضيًا 100000 تكرار مع إمكانية التعديل. وكل هذه الأعداد أكبر بكثير مما يلزم عمليًا لتثبيت الجواب حتى تسعة منازل عشرية.
بعد مرحلة التهيئة، تُحسب قيمة إضافية \(v=f(u)\)، ثم يُطبع \(u+v\). وهذا يطابق تمامًا التفسير الرياضي: المجموع هو مجموع حالتي الدورة الثنائية الجاذبة.
وتضيف نسخة C++ فحصين بسيطين: أحدهما يؤكد أن \(f(-1)=0.710000000\)، والآخر يؤكد أن التشغيل الطويل يعطي المجموع المستقر \(1.710637717\). هذان الفحصان منسجمان تمامًا مع صورة النظام الديناميكي الموضحة أعلاه.
إذا أجرينا \(N\) تكرارًا، فإن زمن التنفيذ يساوي \(O(N)\). كل خطوة تحتوي على عملية أسية واحدة، وعملية floor واحدة، وبعض العمليات الحسابية البسيطة.
أما الذاكرة فهي \(O(1)\)، لأن التنفيذ يحتفظ فقط بالقيمة الحالية ثم بالقيمة التالية اللازمة للمجموع النهائي. لا حاجة إلى تخزين التاريخ الكامل للمتتالية ولا إلى بنية منفصلة لاكتشاف الدورات.