Triangular, pentagonal, and hexagonal numbers are given by \(T_n=\frac{n(n+1)}{2}\), \(P_n=\frac{n(3n-1)}{2}\), and \(H_n=n(2n-1)\). The problem states that \(40755\) is simultaneously triangular, pentagonal, and hexagonal, and asks for the next number with the same property.
The implementations do not search all three families independently. They exploit a structural identity between triangular and hexagonal numbers, then scan only hexagonal candidates and apply an exact pentagonal test.
The whole strategy is to turn a three-condition search into a one-dimensional scan with a precise arithmetic predicate.
The first reduction is immediate:
$$H_n=n(2n-1)=\frac{(2n-1)(2n)}{2}=T_{2n-1}.$$
So every hexagonal number is automatically triangular. That means a number is triangular, pentagonal, and hexagonal exactly when it is both hexagonal and pentagonal. The triangular test disappears entirely.
This is the key invariant used by the code: once a candidate is generated in hexagonal form, one of the three required properties is already guaranteed.
To test whether a number \(x\) is pentagonal, start from
$$x=P_k=\frac{k(3k-1)}{2}.$$
Multiply by \(24\) and add \(1\):
$$24x+1=12k(3k-1)+1=36k^2-12k+1=(6k-1)^2.$$
Therefore \(x\) is pentagonal if and only if \(24x+1\) is a perfect square and the corresponding index
$$k=\frac{1+\sqrt{24x+1}}{6}$$
is an integer. This is exactly the arithmetic condition used in the three implementations.
The important detail is that the square root alone is not trusted as a final answer. After computing a floating-point square root and rounding the implied index, the implementation substitutes that integer back into \(\frac{k(3k-1)}{2}\) and checks whether it reconstructs \(x\) exactly.
The known common value in the statement is
$$H_{143}=143(2\cdot 143-1)=143\cdot 285=40755.$$
Because the task asks for the next such number, the scan begins with the next hexagonal index, \(n=144\).
The hexagonal sequence is strictly increasing for positive \(n\). In fact,
$$H_{n+1}-H_n=(n+1)(2n+1)-n(2n-1)=4n+1 \gt 0.$$
So once the loop moves past \(n=143\), the first candidate that also passes the pentagonal test must be the next desired number.
The given example \(40755\) is a good checkpoint. Since
$$24\cdot 40755+1=978121=989^2,$$
we get
$$k=\frac{1+989}{6}=165,$$
so \(40755=P_{165}\). Combined with \(40755=H_{143}\) and \(H_n=T_{2n-1}\), it is indeed a member of all three families.
The very next hexagonal candidate is
$$H_{144}=144(287)=41328.$$
For this value, \(24\cdot 41328+1=991873\), which is not a perfect square, so the candidate fails immediately. This is exactly the kind of fast rejection that makes the linear scan practical.
The C++, Python, and Java implementations iterate the hexagonal index upward from \(144\). For each step they compute the current candidate as \(n(2n-1)\). No triangular check is performed, because the identity \(H_n=T_{2n-1}\) has already removed that part of the problem.
For each candidate \(x\), the implementation forms the discriminant-like value \(1+24x\), takes its square root, converts the implied pentagonal index to the nearest integer, and then verifies the result exactly by rebuilding \(\frac{k(3k-1)}{2}\). That last exact reconstruction is what makes the test robust even though the intermediate square root is computed in floating point.
Because the candidates are examined in increasing hexagonal index, the first passing value is automatically the next common number after \(40755\). The C++ and Java implementations also include small checkpoint tests before the full search: the known value \(40755\) must pass the pentagonal test, while \(40756\) must fail.
Each loop iteration performs a constant amount of arithmetic and one square-root computation, so the cost per candidate is \(O(1)\). If the next solution occurs at hexagonal index \(N\), the total running time is \(O(N-143)\).
Memory usage is \(O(1)\), since the algorithm stores only a few numeric variables and does not build tables, arrays, or recursion stacks. The main optimization is conceptual rather than structural: the search is efficient because it generates only hexagonal numbers and uses a direct arithmetic test for pentagonality.
Dreiecks-, Fuenfecks- und Sechseckzahlen sind durch \(T_n=\frac{n(n+1)}{2}\), \(P_n=\frac{n(3n-1)}{2}\) und \(H_n=n(2n-1)\) definiert. Die Aufgabenstellung sagt, dass \(40755\) gleichzeitig dreieckig, fuenfeckig und sechseckig ist, und fragt nach der naechsten Zahl mit derselben Eigenschaft.
Die Implementierungen durchsuchen nicht drei Zahlenfolgen gleichzeitig. Stattdessen nutzen sie eine feste Identitaet zwischen Dreiecks- und Sechseckzahlen und pruefen danach nur noch, ob ein hexagonaler Kandidat auch pentagonal ist.
Die gesamte Methode reduziert die Dreifachbedingung auf einen eindimensionalen Suchlauf mit einem exakten Zahltest.
Die zentrale Umformung lautet
$$H_n=n(2n-1)=\frac{(2n-1)(2n)}{2}=T_{2n-1}.$$
Damit ist jede Sechseckzahl automatisch auch dreieckig. Gesucht sind also genau die Zahlen, die sowohl sechseckig als auch fuenfeckig sind. Eine separate Dreieckspruefung ist ueberfluessig.
Genau diese Invariante steckt in den Programmen: Sobald ein Wert in der Form \(H_n\) erzeugt wurde, ist eine der drei Eigenschaften bereits gesichert.
Um zu pruefen, ob eine Zahl \(x\) pentagonal ist, beginnt man mit
$$x=P_k=\frac{k(3k-1)}{2}.$$
Multipliziert man mit \(24\) und addiert \(1\), erhaelt man
$$24x+1=12k(3k-1)+1=36k^2-12k+1=(6k-1)^2.$$
Daraus folgt: \(x\) ist genau dann pentagonal, wenn \(24x+1\) ein perfektes Quadrat ist und
$$k=\frac{1+\sqrt{24x+1}}{6}$$
eine ganze Zahl ist. Das ist exakt die Bedingung, die in allen drei Sprachen verwendet wird.
Wichtig ist dabei die letzte Kontrolle: Die Quadratwurzel wird zwar im Gleitkomma berechnet, aber das Ergebnis wird nicht blind vertraut. Nach dem Runden des vermuteten Index wird \(\frac{k(3k-1)}{2}\) noch einmal ganzzahlig aufgebaut und exakt mit \(x\) verglichen.
Der bekannte gemeinsame Wert aus der Aufgabenstellung ist
$$H_{143}=143(2\cdot 143-1)=143\cdot 285=40755.$$
Da die Aufgabe nach der naechsten solchen Zahl fragt, startet die Schleife beim naechsten hexagonalen Index \(n=144\).
Die Folge \(H_n\) ist fuer positive \(n\) streng wachsend. Genauer gilt
$$H_{n+1}-H_n=(n+1)(2n+1)-n(2n-1)=4n+1 \gt 0.$$
Sobald die Suche also ueber \(n=143\) hinausgeht, ist der erste Treffer automatisch die naechste gesuchte Zahl.
Die bekannte Zahl \(40755\) ist ein guter Kontrollwert. Es gilt
$$24\cdot 40755+1=978121=989^2,$$
also
$$k=\frac{1+989}{6}=165,$$
und damit \(40755=P_{165}\). Zusammen mit \(40755=H_{143}\) und \(H_n=T_{2n-1}\) ist die Dreifachzugehoerigkeit bestaetigt.
Der naechste hexagonale Kandidat ist
$$H_{144}=144(287)=41328.$$
Hier ist \(24\cdot 41328+1=991873\) kein perfektes Quadrat. Der Kandidat scheidet also sofort aus. Genau diese schnelle Verwerfung macht die lineare Suche praktisch.
Die Implementierungen in C++, Python und Java erhoehen den hexagonalen Index beginnend bei \(144\). In jedem Schritt wird der aktuelle Kandidat als \(n(2n-1)\) berechnet. Eine Dreieckspruefung gibt es nicht, weil die Identitaet \(H_n=T_{2n-1}\) diesen Teil bereits erledigt hat.
Fuer jeden Kandidaten \(x\) berechnet die Implementierung den Wert \(1+24x\), zieht die Quadratwurzel, rundet den daraus folgenden Pentagonalindex und prueft danach exakt, ob \(\frac{k(3k-1)}{2}=x\) gilt. Gerade diese exakte Rueckpruefung verhindert, dass eine kleine Gleitkommaabweichung zu einem falschen Treffer fuehrt.
Da die Kandidaten in aufsteigender hexagonaler Reihenfolge betrachtet werden, ist der erste erfolgreiche Test automatisch die gesuchte naechste Zahl nach \(40755\). Die C++- und Java-Versionen fuehren vor der eigentlichen Suche zusaetzlich kleine Kontrolltests aus: \(40755\) muss den Pentagonaltest bestehen, \(40756\) dagegen nicht.
Jede Schleifeniteration braucht nur konstante arithmetische Arbeit und eine Quadratwurzel, also \(O(1)\) Zeit pro Kandidat. Liegt die naechste Loesung beim hexagonalen Index \(N\), dann betraegt die Gesamtlaufzeit \(O(N-143)\).
Der Speicherverbrauch ist \(O(1)\), weil nur einige wenige numerische Variablen benoetigt werden. Es gibt keine Tabellen, keine Rekursion und keine grossen Datenstrukturen. Die eigentliche Beschleunigung entsteht durch die mathematische Reduktion der Suchmenge.
Ucgensel, besgensel ve altigensel sayilar sirasiyla \(T_n=\frac{n(n+1)}{2}\), \(P_n=\frac{n(3n-1)}{2}\) ve \(H_n=n(2n-1)\) formulleriyle tanimlanir. Soruda \(40755\) sayisinin ayni anda ucgensel, besgensel ve altigensel oldugu verilir ve bundan sonraki ortak deger istenir.
Uygulamalar uc ayri dizi uzerinde eszamanli arama yapmaz. Bunun yerine altigensel sayilarin zaten ucgensel oldugu kimligini kullanir, sonra sadece altigensel adaylar uzerinde besgensellik testi uygular.
Yontemin tamami, uc kosullu aramayi tek boyutlu bir taramaya ve kesin bir aritmetik teste indirir.
Temel ozdeslik sunudur:
$$H_n=n(2n-1)=\frac{(2n-1)(2n)}{2}=T_{2n-1}.$$
Dolayisiyla her altigensel sayi otomatik olarak ucgenseldir. Aranan sayilar, yalnizca altigensel ve besgensel olan sayilardir. Ayrica bir ucgensellik testi yapmaya gerek kalmaz.
Kodun korudugu ana degismez deger budur: Bir aday \(H_n\) biciminde uretildigi anda gerekli uc ozellikten biri zaten garanti altindadir.
Bir \(x\) sayisinin besgensel olup olmadigini anlamak icin
$$x=P_k=\frac{k(3k-1)}{2}$$
denkleminden baslanir. Her iki tarafi \(24\) ile carpip \(1\) eklersek
$$24x+1=12k(3k-1)+1=36k^2-12k+1=(6k-1)^2$$
elde edilir. Bu nedenle \(x\), ancak ve ancak \(24x+1\) tam kare ise ve
$$k=\frac{1+\sqrt{24x+1}}{6}$$
tam sayi cikiyorsa besgenseldir. Uc implementasyonun da kullandigi kosul tam olarak budur.
Onemli nokta su: karekok sonucu tek basina kabul edilmez. Once kayan nokta ile karekok hesaplanir, sonra aday indeks en yakin tam sayiya yuvarlanir ve en sonda \(\frac{k(3k-1)}{2}\) yeniden kurularak \(x\) ile birebir esitligi kontrol edilir.
Soruda verilen bilinen ortak deger
$$H_{143}=143(2\cdot 143-1)=143\cdot 285=40755$$
oldugu icin, bir sonraki ortak degeri ararken tarama bir sonraki altigensel indisten, yani \(n=144\)'ten baslatilir.
Altigensel dizi pozitif \(n\) icin kesin artandir. Gercekten
$$H_{n+1}-H_n=(n+1)(2n+1)-n(2n-1)=4n+1 \gt 0.$$
Bu yuzden dongu \(n=143\)'u gectikten sonra bulunan ilk basarili aday, dogrudan sorulan sonraki cevap olur.
Bilinen \(40755\) degeri iyi bir kontrol ornegidir. Cunku
$$24\cdot 40755+1=978121=989^2,$$
buradan
$$k=\frac{1+989}{6}=165$$
elde edilir ve \(40755=P_{165}\) oldugu gorulur. Ayrica \(40755=H_{143}\) ve \(H_n=T_{2n-1}\) oldugundan sayi uc ailenin de icindedir.
Bir sonraki altigensel aday ise
$$H_{144}=144(287)=41328$$
degeridir. Bu sayi icin \(24\cdot 41328+1=991873\) tam kare degildir; dolayisiyla aday hemen elenir. Lineer taramanin pratik olmasini saglayan hizli red mekanizmasi budur.
C++, Python ve Java implementasyonlari altigensel indisi \(144\)'ten itibaren artirir. Her adimda aday deger \(n(2n-1)\) olarak hesaplanir. Ucgensellik sinamasi yapilmaz; cunku \(H_n=T_{2n-1}\) ozdesligi bu kismi zaten ortadan kaldirmistir.
Her aday \(x\) icin once \(1+24x\) hesaplaniyor, sonra karekok aliniyor, buna karsilik gelen besgensel indis en yakin tam sayiya yuvarlaniyor ve son olarak \(\frac{k(3k-1)}{2}=x\) esitligi tam sayi aritmetigiyle dogrulaniyor. Karekok adimi kayan nokta kullansa da, son esleme kontrolu testi guvenli hale getiriyor.
Adaylar artan altigensel sirada incelendigi icin, testi gecen ilk deger otomatik olarak \(40755\)'ten sonraki ilk ortak sayidir. C++ ve Java implementasyonlari tam aramadan once iki kucuk kontrol de yapar: \(40755\) besgensel olmalidir, \(40756\) ise olmamalidir.
Her dongu adimi sabit miktarda aritmetik islem ve bir karekok hesabi yaptigi icin aday basi maliyet \(O(1)\)'dir. Sonraki cozum hexagonal indis olarak \(N\)'de bulunuyorsa toplam sure \(O(N-143)\) olur.
Bellek kullanimi \(O(1)\)'dir; yalnizca birkac sayisal degisken tutulur. Dizi, tablo, recursion ya da buyuk veri yapilari yoktur. Hiz kazanimi veri yapilarindan degil, matematiksel indirgemeden gelir.
Los numeros triangulares, pentagonales y hexagonales se definen por \(T_n=\frac{n(n+1)}{2}\), \(P_n=\frac{n(3n-1)}{2}\) y \(H_n=n(2n-1)\). El enunciado indica que \(40755\) es a la vez triangular, pentagonal y hexagonal, y pide encontrar el siguiente numero con esa misma propiedad.
Las implementaciones no comparan tres sucesiones por separado. Aprovechan primero una identidad exacta entre numeros triangulares y hexagonales, y despues recorren solo candidatos hexagonales mientras aplican una prueba exacta de pentagonalidad.
La idea completa consiste en convertir una busqueda con tres condiciones en un recorrido lineal con un predicado aritmetico muy preciso.
La reduccion principal es
$$H_n=n(2n-1)=\frac{(2n-1)(2n)}{2}=T_{2n-1}.$$
Por tanto, cualquier numero hexagonal es automaticamente triangular. En consecuencia, el problema real es encontrar numeros que sean hexagonales y pentagonales al mismo tiempo. La condicion triangular deja de ser un filtro independiente.
Ese es el invariante central del algoritmo: en cuanto un valor se genera como \(H_n\), una de las tres propiedades ya esta garantizada.
Para decidir si un numero \(x\) es pentagonal, se parte de
$$x=P_k=\frac{k(3k-1)}{2}.$$
Si multiplicamos por \(24\) y sumamos \(1\), obtenemos
$$24x+1=12k(3k-1)+1=36k^2-12k+1=(6k-1)^2.$$
Asi, \(x\) es pentagonal si y solo si \(24x+1\) es un cuadrado perfecto y
$$k=\frac{1+\sqrt{24x+1}}{6}$$
resulta entero. Esa es exactamente la condicion usada por las versiones en C++, Python y Java.
Hay un detalle importante: la raiz cuadrada no se acepta ciegamente. Tras calcularla en punto flotante y redondear el indice candidato, la implementacion vuelve a construir \(\frac{k(3k-1)}{2}\) con aritmetica entera y comprueba si coincide exactamente con \(x\).
El valor comun ya conocido en el enunciado es
$$H_{143}=143(2\cdot 143-1)=143\cdot 285=40755.$$
Como la tarea pide el siguiente valor comun, la exploracion comienza en el siguiente indice hexagonal, es decir, \(n=144\).
La sucesion hexagonal es estrictamente creciente para \(n\) positivo. En efecto,
$$H_{n+1}-H_n=(n+1)(2n+1)-n(2n-1)=4n+1 \gt 0.$$
Por eso, una vez superado \(n=143\), el primer candidato que tambien sea pentagonal es necesariamente la respuesta buscada.
El valor \(40755\) sirve como verificacion conocida. Se cumple que
$$24\cdot 40755+1=978121=989^2,$$
y por tanto
$$k=\frac{1+989}{6}=165.$$
Eso demuestra que \(40755=P_{165}\). Junto con \(40755=H_{143}\) y \(H_n=T_{2n-1}\), queda confirmado que pertenece a las tres familias.
El siguiente candidato hexagonal es
$$H_{144}=144(287)=41328.$$
Para este valor, \(24\cdot 41328+1=991873\), que no es un cuadrado perfecto. Por eso se descarta al instante. Esa capacidad de rechazo rapido es lo que vuelve eficaz al barrido lineal.
Las implementaciones en C++, Python y Java recorren el indice hexagonal desde \(144\) en adelante. En cada iteracion calculan el candidato actual como \(n(2n-1)\). No hacen ninguna comprobacion triangular, porque la identidad \(H_n=T_{2n-1}\) ya resuelve esa parte.
Para cada candidato \(x\), la implementacion forma \(1+24x\), calcula su raiz cuadrada, redondea el indice pentagonal sugerido y despues verifica exactamente que \(\frac{k(3k-1)}{2}=x\). La raiz cuadrada es flotante, pero la comprobacion final es entera y evita falsos positivos.
Como los candidatos se inspeccionan en orden creciente de indice hexagonal, el primer valor que supera la prueba es automaticamente el siguiente numero comun despues de \(40755\). Ademas, las versiones en C++ y Java incluyen comprobaciones previas: \(40755\) debe ser pentagonal y \(40756\) no debe serlo.
Cada iteracion realiza una cantidad constante de operaciones aritmeticas y una raiz cuadrada, asi que el costo por candidato es \(O(1)\). Si la siguiente solucion aparece en el indice hexagonal \(N\), el tiempo total es \(O(N-143)\).
El espacio usado es \(O(1)\), porque solo se mantienen unas pocas variables numericas. No hay tablas, recursion ni estructuras grandes. La aceleracion proviene de la reduccion matematica del espacio de busqueda, no de almacenamiento adicional.
三角数、五边形数和六边形数分别由 \(T_n=\frac{n(n+1)}{2}\)、\(P_n=\frac{n(3n-1)}{2}\) 和 \(H_n=n(2n-1)\) 定义。题目告诉我们，\(40755\) 同时属于这三类数，并要求找出下一个也同时满足这三个条件的数。
实际实现并没有去同时枚举三条数列，也没有做三重判定。它先利用六边形数与三角数之间的恒等关系，把问题缩成“枚举六边形数并检测是否也是五边形数”，然后再用一个严格的判别式条件完成检查。
整个方法的核心，是把“三个条件同时成立”的搜索，化成“按顺序扫描一个序列，并对每个候选值做一次精确判定”。
最关键的化简是下面这个恒等式：
$$H_n=n(2n-1)=\frac{(2n-1)(2n)}{2}=T_{2n-1}.$$
这说明每一个六边形数自动也是一个三角数，而且对应的三角下标恰好是奇数 \(2n-1\)。因此题目中的“三角且五边形且六边形”实际上等价于“六边形且五边形”。三角条件可以彻底删掉。
这也是代码里最重要的不变量：一旦候选值被写成 \(H_n\) 的形式，它就已经满足了三项要求中的一项，后面只需要继续判断它是不是五边形数。
设某个数 \(x\) 是五边形数，那么它一定可以写成
$$x=P_k=\frac{k(3k-1)}{2}.$$
对这个式子乘以 \(24\) 再加上 \(1\)，得到
$$24x+1=12k(3k-1)+1=36k^2-12k+1=(6k-1)^2.$$
于是结论非常直接：\(x\) 是五边形数，当且仅当 \(24x+1\) 是完全平方数，并且
$$k=\frac{1+\sqrt{24x+1}}{6}$$
是整数。三种语言的实现都在做这件事，本质上没有差别。
这里有一个实现细节很重要。程序会先用浮点数求 \(\sqrt{24x+1}\)，再把推回去得到的下标四舍五入到最近的整数。但它不会只依赖浮点结果，而是会把这个整数下标重新代回公式 \(\frac{k(3k-1)}{2}\)，检查是否能严格还原出原来的 \(x\)。这个“先近似、后精确验证”的组合，让测试既简单又可靠。
题目已经给出了已知公共值 \(40755\)，而它对应的六边形表示是
$$H_{143}=143(2\cdot 143-1)=143\cdot 285=40755.$$
既然题目要找的是 下一个 公共值，那么扫描自然应该从下一个六边形下标开始，也就是 \(n=144\)。
这样做之所以正确，还依赖于六边形数列的单调性。对正整数 \(n\)，有
$$H_{n+1}-H_n=(n+1)(2n+1)-n(2n-1)=4n+1 \gt 0.$$
所以六边形数严格递增。也就是说，一旦我们从 \(n=144\) 往上依次检查，那么第一个同时通过五边形判定的值，就一定是 \(40755\) 之后的下一个答案，而不会漏掉更小的公共值。
题目给出的 \(40755\) 正好可以当作一个完整样例。先看五边形判定：
$$24\cdot 40755+1=978121=989^2.$$
于是
$$k=\frac{1+989}{6}=165,$$
说明 \(40755=P_{165}\)。另一方面，它又等于 \(H_{143}\)，而所有六边形数都满足 \(H_n=T_{2n-1}\)，因此它当然也属于三角数列。三重身份全部成立。
再看扫描开始后的第一个候选值：
$$H_{144}=144(287)=41328.$$
对它做同样的检查，得到 \(24\cdot 41328+1=991873\)，这不是完全平方数，所以它立刻被排除。程序就是靠这种非常便宜的“快速否决”一步步向前推进的。
C++、Python 和 Java 实现都会把六边形下标从 \(144\) 开始递增，并在每一步计算当前候选值 \(n(2n-1)\)。由于 \(H_n=T_{2n-1}\) 已经说明它天然是三角数，所以实现里完全没有单独的三角性检查。
对于当前候选值 \(x\)，实现先构造 \(1+24x\)，然后求平方根，再把由此得到的五边形下标取到最近的整数。接下来它会用整数算术重新计算 \(\frac{k(3k-1)}{2}\)，看是否恰好等于 \(x\)。即使平方根步骤用到了浮点数，最后这一步精确回代也会把误判挡掉。
因为候选值按照六边形下标递增顺序被检查，所以一旦某个值第一次通过五边形判定，它就自动是题目要求的“下一个公共值”。此外，C++ 和 Java 版本在正式搜索前还做了两个小型校验：已知的 \(40755\) 必须通过测试，而相邻的 \(40756\) 必须失败。
每次循环只做常数次整数运算和一次平方根运算，因此单个候选值的时间代价是 \(O(1)\)。如果下一个解出现在六边形下标 \(N\)，那么总时间就是 \(O(N-143)\)。
空间复杂度是 \(O(1)\)。实现只保存少量数值变量，不需要数组、哈希表、递归栈或任何大型预处理结构。这个解法快的原因，不在于复杂的数据结构，而在于搜索空间被数学上大幅缩小了。
Треугольные, пятиугольные и шестиугольные числа задаются формулами \(T_n=\frac{n(n+1)}{2}\), \(P_n=\frac{n(3n-1)}{2}\) и \(H_n=n(2n-1)\). В условии сказано, что \(40755\) одновременно принадлежит всем трем семействам, и требуется найти следующее такое число.
Реализации не пытаются параллельно перебирать все три последовательности. Сначала используется точное тождество между шестиугольными и треугольными числами, а затем перебираются только шестиугольные кандидаты с проверкой на пятиугольность.
Вся идея состоит в том, чтобы заменить поиск по трем условиям линейным перебором одной последовательности и строгим арифметическим критерием.
Главное тождество имеет вид
$$H_n=n(2n-1)=\frac{(2n-1)(2n)}{2}=T_{2n-1}.$$
Значит, любое шестиугольное число автоматически является треугольным. Следовательно, в задаче достаточно искать числа, которые одновременно шестиугольные и пятиугольные. Отдельная проверка на треугольность не нужна.
Именно это и является основным инвариантом алгоритма: как только кандидат построен в форме \(H_n\), одна из трех требуемых характеристик уже выполнена.
Пусть число \(x\) пятиугольное. Тогда существует индекс \(k\), для которого
$$x=P_k=\frac{k(3k-1)}{2}.$$
Умножим на \(24\) и прибавим \(1\):
$$24x+1=12k(3k-1)+1=36k^2-12k+1=(6k-1)^2.$$
Отсюда следует критерий: \(x\) является пятиугольным тогда и только тогда, когда \(24x+1\) является полным квадратом и
$$k=\frac{1+\sqrt{24x+1}}{6}$$
получается целым числом. Именно этим критерием пользуются версии на C++, Python и Java.
При этом квадратный корень служит только промежуточной оценкой. После вычисления корня и округления предполагаемого индекса программа заново подставляет целое \(k\) в формулу \(\frac{k(3k-1)}{2}\) и проверяет точное совпадение с \(x\). Благодаря этому итоговая проверка остается строгой, несмотря на использование чисел с плавающей точкой внутри.
Из условия уже известен один общий элемент:
$$H_{143}=143(2\cdot 143-1)=143\cdot 285=40755.$$
Так как требуется найти следующее такое число, логично начать с ближайшего следующего шестиугольного индекса, то есть с \(n=144\).
Это корректно еще и потому, что последовательность \(H_n\) строго возрастает при положительных \(n\). Действительно,
$$H_{n+1}-H_n=(n+1)(2n+1)-n(2n-1)=4n+1 \gt 0.$$
Значит, после перехода за \(n=143\) первый кандидат, который пройдет тест на пятиугольность, автоматически и будет ближайшим следующим решением.
Число \(40755\) удобно использовать как проверочный пример. Для него
$$24\cdot 40755+1=978121=989^2,$$
поэтому
$$k=\frac{1+989}{6}=165.$$
Следовательно, \(40755=P_{165}\). Одновременно \(40755=H_{143}\), а всякое \(H_n\) равно \(T_{2n-1}\), так что принадлежность всем трем семействам подтверждается полностью.
Следующий шестиугольный кандидат равен
$$H_{144}=144(287)=41328.$$
Здесь \(24\cdot 41328+1=991873\), а это не полный квадрат. Поэтому такой кандидат сразу отбрасывается. Именно такие быстрые отказы и делают линейный перебор достаточно легким.
Реализации на C++, Python и Java перебирают шестиугольный индекс, начиная с \(144\). На каждом шаге текущий кандидат вычисляется по формуле \(n(2n-1)\). Отдельной проверки на треугольность нет, потому что тождество \(H_n=T_{2n-1}\) уже устранило эту часть задачи.
Для каждого кандидата \(x\) программа строит число \(1+24x\), берет квадратный корень, округляет полученный индекс и затем точно проверяет, что \(\frac{k(3k-1)}{2}=x\). Даже если корень вычисляется в плавающей арифметике, завершающая целочисленная подстановка не позволяет принять неверный результат.
Так как кандидаты рассматриваются по возрастанию шестиугольного индекса, первое значение, прошедшее тест, и есть искомое следующее общее число после \(40755\). Кроме того, версии на C++ и Java перед основным поиском выполняют два контрольных теста: \(40755\) должно распознаваться как пятиугольное, а \(40756\) - нет.
Одна итерация цикла требует лишь постоянного числа арифметических операций и одного извлечения квадратного корня, то есть \(O(1)\) времени на кандидата. Если следующее решение достигается на шестиугольном индексе \(N\), полное время работы равно \(O(N-143)\).
Память составляет \(O(1)\): алгоритм хранит только несколько числовых переменных и не использует массивы, таблицы или рекурсию. Ускорение здесь достигается не структурами данных, а удачной математической редукцией пространства поиска.
تعرَّف الاعداد المثلثية والخماسية والسداسية بالعلاقات \(T_n=\frac{n(n+1)}{2}\) و\(P_n=\frac{n(3n-1)}{2}\) و\(H_n=n(2n-1)\). يذكر نص المسالة ان \(40755\) عدد يقع في العائلات الثلاث معًا، والمطلوب هو ايجاد العدد التالي الذي يحقق الخاصية نفسها.
التنفيذات لا تبحث في السلاسل الثلاث بشكل مستقل. الفكرة ابسط من ذلك: نستفيد اولًا من علاقة مباشرة بين الاعداد السداسية والمثلثية، ثم نفحص فقط الاعداد السداسية لنعرف هل هي خماسية ايضا ام لا.
جوهر الحل هو تحويل شرط ثلاثي إلى فحص خطي لسلسلة واحدة مع اختبار عددي دقيق.
الهوية الاساسية هي
$$H_n=n(2n-1)=\frac{(2n-1)(2n)}{2}=T_{2n-1}.$$
وهذا يعني ان كل عدد سداسي يقع تلقائيًا داخل الاعداد المثلثية. لذلك يصبح المطلوب الحقيقي هو ايجاد عدد يكون سداسيًا وخماسيًا في الوقت نفسه. لم نعد بحاجة إلى اختبار المثلثية على الاطلاق.
هذه هي الثابتة الاساسية التي يعتمد عليها الكود: ما دام المرشح قد وُلد على صورة \(H_n\)، فقد تحقق احد الشروط الثلاثة مسبقًا.
اذا كان \(x\) عددًا خماسيًا، فهناك عدد صحيح \(k\) بحيث
$$x=P_k=\frac{k(3k-1)}{2}.$$
وبضرب الطرفين في \(24\) ثم اضافة \(1\) نحصل على
$$24x+1=12k(3k-1)+1=36k^2-12k+1=(6k-1)^2.$$
اذن يكون \(x\) خماسيًا إذا وفقط إذا كان \(24x+1\) مربعًا كاملًا وكان
$$k=\frac{1+\sqrt{24x+1}}{6}$$
عددًا صحيحًا. هذا هو الشرط الحسابي نفسه الذي تستخدمه تطبيقات C++ وPython وJava.
لكن التنفيذ لا يثق بنتيجة الجذر التربيعي وحدها. بعد حساب الجذر باستخدام اعداد عائمة وتقريب الفهرس الناتج إلى اقرب عدد صحيح، يعيد بناء القيمة \(\frac{k(3k-1)}{2}\) بدقة صحيحة ويقارنها مع \(x\). بهذه الطريقة تبقى النتيجة النهائية دقيقة حتى لو استُخدم الجذر التربيعي العائم كخطوة وسيطة.
القيمة المشتركة المعروفة في نص المسالة هي
$$H_{143}=143(2\cdot 143-1)=143\cdot 285=40755.$$
وبما ان المطلوب هو العدد التالي بعد هذه القيمة، فمن الطبيعي ان يبدأ المسح من الفهرس السداسي التالي، اي من \(n=144\).
كما ان هذا صحيح رياضيًا لان متتالية الاعداد السداسية متزايدة تزايدًا صارمًا عندما يكون \(n\) موجبًا. فعلًا لدينا
$$H_{n+1}-H_n=(n+1)(2n+1)-n(2n-1)=4n+1 \gt 0.$$
لذلك، بعد تجاوز \(n=143\)، يكون اول مرشح ينجح في اختبار الخماسية هو بالضرورة الجواب التالي المطلوب، ولا يمكن ان يكون هناك حل اصغر قد تم تجاوزه.
يمكن استخدام \(40755\) كمثال تحقق كامل. لدينا
$$24\cdot 40755+1=978121=989^2,$$
ومن ثم
$$k=\frac{1+989}{6}=165.$$
اي ان \(40755=P_{165}\). وبما انه ايضا يساوي \(H_{143}\)، وكل عدد سداسي هو مثلثي وفق العلاقة \(H_n=T_{2n-1}\)، فهذا يثبت ان \(40755\) ينتمي فعلًا إلى العائلات الثلاث.
اول مرشح بعده في المسح هو
$$H_{144}=144(287)=41328.$$
لكن \(24\cdot 41328+1=991873\) ليس مربعًا كاملًا، ولذلك يُرفض مباشرة. هذا النوع من الرفض السريع هو ما يجعل البحث الخطي عمليًا جدًا في هذه المسالة.
تنفيذات C++ وPython وJava تزيد الفهرس السداسي ابتداءً من \(144\). في كل خطوة يُحسب المرشح الحالي بالصيغة \(n(2n-1)\). ولا يوجد اي اختبار مستقل للمثلثية، لان الهوية \(H_n=T_{2n-1}\) حسمت هذا الجزء مسبقًا.
لكل مرشح \(x\)، تبني الشفرة القيمة \(1+24x\)، ثم تحسب جذرها التربيعي، ثم تقرّب الفهرس الخماسي الناتج، وبعد ذلك تتحقق بدقة من ان \(\frac{k(3k-1)}{2}=x\). حتى لو استُخدمت الحسابات العائمة في خطوة الجذر، فإن التحقق الصحيح النهائي يمنع اي قبول خاطئ.
بما ان المرشحين يفحصون بترتيب تصاعدي حسب الفهرس السداسي، فإن اول قيمة تنجح في الاختبار تكون تلقائيًا هي العدد المشترك التالي بعد \(40755\). كما تضيف نسختا C++ وJava اختبارين تمهيديين صغيرين: يجب ان ينجح \(40755\) في اختبار الخماسية، بينما يجب ان يفشل \(40756\).
كل دورة من الحلقة تقوم بعدد ثابت من العمليات الحسابية وبحساب جذر تربيعي واحد، لذا فزمن كل مرشح هو \(O(1)\). إذا ظهرت القيمة التالية عند الفهرس السداسي \(N\)، فإن الزمن الكلي يكون \(O(N-143)\).
استهلاك الذاكرة هو \(O(1)\)، لان الخوارزمية تحتفظ بعدد قليل فقط من المتغيرات العددية ولا تستخدم جداول او مصفوفات كبيرة او استدعاءً تكراريًا. مصدر الكفاءة هنا هو الاختزال الرياضي لمساحة البحث، لا استعمال هياكل بيانات معقدة.