We seek six distinct 4-digit figurate numbers, one from each of the triangular, square, pentagonal, hexagonal, heptagonal, and octagonal families. They must form a cycle: the last two digits of each number must equal the first two digits of the next, and the sixth number must link back to the first.
The problem is small enough to solve by exhaustive search, but only after we turn the infinite figurate sequences into a finite candidate set and exploit the strong prefix-suffix constraint. The implementations therefore generate all admissible 4-digit values and then search recursively for a six-term cycle that uses each family exactly once.
The six figurate families used in the problem are
\[ T_n=\frac{n(n+1)}{2}, \quad S_n=n^2, \quad P_n=\frac{n(3n-1)}{2}, \quad H_n=n(2n-1), \quad \operatorname{Hp}_n=\frac{n(5n-3)}{2}, \quad O_n=n(3n-2). \]
For each family we only care about values in the interval \(1000 \le x \le 9999\), because the cycle must be built from 4-digit numbers.
Solving the inequalities \(1000 \le x \le 9999\) for each formula shows that only finitely many indices matter: triangular numbers come from \(45 \le n \le 140\), squares from \(32 \le n \le 99\), pentagonal numbers from \(26 \le n \le 81\), hexagonal numbers from \(23 \le n \le 70\), heptagonal numbers from \(21 \le n \le 63\), and octagonal numbers from \(19 \le n \le 58\).
There is one further restriction hidden in the wording of the problem. If a number ends in \(03\), then its suffix is not a genuine two-digit prefix for the next 4-digit number. For that reason the search keeps only candidates whose first two digits and last two digits both lie between 10 and 99.
For any admissible 4-digit value \(x\), define
\[ p(x)=\left\lfloor \frac{x}{100} \right\rfloor, \qquad s(x)=x \bmod 100. \]
A chain \(x_1,x_2,\dots,x_6\) is cyclic exactly when
\[ s(x_i)=p(x_{i+1}) \quad (1 \le i \le 5), \qquad s(x_6)=p(x_1). \]
The type condition is just as important: one term must come from each figurate family. Some values belong to more than one family, so the mathematically correct object is a typed candidate, not just an integer by itself. The search therefore tracks which families have been used, not merely which numeric values have appeared.
Once the admissible lists are generated, the problem becomes a depth-6 backtracking search. At each step two invariants matter: the next candidate must come from an unused family, and its prefix must equal the current required two-digit suffix.
These conditions prune the tree very aggressively. Although there are several dozen candidates in each family, a fixed two-digit prefix usually matches only a small handful of them and often none at all. Most branches therefore die after only a few steps, so the brute-force search becomes practical without any deeper number-theoretic machinery.
A full valid cycle is
\[ 8256 \rightarrow 5625 \rightarrow 2512 \rightarrow 1281 \rightarrow 8128 \rightarrow 2882 \rightarrow 8256. \]
Here the six roles are triangular, square, heptagonal, octagonal, hexagonal, and pentagonal respectively. The two-digit links are easy to verify:
\[ 82\vert 56,\; 56\vert 25,\; 25\vert 12,\; 12\vert 81,\; 81\vert 28,\; 28\vert 82. \]
This example shows exactly what the search is looking for: six typed figurate numbers, each from a different family, whose suffix-prefix relations close into one directed loop.
After five successful links, the recursion has already fixed the order of all six families and all six values. At that point only one condition remains: the suffix of the last chosen number must equal the prefix of the first chosen number. If that equality holds, the chain is a genuine cycle and its sum is the desired answer.
The C++, Python, and Java implementations evaluate each figurate formula for increasing \(n\) until the values exceed 9999. Every 4-digit value is split into a prefix and suffix, and values with a one-digit prefix or suffix are discarded immediately. What remains is a small list of admissible candidates for each of the six families.
The implementation keeps a recursion state consisting of the families already used, the suffix required for the next step, the first prefix in the chain, and the running sum of the chosen values. On the first move there is no suffix restriction yet; after that, every new choice must start with the previous suffix. Because a family can be used at most once, the recursion depth is exactly six.
When six candidates have been chosen, the implementation checks whether the current suffix equals the first prefix. If so, the chain closes and the accumulated sum is stored as the answer. The search then stops immediately, which is justified here because the problem instance has a unique solution up to rotation.
If \(N_3,N_4,N_5,N_6,N_7,N_8\) denote the numbers of admissible 4-digit candidates in the six families, preprocessing costs
\[ O(N_3+N_4+N_5+N_6+N_7+N_8), \]
since each list is generated once.
The search is exponential in the worst case, but the depth is fixed at 6 and the prefix condition makes the practical search tree very small. A loose upper bound is obtained by trying every family order and every candidate in that order, while the real run time is far lower because most partial chains cannot be extended. Memory usage is \(O(N_3+\cdots+N_8)\) for the stored candidate lists plus \(O(6)\) recursion depth.
Gesucht sind sechs verschiedene vierstellige figurierte Zahlen, jeweils eine aus den Familien der Dreiecks-, Quadrat-, Fuenfeck-, Sechseck-, Siebeneck- und Achteckzahlen. Sie muessen einen Zyklus bilden: Die letzten beiden Ziffern jeder Zahl muessen mit den ersten beiden Ziffern der naechsten Zahl uebereinstimmen, und die sechste Zahl muss wieder zur ersten zurueckfuehren.
Die Aufgabe ist klein genug fuer eine vollstaendige Suche, aber nur dann, wenn man die unendlichen Zahlenfolgen zuerst auf eine endliche Kandidatenmenge reduziert und die starke Praefix-Suffix-Bedingung ausnutzt. Genau das tun die Implementierungen: Sie erzeugen alle zulaessigen vierstelligen Werte und suchen dann rekursiv nach einem 6-Zyklus, der jede Familie genau einmal verwendet.
Die sechs benoetigten Familien figurierter Zahlen sind
\[ T_n=\frac{n(n+1)}{2}, \quad S_n=n^2, \quad P_n=\frac{n(3n-1)}{2}, \quad H_n=n(2n-1), \quad \operatorname{Hp}_n=\frac{n(5n-3)}{2}, \quad O_n=n(3n-2). \]
Relevant sind nur Werte im Intervall \(1000 \le x \le 9999\), denn nur vierstellige Zahlen duerfen im Zyklus vorkommen.
Aus den Ungleichungen \(1000 \le x \le 9999\) folgen endliche Indexbereiche: Dreieckszahlen stammen aus \(45 \le n \le 140\), Quadratzahlen aus \(32 \le n \le 99\), Fuenfeckzahlen aus \(26 \le n \le 81\), Sechseckzahlen aus \(23 \le n \le 70\), Siebeneckzahlen aus \(21 \le n \le 63\) und Achteckzahlen aus \(19 \le n \le 58\).
Eine zweite Einschränkung steckt in der Zyklusbedingung. Endet eine Zahl etwa auf \(03\), dann liefert ihr Suffix kein echtes zweistelliges Praefix fuer die naechste vierstellige Zahl. Deshalb behaelt die Suche nur Kandidaten, deren erste beiden und letzte beiden Ziffern jeweils zwischen 10 und 99 liegen.
Fuer jeden zulaessigen vierstelligen Wert \(x\) definieren wir
\[ p(x)=\left\lfloor \frac{x}{100} \right\rfloor, \qquad s(x)=x \bmod 100. \]
Eine Kette \(x_1,x_2,\dots,x_6\) ist genau dann zyklisch, wenn
\[ s(x_i)=p(x_{i+1}) \quad (1 \le i \le 5), \qquad s(x_6)=p(x_1). \]
Ebenso wichtig ist die Typbedingung: Ein Glied muss aus jeder der sechs Familien stammen. Manche Werte gehoeren zu mehr als einer Familie, daher ist das mathematisch richtige Objekt ein typisierter Kandidat und nicht nur eine nackte ganze Zahl. Die Suche verwaltet also, welche Familien bereits benutzt wurden, nicht nur welche Zahlenwerte vorkamen.
Nach dem Erzeugen der Kandidatenlisten bleibt eine Backtracking-Suche der Tiefe 6. In jedem Schritt gelten zwei Invarianten: Die naechste Zahl muss aus einer noch unbenutzten Familie stammen, und ihr Praefix muss mit dem aktuell geforderten zweistelligen Suffix uebereinstimmen.
Diese Bedingungen beschneiden den Suchbaum sehr stark. Zwar enthaelt jede Familie mehrere Dutzend Kandidaten, aber ein festes zweistelliges Praefix passt meist nur zu sehr wenigen davon und oft zu gar keinem. Deshalb enden die meisten Aeste schon nach wenigen Schritten, und die brute-force-Suche bleibt ohne weitere Theorie gut beherrschbar.
Ein vollstaendiger gueltiger Zyklus ist
\[ 8256 \rightarrow 5625 \rightarrow 2512 \rightarrow 1281 \rightarrow 8128 \rightarrow 2882 \rightarrow 8256. \]
Die sechs Rollen sind hier Dreiecks-, Quadrat-, Siebeneck-, Achteck-, Sechseck- und Fuenfeckzahl. Die zweistelligen Verknuepfungen sind direkt sichtbar:
\[ 82\vert 56,\; 56\vert 25,\; 25\vert 12,\; 12\vert 81,\; 81\vert 28,\; 28\vert 82. \]
Genau nach einer solchen Struktur sucht das Programm: sechs typisierte figurierte Zahlen aus verschiedenen Familien, deren Suffix-Praefix-Beziehungen einen geschlossenen gerichteten Kreis bilden.
Nach fuenf erfolgreichen Verknuepfungen hat die Rekursion bereits die Reihenfolge aller sechs Familien und alle sechs Werte festgelegt. Dann fehlt nur noch eine Bedingung: Das Suffix der letzten Zahl muss mit dem Praefix der ersten Zahl uebereinstimmen. Gilt diese Gleichheit, ist aus der Kette ein echter Zyklus geworden, und ihre Summe ist die gesuchte Antwort.
Die C++-, Python- und Java-Implementierungen werten jede figurierte Formel fuer wachsende Werte von \(n\) aus, bis die Zahlen 9999 ueberschreiten. Jeder vierstellige Wert wird in Praefix und Suffix zerlegt; Werte mit einstelligen Anfangs- oder Endblöcken werden sofort verworfen. Uebrig bleiben kleine Listen zulaessiger Kandidaten fuer jede der sechs Familien.
Der Suchzustand besteht aus den bereits benutzten Familien, dem Suffix, mit dem der naechste Wert beginnen muss, dem ersten Praefix der Kette und der laufenden Summe der gewaehlten Zahlen. Beim ersten Schritt gibt es noch keine Praefixvorgabe; danach muss jede neue Wahl mit dem vorherigen Suffix beginnen. Weil jede Familie hoechstens einmal benutzt werden darf, ist die Rekursionstiefe genau 6.
Sobald sechs Kandidaten gewaehlt wurden, prueft die Implementierung, ob das aktuelle Suffix dem ersten Praefix entspricht. Falls ja, schliesst sich die Kette zum Zyklus, und die aufsummierten Werte werden als Antwort gespeichert. Danach wird die Suche sofort beendet, was hier zulaessig ist, weil die Aufgabe eine bis auf Rotation eindeutige Loesung besitzt.
Bezeichnen \(N_3,N_4,N_5,N_6,N_7,N_8\) die Zahlen der zulaessigen vierstelligen Kandidaten in den sechs Familien, dann kostet die Vorverarbeitung
\[ O(N_3+N_4+N_5+N_6+N_7+N_8), \]
da jede Liste genau einmal erzeugt wird.
Die Suche ist im Worst Case exponentiell, aber die Tiefe ist fest auf 6 begrenzt, und die Praefixbedingung macht den tatsaechlichen Suchbaum sehr klein. Eine grobe obere Schranke entsteht, wenn man jede Familienreihenfolge und jeden Kandidaten in dieser Reihenfolge ausprobiert; die reale Laufzeit liegt deutlich darunter, weil sich die meisten Teilketten nicht fortsetzen lassen. Der Speicherbedarf ist \(O(N_3+\cdots+N_8)\) fuer die Kandidatenlisten plus \(O(6)\) fuer den Rekursionsstapel.
Amacimiz, ucgen, kare, besgen, altigen, yedigen ve sekizgen sayi ailelerinin her birinden tam birer tane olmak uzere alti farkli 4 basamakli figuratif sayi bulmaktir. Bu sayilar dongusel olmalidir: her sayinin son iki basamagi, sonraki sayinin ilk iki basamagina esit olmalidir; altinci sayi da tekrar birinciye baglanmalidir.
Problem, dogru aday kumesi uretildiginde tumuyle aranabilecek kadar kucuktur. Ana fikir, sonsuz polygonal dizileri sonlu 4 basamakli aday listelerine indirmek ve iki basamakli on ek-son ek kosulunu sert bir budama araci olarak kullanmaktir. Uygulamalar da tam olarak bunu yapar: Once gecerli adaylari uretir, sonra her aileyi tam bir kez kullanan 6 elemanli bir dongu icin ozyinelemeli arama yapar.
Problemin kullandigi alti figuratif aile su formullerle verilir:
\[ T_n=\frac{n(n+1)}{2}, \quad S_n=n^2, \quad P_n=\frac{n(3n-1)}{2}, \quad H_n=n(2n-1), \quad \operatorname{Hp}_n=\frac{n(5n-3)}{2}, \quad O_n=n(3n-2). \]
Burada yalnizca \(1000 \le x \le 9999\) araligindaki degerler ilgilidir; cunku dongu yalnizca 4 basamakli sayilardan olusabilir.
\(1000 \le x \le 9999\) esitsizlikleri cozulunce sadece sonlu sayida indis kalir: ucgen sayilar icin \(45 \le n \le 140\), kareler icin \(32 \le n \le 99\), besgenler icin \(26 \le n \le 81\), altigenler icin \(23 \le n \le 70\), yedigenler icin \(21 \le n \le 63\), sekizgenler icin \(19 \le n \le 58\).
Metnin icinde gizli bir ikinci filtre daha vardir. Bir sayi \(03\) ile bitiyorsa, bu son blok sonraki 4 basamakli sayi icin gercek bir iki basamakli baslangic olamaz. Bu nedenle arama, ilk iki basamagi da son iki basamagi da 10 ile 99 arasinda olan adaylari tutar.
Her gecerli 4 basamakli \(x\) icin
\[ p(x)=\left\lfloor \frac{x}{100} \right\rfloor, \qquad s(x)=x \bmod 100 \]
tanimlarini yapalim. O zaman \(x_1,x_2,\dots,x_6\) zinciri ancak ve ancak
\[ s(x_i)=p(x_{i+1}) \quad (1 \le i \le 5), \qquad s(x_6)=p(x_1) \]
kosullari saglandiginda donguseldir. Tip kosulu da en az bunun kadar onemlidir: alti terimin her biri farkli bir figuratif aileden gelmelidir. Bazi sayilar birden fazla aileye ait olabilir; dolayisiyla dogru matematiksel nesne yalnizca tamsayi degil, tip etiketi tasiyan adaydir. Arama da bu nedenle kullanilan aileleri izler.
Aday listeleri uretildikten sonra elde kalan sey, derinligi 6 olan bir geri izleme problemidir. Her adimda iki degismez vardir: siradaki sayi kullanilmamis bir aileden gelmeli ve on eki, o anda gereken iki basamakli soneke esit olmalidir.
Bu iki kosul arama agacini sert bicimde budar. Her ailede onlarca aday bulunsa da, sabit bir iki basamakli on eke uyan aday sayisi genellikle cok azdir, hatta cogu zaman sifirdir. Bu yuzden dallarin buyuk kismi birkac adim sonra kapanir ve problem agir bir kuramsal araca gerek duymadan brute-force ile cozulur.
Gecerli bir tam dongu sunlardir:
\[ 8256 \rightarrow 5625 \rightarrow 2512 \rightarrow 1281 \rightarrow 8128 \rightarrow 2882 \rightarrow 8256. \]
Burada roller sirasiyla ucgen, kare, yedigen, sekizgen, altigen ve besgen sayilardir. Iki basamakli baglantilar aciktir:
\[ 82\vert 56,\; 56\vert 25,\; 25\vert 12,\; 12\vert 81,\; 81\vert 28,\; 28\vert 82. \]
Aramanin hedefledigi yapi tam olarak budur: her biri farkli bir aileye ait alti tipli figuratif sayi, ve bunlarin son ek-on ek iliskileri tek bir kapali dongu olusturur.
Bes basarili gecisten sonra ozyineleme zaten alti ailenin sirasini ve alti degerin tamamini belirlemis olur. Geriye tek bir test kalir: son secilen sayinin son eki, ilk secilen sayinin on ekine esit mi? Esitse zincir kapaniyordur ve sayilarin toplami istenen cevaptir.
C++, Python ve Java uygulamalari her figuratif formulu artan \(n\) degerleri icin hesaplar ve deger 9999'u astiginda durur. Her 4 basamakli deger on ek ve son eke ayrilir; basi veya sonu tek basamakli olanlar hemen elenir. Boylece her aile icin kucuk bir gecerli aday listesi elde edilir.
Uygulama, kullanilmis aileleri, bir sonraki adimda gerekli soneki, zincirin ilk on ekini ve secilen sayilarin kismi toplamini tutar. Ilk hamlede henuz bir son ek zorunlulugu yoktur; bundan sonra her yeni secim onceki sayinin son ekiyle baslamak zorundadir. Her aile en fazla bir kez kullanildigi icin ozyineleme derinligi tam 6'dır.
Alti aday secildiginde uygulama, mevcut sonekin ilk on eke esit olup olmadigini kontrol eder. Esitlik varsa zincir kapanmistir ve biriken toplam cevap olarak kaydedilir. Problemde cozum donmeye kadar tek oldugu icin arama bu noktada hemen durdurulur.
\(N_3,N_4,N_5,N_6,N_7,N_8\) her ailedeki gecerli 4 basamakli aday sayilarini gostersin. O zaman on isleme maliyeti
\[ O(N_3+N_4+N_5+N_6+N_7+N_8) \]
olur; cunku her liste bir kez uretilir.
Arama en kotu durumda usseldir, fakat derinlik sabit olarak 6'dır ve on ek kosulu pratikte arama agacini cok kucultur. Kaba bir ust sinir, tum aile siralamalarini ve her siralamadaki tum aday secimlerini denemektir; gercek calisma suresi bundan cok daha dusuktur, cunku parcali zincirlerin buyuk cogu devam edemez. Bellek kullanimi aday listeleri icin \(O(N_3+\cdots+N_8)\), ozyineleme yigini icin ise \(O(6)\)'dir.
Se buscan seis numeros figurados distintos de 4 cifras, uno de cada una de las familias triangular, cuadrada, pentagonal, hexagonal, heptagonal y octagonal. Deben formar un ciclo: las dos ultimas cifras de cada numero deben coincidir con las dos primeras del siguiente, y el sexto numero debe volver a enlazar con el primero.
El problema es lo bastante pequeno como para resolverse por busqueda exhaustiva, pero solo despues de convertir las sucesiones infinitas en un conjunto finito de candidatos y de aprovechar la fuerte restriccion prefijo-sufijo. Por eso las implementaciones generan primero todos los valores admisibles de 4 cifras y despues realizan una busqueda recursiva de un ciclo de longitud 6 que use cada familia exactamente una vez.
Las seis familias figuradas del problema son
\[ T_n=\frac{n(n+1)}{2}, \quad S_n=n^2, \quad P_n=\frac{n(3n-1)}{2}, \quad H_n=n(2n-1), \quad \operatorname{Hp}_n=\frac{n(5n-3)}{2}, \quad O_n=n(3n-2). \]
Solo interesan los valores en el intervalo \(1000 \le x \le 9999\), porque el ciclo debe estar formado por numeros de 4 cifras.
Al resolver \(1000 \le x \le 9999\) para cada formula se obtiene que solo importan rangos finitos de indices: los triangulares vienen de \(45 \le n \le 140\), los cuadrados de \(32 \le n \le 99\), los pentagonales de \(26 \le n \le 81\), los hexagonales de \(23 \le n \le 70\), los heptagonales de \(21 \le n \le 63\) y los octagonales de \(19 \le n \le 58\).
Hay una segunda restriccion implicita en el enunciado. Si un numero termina en \(03\), ese sufijo no puede ser un prefijo valido de dos cifras para otro numero de 4 cifras. Por eso la busqueda conserva solo candidatos cuyas dos primeras y dos ultimas cifras esten ambas entre 10 y 99.
Para cualquier valor admisible \(x\), definimos
\[ p(x)=\left\lfloor \frac{x}{100} \right\rfloor, \qquad s(x)=x \bmod 100. \]
Una cadena \(x_1,x_2,\dots,x_6\) es ciclica exactamente cuando
\[ s(x_i)=p(x_{i+1}) \quad (1 \le i \le 5), \qquad s(x_6)=p(x_1). \]
La condicion de tipo es igual de importante: debe aparecer exactamente un termino de cada familia. Algunos valores pertenecen a mas de una familia, asi que el objeto matematico correcto es un candidato tipado, no solo un entero aislado. La busqueda, por tanto, controla que familias ya se usaron, no solamente que valores numericos aparecieron.
Una vez construidas las listas admisibles, el problema se reduce a una busqueda con retroceso de profundidad 6. En cada nivel hay dos invariantes: el siguiente numero debe proceder de una familia aun no usada, y su prefijo debe coincidir con el sufijo exigido por el paso anterior.
Esas dos condiciones podan el arbol de manera muy agresiva. Aunque cada familia contiene varias decenas de candidatos, un prefijo fijo de dos cifras suele coincidir con muy pocos de ellos y a menudo con ninguno. Por eso la mayoria de las ramas mueren tras pocos pasos y la exploracion exhaustiva resulta totalmente viable.
Un ciclo valido completo es
\[ 8256 \rightarrow 5625 \rightarrow 2512 \rightarrow 1281 \rightarrow 8128 \rightarrow 2882 \rightarrow 8256. \]
Aqui los seis papeles son triangular, cuadrado, heptagonal, octagonal, hexagonal y pentagonal, en ese orden. Las uniones de dos cifras se comprueban enseguida:
\[ 82\vert 56,\; 56\vert 25,\; 25\vert 12,\; 12\vert 81,\; 81\vert 28,\; 28\vert 82. \]
Ese ejemplo muestra exactamente lo que persigue la busqueda: seis numeros figurados tipados, cada uno de una familia diferente, cuyas relaciones sufijo-prefijo se cierran en un unico bucle.
Despues de cinco enlaces correctos, la recursion ya ha fijado el orden de las seis familias y los seis valores concretos. Solo queda una comprobacion: el sufijo del ultimo numero debe coincidir con el prefijo del primero. Si eso ocurre, la cadena ya es un ciclo autentico y su suma es la respuesta buscada.
Las implementaciones en C++, Python y Java evalúan cada formula figurada para valores crecientes de \(n\) hasta que el resultado supera 9999. Cada valor de 4 cifras se separa en prefijo y sufijo, y se descartan de inmediato los que tienen una parte inicial o final de una sola cifra. Lo que queda es una lista pequena de candidatos admisibles para cada una de las seis familias.
La implementacion mantiene un estado con las familias ya utilizadas, el sufijo que debe satisfacer el siguiente numero, el primer prefijo de la cadena y la suma parcial de los valores elegidos. En el primer paso todavia no existe ninguna restriccion de sufijo; despues, cada nueva eleccion debe empezar con el sufijo anterior. Como cada familia puede usarse a lo sumo una vez, la profundidad de la recursion es exactamente 6.
Cuando ya se han elegido seis candidatos, la implementacion compara el sufijo actual con el primer prefijo. Si son iguales, la cadena se cierra y la suma acumulada se guarda como respuesta. La exploracion termina en ese instante, lo cual es correcto aqui porque la instancia del problema tiene una solucion unica salvo rotacion.
Si \(N_3,N_4,N_5,N_6,N_7,N_8\) representan los numeros de candidatos admisibles de 4 cifras en las seis familias, la fase de preprocesamiento cuesta
\[ O(N_3+N_4+N_5+N_6+N_7+N_8), \]
porque cada lista se genera una sola vez.
La busqueda es exponencial en el peor caso, pero la profundidad esta fijada en 6 y la condicion de prefijo reduce mucho el arbol real. Una cota muy amplia consiste en probar todos los ordenes posibles de las familias y todos los candidatos en esos ordenes; en la practica el tiempo es mucho menor porque casi todas las cadenas parciales no pueden prolongarse. El uso de memoria es \(O(N_3+\cdots+N_8)\) para almacenar las listas y \(O(6)\) para la pila recursiva.
题目要求找出六个不同的四位数形数，分别来自三角数、平方数、五边形数、六边形数、七边形数和八边形数六个家族。它们必须构成一个闭环：每个数的后两位必须等于下一个数的前两位，第六个数还要重新接回第一个数。
这道题的规模其实不大，但前提是先把无限的形数序列缩成有限的候选集合，再充分利用“前两位/后两位匹配”这个强约束。三种实现的思路完全一致：先生成所有可参与循环的四位候选，再通过递归搜索找出一个恰好使用六种家族各一次的长度为 6 的循环。
题目中的六类形数分别是
\[ T_n=\frac{n(n+1)}{2}, \quad S_n=n^2, \quad P_n=\frac{n(3n-1)}{2}, \quad H_n=n(2n-1), \quad \operatorname{Hp}_n=\frac{n(5n-3)}{2}, \quad O_n=n(3n-2). \]
我们只关心满足 \(1000 \le x \le 9999\) 的值，因为题目明确要求使用四位数。
把 \(1000 \le x \le 9999\) 分别代入六个公式，可以得到有限的指标范围：三角数对应 \(45 \le n \le 140\)，平方数对应 \(32 \le n \le 99\)，五边形数对应 \(26 \le n \le 81\)，六边形数对应 \(23 \le n \le 70\)，七边形数对应 \(21 \le n \le 63\)，八边形数对应 \(19 \le n \le 58\)。因此真正需要检查的候选非常有限。
题目里还有一个容易忽略的约束。如果一个四位数以 \(03\) 结尾，那么它的后两位并不能作为下一个四位数的合法前两位。所以实现不仅要求数值是四位数，还要求它的前两位和后两位都落在 10 到 99 之间。这个过滤步骤直接剔除了很多不可能出现在环中的项。
对任意一个合法候选 \(x\)，定义
\[ p(x)=\left\lfloor \frac{x}{100} \right\rfloor, \qquad s(x)=x \bmod 100. \]
那么一个长度为 6 的序列 \(x_1,x_2,\dots,x_6\) 成为题目所需的循环，当且仅当
\[ s(x_i)=p(x_{i+1}) \quad (1 \le i \le 5), \qquad s(x_6)=p(x_1). \]
除了首尾数字匹配之外，还必须保证六个项分别来自六种不同的形数家族。有些整数可能同时属于两个家族，例如某个数既是三角数又是六边形数。在这种情况下，数学上真正被选择的对象不是“这个整数本身”，而是“带有家族标签的候选项”。因此搜索时必须记录哪些家族已经被使用，而不仅仅是记录出现过哪些数值。
一旦候选列表生成完毕，问题就变成一个深度固定为 6 的回溯搜索。每一步都遵守两个不变量：下一项必须来自尚未使用的家族，而且它的前两位必须等于当前要求的后两位。
这两个条件会极大地压缩搜索树。虽然每个家族里都有几十个四位候选，但当你固定了一个两位前缀以后，真正匹配的数字通常只有极少几个，很多时候甚至一个都没有。于是绝大多数分支在很浅的层数就会终止，原本看起来像组合爆炸的问题，实际上就变成了一个很小的递归枚举。
满足条件的完整循环可以写成
\[ 8256 \rightarrow 5625 \rightarrow 2512 \rightarrow 1281 \rightarrow 8128 \rightarrow 2882 \rightarrow 8256. \]
在这个顺序里，它们分别扮演三角数、平方数、七边形数、八边形数、六边形数和五边形数的角色。把每个数切成前两位和后两位，就能直接看到闭环结构：
\[ 82\vert 56,\; 56\vert 25,\; 25\vert 12,\; 12\vert 81,\; 81\vert 28,\; 28\vert 82. \]
这正是程序在寻找的对象：六个带类型的形数，每种家族恰好出现一次，并且后缀与前缀的关系最终闭合成一个环。
当递归已经成功接出前五条连接时，六个家族的顺序和六个具体的数其实都已经确定了。此时只剩最后一个条件需要检查：最后一个数的后两位是否等于第一个数的前两位。如果相等，这条链就不再只是“可延伸的路径”，而是真正满足题意的循环，它们的和就是要求的答案。
C++、Python 和 Java 实现都会对每一种形数公式从小到大枚举 \(n\)，直到数值超过 9999 为止。每得到一个四位数，就把它拆成前两位和后两位；如果其中任何一部分不是合法的两位数，就立刻丢弃。保留下来的就是每个家族对应的可用候选列表。
实现维护的递归状态包括：哪些家族已经使用过、下一步必须匹配的后缀、整条链起点的前缀，以及当前已经选中数字的和。第一步还没有后缀约束；从第二步开始，每个新候选都必须以前一步的后两位开头。由于每个家族最多只能用一次，所以递归深度固定就是 6。
当已经选满 6 个候选之后，实现会比较“当前后缀”和“起始前缀”是否相等。若相等，说明路径已经首尾相接，形成完整循环，于是把累计和记为答案并立即停止搜索。对这道题这样做是合理的，因为题目本身保证了解在旋转意义下是唯一的。
设 \(N_3,N_4,N_5,N_6,N_7,N_8\) 分别表示六个家族中满足条件的四位候选数量，那么预处理开销为
\[ O(N_3+N_4+N_5+N_6+N_7+N_8), \]
因为每个列表只生成一次。
回溯部分在最坏情形下仍然是指数级的，但这里的深度固定为 6，而且前缀匹配条件会把实际搜索树压得很小。一个非常宽松的上界，是尝试所有家族顺序和对应顺序下的所有候选；真实运行时间远小于这个估计，因为几乎所有部分链都无法继续延伸。空间复杂度为 \(O(N_3+\cdots+N_8)\) 的候选存储，再加上 \(O(6)\) 的递归栈深度。
Нужно найти шесть различных четырехзначных фигурных чисел, по одному из семейств треугольных, квадратных, пятиугольных, шестиугольных, семиугольных и восьмиугольных чисел. Они должны образовать цикл: последние две цифры каждого числа должны совпадать с первыми двумя цифрами следующего, а шестое число должно снова вести к первому.
Задача допускает полный перебор, но только после того, как бесконечные последовательности будут сведены к конечным спискам кандидатов, а условие совпадения префикса и суффикса будет использовано как сильное отсечение. Именно так и устроены реализации: сначала строятся все допустимые четырехзначные значения, а затем рекурсивно ищется цикл длины 6, использующий каждое семейство ровно один раз.
Шесть фигурных семейств из условия задаются формулами
\[ T_n=\frac{n(n+1)}{2}, \quad S_n=n^2, \quad P_n=\frac{n(3n-1)}{2}, \quad H_n=n(2n-1), \quad \operatorname{Hp}_n=\frac{n(5n-3)}{2}, \quad O_n=n(3n-2). \]
Нас интересуют только значения из диапазона \(1000 \le x \le 9999\), потому что в цикл могут входить только четырехзначные числа.
Решая неравенства \(1000 \le x \le 9999\) для каждой формулы, получаем конечные диапазоны индексов: для треугольных чисел это \(45 \le n \le 140\), для квадратов \(32 \le n \le 99\), для пятиугольных \(26 \le n \le 81\), для шестиугольных \(23 \le n \le 70\), для семиугольных \(21 \le n \le 63\), для восьмиугольных \(19 \le n \le 58\).
Есть и еще одно важное ограничение. Если число оканчивается, например, на \(03\), то такой суффикс не может служить корректным двузначным префиксом следующего четырехзначного числа. Поэтому поиск оставляет только те кандидаты, у которых и первые две, и последние две цифры лежат в диапазоне от 10 до 99.
Для любого допустимого значения \(x\) введем обозначения
\[ p(x)=\left\lfloor \frac{x}{100} \right\rfloor, \qquad s(x)=x \bmod 100. \]
Цепочка \(x_1,x_2,\dots,x_6\) является циклической тогда и только тогда, когда выполнено
\[ s(x_i)=p(x_{i+1}) \quad (1 \le i \le 5), \qquad s(x_6)=p(x_1). \]
Не менее важно и условие по типам: в ответе должно присутствовать ровно по одному числу из каждого семейства. Некоторые значения встречаются сразу в нескольких семействах, поэтому математически правильный объект здесь не просто целое число, а типизированный кандидат. Соответственно, поиск отслеживает именно использованные семейства, а не только встречавшиеся числовые значения.
После построения списков кандидатов задача сводится к поиску с возвратом глубины 6. На каждом шаге действуют два инварианта: следующее число должно принадлежать еще не использованному семейству, а его префикс обязан совпадать с текущим требуемым суффиксом.
Эти условия очень сильно сокращают дерево перебора. В каждом семействе есть лишь несколько десятков допустимых кандидатов, и для фиксированного двузначного префикса обычно подходят только единицы, а часто не подходит ни один. Поэтому большинство ветвей обрывается уже через пару шагов, и полный перебор оказывается вполне практичным.
Корректный полный цикл имеет вид
\[ 8256 \rightarrow 5625 \rightarrow 2512 \rightarrow 1281 \rightarrow 8128 \rightarrow 2882 \rightarrow 8256. \]
В этом порядке числа играют роли треугольного, квадратного, семиугольного, восьмиугольного, шестиугольного и пятиугольного соответственно. Двузначные связи проверяются напрямую:
\[ 82\vert 56,\; 56\vert 25,\; 25\vert 12,\; 12\vert 81,\; 81\vert 28,\; 28\vert 82. \]
Именно такую структуру и ищет алгоритм: шесть типизированных фигурных чисел из разных семейств, у которых отношения «суффикс-префикс» замыкаются в один цикл.
После пяти успешных переходов рекурсия уже зафиксировала порядок всех шести семейств и сами шесть значений. Остается проверить только одно: совпадает ли суффикс последнего числа с префиксом первого. Если да, то цепочка действительно замкнулась, и сумма ее элементов является искомым ответом.
Реализации на C++, Python и Java вычисляют каждую фигурную формулу для возрастающих \(n\), пока значение не превысит 9999. Каждый четырехзначный результат разбивается на префикс и суффикс, а значения с однозначным начальным или конечным блоком сразу отбрасываются. После этого для каждого из шести семейств остается небольшой список допустимых кандидатов.
Поиск хранит набор уже использованных семейств, суффикс, которому должен соответствовать следующий шаг, первый префикс всей цепочки и текущую сумму выбранных значений. На самом первом шаге ограничение на префикс отсутствует; затем каждое новое число обязано начинаться с предыдущего суффикса. Поскольку каждое семейство можно использовать не более одного раза, глубина рекурсии всегда равна 6.
Когда выбрано шесть кандидатов, реализация сравнивает текущий суффикс с первым префиксом. Если они совпадают, цепочка замыкается, накопленная сумма сохраняется как ответ, и дальнейший поиск прекращается. Здесь это корректно, потому что решение задачи единственно с точностью до циклического сдвига.
Пусть \(N_3,N_4,N_5,N_6,N_7,N_8\) обозначают количества допустимых четырехзначных кандидатов в шести семействах. Тогда предварительная обработка стоит
\[ O(N_3+N_4+N_5+N_6+N_7+N_8), \]
поскольку каждый список строится один раз.
Худший случай для поиска экспоненциален, но глубина здесь фиксирована и равна 6, а условие совпадения префикса делает реальное дерево перебора очень маленьким. Грубая верхняя оценка получается, если разрешить все порядки семейств и все выборы кандидатов в этих порядках; фактическое время намного меньше, потому что почти все частичные цепочки не продолжаются. Память составляет \(O(N_3+\cdots+N_8)\) для хранения списков кандидатов и \(O(6)\) для рекурсивного стека.
المطلوب هو العثور على ستة اعداد شكلية مختلفة مكوّنة من اربع خانات، واحد من كل عائلة من العائلات التالية: المثلثية، والمربعة، والخماسية، والسداسية، والسباعية، والمثمنة. ويجب ان تكوّن هذه الاعداد دورة مغلقة: آخر رقمين من كل عدد يساويان اول رقمين من العدد التالي، والعدد السادس يجب ان يعود فيربط من جديد بالعدد الاول.
هذه المسألة صغيرة بما يكفي لتُحل بالبحث الكامل، لكن ذلك لا يصبح عملياً إلا بعد تحويل المتتاليات الشكلية اللانهائية إلى مجموعة محدودة من المرشحين، ثم استغلال شرط تطابق السابقة واللاحقة على خانتين بوصفه اداة تقليم قوية. لذلك تقوم التطبيقات اولاً بتوليد جميع القيم الرباعية الصالحة، ثم تبحث عودياً عن دورة طولها 6 تستخدم كل عائلة مرة واحدة بالضبط.
العائلات الشكلية الست المستخدمة في المسألة هي
\[ T_n=\frac{n(n+1)}{2}, \quad S_n=n^2, \quad P_n=\frac{n(3n-1)}{2}, \quad H_n=n(2n-1), \quad \operatorname{Hp}_n=\frac{n(5n-3)}{2}, \quad O_n=n(3n-2). \]
ونحن لا نهتم إلا بالقيم التي تحقق \(1000 \le x \le 9999\)، لأن عناصر الدورة يجب ان تكون اعداداً من اربع خانات.
عند حل المتباينات \(1000 \le x \le 9999\) لكل صيغة، نحصل على مجالات منتهية للمؤشرات: الاعداد المثلثية تأتي من \(45 \le n \le 140\)، والمربعة من \(32 \le n \le 99\)، والخماسية من \(26 \le n \le 81\)، والسداسية من \(23 \le n \le 70\)، والسباعية من \(21 \le n \le 63\)، والمثمنة من \(19 \le n \le 58\).
وهناك قيد ثانٍ مهم يختبئ داخل صياغة المسألة. فإذا انتهى عدد ما بـ \(03\) مثلاً، فإن هذه اللاحقة لا تصلح لتكون سابقة صحيحة من رقمين لعدد رباعي تالٍ. لذلك تحتفظ الخوارزمية فقط بالمرشحين الذين تكون اول خانتين وآخر خانتين فيهم جميعاً بين 10 و99.
لكل قيمة صالحة \(x\) نعرّف
\[ p(x)=\left\lfloor \frac{x}{100} \right\rfloor, \qquad s(x)=x \bmod 100. \]
وعندئذ تكون السلسلة \(x_1,x_2,\dots,x_6\) دورية تماماً اذا وفقط اذا تحقق
\[ s(x_i)=p(x_{i+1}) \quad (1 \le i \le 5), \qquad s(x_6)=p(x_1). \]
لكن شرط الانواع لا يقل اهمية عن ذلك: يجب ان يأتي حد واحد من كل عائلة شكلية. وبعض القيم قد تنتمي الى اكثر من عائلة، ولذلك فالكائن الرياضي الصحيح هنا ليس مجرد عدد صحيح منفرد، بل مرشح مقيّد بالنوع. ولهذا السبب تتعقب الخوارزمية العائلات التي استُخدمت، لا مجرد القيم الرقمية التي ظهرت.
بعد بناء قوائم المرشحين، تتحول المسألة إلى بحث تراجعي بعمق ثابت يساوي 6. وفي كل خطوة يوجد ثابتان حاكمان: يجب ان يأتي العدد التالي من عائلة لم تُستخدم بعد، ويجب ان يساوي بادئته الرقمين المطلوبين من لاحقة الخطوة السابقة.
هذان الشرطان يختزلان شجرة البحث بقوة شديدة. فمع ان كل عائلة تحتوي على عشرات من المرشحين، فإن سابقة معينة من رقمين لا تطابق عادة إلا عدداً قليلاً جداً منهم، وكثيراً ما لا تطابق اياً منهم. ولذلك تموت معظم الفروع بعد خطوات قليلة، ويصبح البحث الشامل عملياً من دون الحاجة إلى أدوات نظرية اعمق.
يمكن كتابة دورة صحيحة كاملة بالشكل
\[ 8256 \rightarrow 5625 \rightarrow 2512 \rightarrow 1281 \rightarrow 8128 \rightarrow 2882 \rightarrow 8256. \]
وفي هذا الترتيب تؤدي القيم ادوار العدد المثلثي، ثم المربع، ثم السباعي، ثم المثمن، ثم السداسي، ثم الخماسي. وروابط الرقمين واضحة مباشرة:
\[ 82\vert 56,\; 56\vert 25,\; 25\vert 12,\; 12\vert 81,\; 81\vert 28,\; 28\vert 82. \]
هذا يوضح بدقة ما يبحث عنه البرنامج: ستة اعداد شكلية مقيّدة بالنوع، كل واحد منها من عائلة مختلفة، وتغلق علاقات السابقة واللاحقة بينها دورة واحدة كاملة.
بعد نجاح خمس وصلات، تكون العودية قد حدّدت بالفعل ترتيب العائلات الست والقيم الست نفسها. عندئذ لا يبقى إلا اختبار واحد: هل لاحقة العدد الاخير تساوي سابقة العدد الاول؟ إذا تحقق ذلك، لم تعد السلسلة مجرد مسار قابل للتمديد، بل أصبحت الدورة المطلوبة، ويكون مجموع عناصرها هو الجواب.
تقوم تطبيقات C++ وPython وJava بحساب كل صيغة شكلية لقيم متزايدة من \(n\) حتى تتجاوز النتائج 9999. وكل قيمة رباعية تُقسّم إلى سابقة ولاحقة، ثم تُستبعد مباشرة القيم التي تحتوي على جزء ابتدائي او نهائي من خانة واحدة فقط. وما يبقى هو قائمة صغيرة من المرشحين المسموح بهم لكل واحدة من العائلات الست.
تحمل الشيفرة حالة عودية تتكون من العائلات التي استُخدمت بالفعل، واللاحقة التي يجب ان يطابقها العدد التالي، والسابقة الاولى في السلسلة، والمجموع الجاري للقيم المختارة. في الخطوة الاولى لا يوجد قيد لاحقة بعد؛ وبعد ذلك يجب ان يبدأ كل اختيار جديد باللاحقة السابقة. وبما ان كل عائلة تُستخدم مرة واحدة كحد اقصى، فإن عمق العودية يساوي 6 تماماً.
عندما يتم اختيار ستة مرشحين، تقارن الشيفرة بين اللاحقة الحالية والسابقة الاولى. فإذا تساوتا، انغلقت السلسلة وتُحفظ القيمة المجمعة بوصفها الجواب. ثم يتوقف البحث مباشرة، وهذا صحيح هنا لأن المسألة تضمن وجود حل وحيد حتى مع اعتبار الدوران.
إذا رمزنا بـ \(N_3,N_4,N_5,N_6,N_7,N_8\) إلى اعداد المرشحين الرباعيين الصالحين في العائلات الست، فإن كلفة المعالجة المسبقة هي
\[ O(N_3+N_4+N_5+N_6+N_7+N_8), \]
لأن كل قائمة تُبنى مرة واحدة فقط.
اما البحث نفسه فهو أسي في اسوأ الاحوال، لكن العمق ثابت ويساوي 6، كما أن شرط تطابق السابقة يجعل شجرة البحث الفعلية صغيرة جداً. ويمكن وضع حد اعلى خشن بتجربة جميع ترتيبات العائلات وجميع المرشحين ضمن تلك الترتيبات، لكن الزمن الحقيقي اقل بكثير لأن معظم السلاسل الجزئية لا يمكن تمديدها. ويبلغ استهلاك الذاكرة \(O(N_3+\cdots+N_8)\) لتخزين القوائم، بالإضافة إلى \(O(6)\) لمكدس الاستدعاء العودي.