We seek every integer \(n\) with \(1 \le n < 10^6\) whose standard decimal representation and standard binary representation are both palindromes. The required result is the sum of all such numbers.
The phrase "without leading zeros" matters. In base 10 we already use the usual decimal writing, and in base 2 we use the canonical binary expansion. So a number like \(10\) is binary \(1010_2\), not \(01010_2\), and only the canonical form is allowed in the palindrome test.
The problem is small enough that a direct search is completely practical, but the search is guided by a few clean structural facts about palindromes in two bases.
Write the decimal expansion of \(n\) as
$$n=d_{m-1}10^{m-1}+d_{m-2}10^{m-2}+\cdots+d_1 10+d_0,$$
with \(d_{m-1}\neq 0\). Write the binary expansion as
$$n=b_{\ell-1}2^{\ell-1}+b_{\ell-2}2^{\ell-2}+\cdots+b_1 2+b_0,$$
with \(b_{\ell-1}=1\). The two palindrome conditions are simply
$$d_i=d_{m-1-i}\quad\text{for }0\le i<m,$$
and
$$b_j=b_{\ell-1-j}\quad\text{for }0\le j<\ell.$$
So the entire task is to find integers whose decimal digit string and binary digit string are both mirror-symmetric around the center.
Because the binary expansion has no leading zeros, its first digit is always \(1\). If the binary string is also a palindrome, the last digit must match the first one, so \(b_0=1\) as well. But \(b_0\) is exactly the parity bit, therefore every double-base palindrome is odd.
This does not change the mathematical definition, but it explains why even numbers can never contribute to the sum. The implementations keep the simpler full scan, yet the binary palindrome test rejects all even inputs automatically.
Since the search stops below \(10^6\), a decimal candidate has at most six digits. In binary we have
$$2^{19}=524288 < 10^6 < 2^{20}=1048576,$$
so every candidate has at most twenty binary digits. That means each palindrome check is tiny: at most 6 character comparisons for the decimal string and at most 20 characters in the binary string.
There are also only
$$\sum_{k=1}^{6} 9\cdot 10^{\lceil k/2\rceil-1}=9+9+90+90+900+900=1998$$
decimal palindromes below one million. This count shows how restrictive the condition already is, even before imposing the binary palindrome condition.
The example from the statement is a good illustration because both symmetries are visible. In decimal,
$$585=5\cdot 10^2+8\cdot 10+5,$$
so the digit pattern is \(5,8,5\), which reads the same from either side.
In binary, repeated division by 2 gives
$$585=2^9+2^6+2^3+2^0=1001001001_2.$$
The binary digits are again symmetric: the first and last bits are \(1\), the second and next-to-last are \(0\), and so on. Therefore \(585\) is one of the terms that must be added.
A more optimized strategy could generate only decimal palindromes first, but the implementations intentionally use the simpler method: scan all integers from \(1\) up to the limit, test decimal symmetry, build the binary expansion, and test binary symmetry. Because the upper bound is only one million and the digit lengths are so small, that straightforward approach is already fast enough.
The C++, Python, and Java implementations all follow the same structure. They accept an optional upper limit, defaulting to \(10^6\), and they optionally run small checkpoints before the full computation.
The main loop visits each integer \(n\) with \(1 \le n < \text{limit}\). First the implementation converts \(n\) to its decimal string and compares mirrored positions from the two ends toward the center. If any pair differs, \(n\) is discarded immediately.
If the decimal test succeeds, the implementation constructs the binary representation manually. It repeatedly takes the least significant bit, appends the corresponding character, and divides by 2. After \(t\) iterations, the collected characters are exactly the lowest \(t\) bits of \(n\), written from low bit to high bit; reversing that sequence yields the canonical binary expansion with no leading zeros. The same mirrored-character palindrome test is then applied to the binary string.
Whenever both tests succeed, the number is added to a running sum. The optional checkpoints verify two things: the palindrome test accepts a known symmetric string, and the partial sum below \(1000\) is \(1772\). Those checks ensure that both the symmetry logic and the accumulation logic are behaving correctly before the full run.
Let \(L\) be the limit. The implementation examines every integer from \(1\) to \(L-1\), so there are \(O(L)\) candidates. For each one, decimal conversion and the decimal palindrome test cost \(O(\log_{10} L)\), while binary conversion and the binary palindrome test cost \(O(\log_2 L)\). Therefore the total running time is
$$O(L\log L).$$
The extra space per candidate is \(O(\log L)\), because the implementation stores short decimal and binary strings. For the specific Project Euler bound \(L=10^6\), those strings never exceed 6 and 20 characters respectively, so the constant factors are very small.
Gesucht sind alle ganzen Zahlen \(n\) mit \(1 \le n < 10^6\), deren übliche Dezimaldarstellung und deren übliche Binärdarstellung beide Palindrome sind. Das Ergebnis der Aufgabe ist die Summe aller dieser Zahlen.
Die Bedingung "ohne führende Nullen" ist wesentlich. Im Dezimalsystem verwenden wir die normale Schreibweise, und im Binärsystem die kanonische Darstellung. Daher ist \(10\) in Binärschreibweise \(1010_2\) und nicht \(01010_2\); nur die kanonische Form darf auf Palindromeigenschaft geprüft werden.
Die Schranke ist klein genug für eine direkte Suche, aber einige einfache Strukturbeobachtungen erklären präzise, warum diese Suche funktioniert und warum sie schnell genug ist.
Schreibe die Dezimalentwicklung von \(n\) als
$$n=d_{m-1}10^{m-1}+d_{m-2}10^{m-2}+\cdots+d_1 10+d_0,$$
wobei \(d_{m-1}\neq 0\) gilt. Die Binärentwicklung sei
$$n=b_{\ell-1}2^{\ell-1}+b_{\ell-2}2^{\ell-2}+\cdots+b_1 2+b_0,$$
mit \(b_{\ell-1}=1\). Palindromie bedeutet dann genau
$$d_i=d_{m-1-i}\quad\text{für }0\le i<m,$$
und zugleich
$$b_j=b_{\ell-1-j}\quad\text{für }0\le j<\ell.$$
Die Aufgabe besteht also darin, Zahlen zu finden, deren Ziffernfolge in beiden Basen um die Mitte gespiegelt symmetrisch ist.
Da die Binärdarstellung keine führenden Nullen besitzt, beginnt sie immer mit einer \(1\). Ist diese Darstellung zusätzlich ein Palindrom, dann muss auch die letzte Stelle \(1\) sein, also \(b_0=1\). Genau dieses Bit entscheidet über die Parität, also ist jede doppelt-palindromische Zahl notwendigerweise ungerade.
Die Implementierungen nutzen diese Beobachtung nicht als separate Schleifenoptimierung, weil die vollständige Suche ohnehin schnell genug ist. Mathematisch erklärt sie aber sofort, warum gerade Zahlen nie zur Summe beitragen können.
Unterhalb von \(10^6\) hat jeder Kandidat höchstens sechs Dezimalstellen. Für die Binärlänge gilt
$$2^{19}=524288 < 10^6 < 2^{20}=1048576,$$
also besitzt jeder Kandidat höchstens zwanzig Binärstellen. Jede einzelne Palindromprüfung ist damit sehr klein: höchstens 6 Zeichen im Dezimalsystem und höchstens 20 Zeichen im Binärsystem.
Außerdem gibt es unter einer Million nur
$$\sum_{k=1}^{6} 9\cdot 10^{\lceil k/2\rceil-1}=9+9+90+90+900+900=1998$$
dezimale Palindrome. Schon diese Zahl zeigt, wie einschränkend die Dezimalbedingung ist, noch bevor die Binärbedingung hinzukommt.
Das Beispiel aus der Aufgabenstellung zeigt die doppelte Symmetrie sehr klar. Dezimal gilt
$$585=5\cdot 10^2+8\cdot 10+5,$$
also ist die Ziffernfolge \(5,8,5\) ein Palindrom.
Binär erhält man durch wiederholtes Teilen durch 2
$$585=2^9+2^6+2^3+2^0=1001001001_2.$$
Auch hier sind die Ziffern gespiegelt gleich, also ist \(585\) tatsächlich einer der Summanden.
Man könnte zuerst nur Dezimalpalindrome erzeugen und dann deren Binärdarstellungen testen. Die vorhandenen Implementierungen wählen bewusst die einfachere Variante: alle Zahlen von \(1\) bis zur Schranke durchlaufen, die Dezimalsymmetrie prüfen, die Binärdarstellung konstruieren und anschließend die Binärsymmetrie prüfen. Wegen der kleinen Obergrenze von einer Million ist diese direkte Methode bereits vollkommen ausreichend.
Die C++-, Python- und Java-Implementierungen verwenden denselben Ablauf. Zunächst wird optional eine obere Grenze eingelesen; standardmäßig ist sie \(10^6\). Zusätzlich können kleine Selbsttests vor dem vollständigen Lauf aktiviert bleiben oder abgeschaltet werden.
Die Hauptschleife betrachtet jedes \(n\) mit \(1 \le n < \text{limit}\). Zuerst wird \(n\) in eine Dezimalzeichenkette umgewandelt. Danach vergleicht die Implementierung paarweise Zeichen von links und rechts, bis entweder ein Widerspruch gefunden wird oder die Mitte erreicht ist. Bei einem Widerspruch wird die Zahl sofort verworfen.
Besteht \(n\) den Dezimaltest, wird die Binärdarstellung nicht über eine Bibliotheksroutine, sondern direkt durch wiederholtes Auslesen des niederwertigsten Bits und anschließendes Teilen durch 2 erzeugt. Nach \(t\) Schritten enthält die aufgebaute Folge genau die \(t\) niedrigsten Bits, allerdings zunächst in umgekehrter Reihenfolge. Erst das Umdrehen dieser Folge liefert die normale Binärdarstellung ohne führende Nullen. Auf diese Darstellung wird dann dieselbe Spiegelprüfung angewendet.
Bestehen beide Tests, wird \(n\) zur laufenden Summe addiert. Die optionalen Prüfungen kontrollieren zwei bekannte Tatsachen: eine offensichtliche palindromische Zeichenkette wird korrekt erkannt, und die Teilsumme für alle gültigen Zahlen unter \(1000\) ist \(1772\). Damit werden sowohl die Symmetrieprüfung als auch die Summation abgesichert.
Sei \(L\) die Obergrenze. Dann werden genau \(L-1\) Kandidaten untersucht, also \(O(L)\) viele. Für jeden Kandidaten kosten Dezimalumwandlung und Dezimalprüfung \(O(\log_{10} L)\), während Binärumwandlung und Binärprüfung \(O(\log_2 L)\) benötigen. Insgesamt ergibt sich somit eine Laufzeit von
$$O(L\log L).$$
Der zusätzliche Speicherbedarf pro Kandidat ist \(O(\log L)\), da kurze Dezimal- und Binärzeichenketten gehalten werden. Für \(L=10^6\) sind das höchstens 6 bzw. 20 Zeichen, also sehr kleine Konstanten.
\(1 \le n < 10^6\) aralığındaki tüm tam sayılar içinde, hem standart onluk yazımı hem de standart ikilik yazımı palindrom olanları arıyoruz. Sorunun istediği sonuç, bu sayıların toplamıdır.
"Başa sıfır eklenmeden" şartı önemlidir. Onlukta zaten normal gösterimi kullanırız. İkilikte de sayıyı kanonik biçimiyle yazarız; dolayısıyla \(10\) sayısı \(1010_2\) olarak değerlendirilir, \(01010_2\) olarak değil. Palindrom testi yalnızca bu gerçek gösterim üzerinde yapılır.
Üst sınır küçük olduğu için doğrudan tarama rahatlıkla uygulanabilir. Yine de bu taramanın neden doğru ve yeterli olduğunu birkaç problem-özel gözlemle netleştirmek faydalıdır.
\(n\) sayısının onluk açılımını
$$n=d_{m-1}10^{m-1}+d_{m-2}10^{m-2}+\cdots+d_1 10+d_0,$$
şeklinde yazalım; burada \(d_{m-1}\neq 0\) olsun. İkilik açılımı da
$$n=b_{\ell-1}2^{\ell-1}+b_{\ell-2}2^{\ell-2}+\cdots+b_1 2+b_0,$$
olsun; burada da \(b_{\ell-1}=1\). Palindrom olma koşulları tam olarak
$$d_i=d_{m-1-i}\quad\text{ve}\quad b_j=b_{\ell-1-j}$$
eşitlikleridir. Yani amaç, hem onluk rakam dizisi hem de ikilik bit dizisi merkeze göre simetrik olan sayıları bulmaktır.
İkilik gösterimde başta sıfır olmadığı için ilk bit her zaman \(1\)'dir. Eğer bit dizisi palindromsa, son bitin de ilk bitle aynı olması gerekir; dolayısıyla \(b_0=1\). Ama \(b_0\) tam olarak tek-çift bilgisini verir. Bu yüzden çift tabanlı palindrom olan her sayı mutlaka tektir.
Uygulamalar bu gözlemi ayrı bir filtre olarak kullanmıyor; onun yerine tüm aralığı geziyorlar. Yine de matematiksel olarak bu özellik, neden hiçbir çift sayının sonuca katkı veremeyeceğini anında açıklar.
Arama \(10^6\)'nın altında bittiği için bir adayın onluk yazımı en fazla 6 basamaktır. İkilik uzunluk için de
$$2^{19}=524288 < 10^6 < 2^{20}=1048576$$
olduğundan her aday en fazla 20 bite sahiptir. Böylece her tekil palindrom kontrolü çok küçüktür.
Ayrıca bir milyonun altında yalnızca
$$\sum_{k=1}^{6} 9\cdot 10^{\lceil k/2\rceil-1}=9+9+90+90+900+900=1998$$
tane onluk palindrom vardır. Bu sayı, yalnızca onluk koşulun bile aday kümesini ne kadar daralttığını gösterir; ikilik koşul eklendiğinde küme daha da seyrekleşir.
Soruda verilen \(585\) sayısı iki tabandaki simetriyi birlikte görmek için idealdir. Onlukta
$$585=5\cdot 10^2+8\cdot 10+5$$
olduğu için rakam dizisi \(5,8,5\) biçimindedir ve soldan-sağa, sağdan-sola aynıdır.
İkilikte ise tekrar tekrar 2'ye bölerek
$$585=2^9+2^6+2^3+2^0=1001001001_2$$
elde edilir. Bu bit dizisi de simetriktir. Dolayısıyla \(585\), toplama giren gerçek örneklerden biridir.
Kuramsal olarak önce yalnızca onluk palindromlar üretilebilir, sonra bunların ikilik gösterimleri sınanabilir. Fakat eldeki C++, Python ve Java uygulamaları daha yalın olan yaklaşımı seçer: \(1\)'den limite kadar tüm sayıları dolaş, onluk palindromluğunu denetle, ikilik yazımı kur, sonra ikilik palindromluğunu denetle. Üst sınır sadece bir milyon olduğu için bu doğrudan yöntem fazlasıyla yeterlidir.
C++, Python ve Java uygulamaları aynı algoritmayı izler. İsteğe bağlı bir üst sınır okunur; varsayılan değer \(10^6\)'dır. İstenirse küçük doğrulama kontrolleri atlanabilir, aksi halde tam hesaplamadan önce çalıştırılır.
Ana döngüde \(1 \le n < \text{limit}\) olan her sayı ele alınır. Önce sayı onluk karakter dizisine çevrilir ve soldan-sağa ile sağdan-sola karşılıklı duran karakterler karşılaştırılır. Eşleşmeyen bir çift bulunursa sayı hemen elenir.
Onluk testini geçen sayılar için ikilik gösterim elle kurulmaktadır. En düşük anlamlı bit alınır, buna karşılık gelen karakter diziye eklenir, sonra sayı 2'ye bölünür. \(t\) adım sonunda elde edilen karakterler, sayının en düşük \(t\) bitini düşük bitten yüksek bite doğru içerir. Bu diziyi ters çevirmek, başında sıfır olmayan standart ikilik yazımı verir. Ardından aynı ayna karşılaştırması bu ikilik diziye uygulanır.
Her iki testi de geçen sayılar bir toplamda biriktirilir. İsteğe bağlı kontrol aşaması iki bilinen gerçeği doğrular: açıkça simetrik bir dize doğru tanınmalıdır ve \(1000\)'in altındaki geçerli sayıların toplamı \(1772\) olmalıdır. Böylece hem palindrom testi hem de toplama mantığı sınanmış olur.
Limit \(L\) olsun. Uygulama \(1\)'den \(L-1\)'e kadar tüm sayıları dolaştığı için \(O(L)\) aday inceler. Her aday için onluk dönüştürme ve onluk palindrom testi \(O(\log_{10} L)\), ikilik dönüştürme ve ikilik palindrom testi ise \(O(\log_2 L)\) zaman alır. Toplam süre bu yüzden
$$O(L\log L)$$
olur. Ek bellek kullanımı aday başına \(O(\log L)\)'dir; çünkü kısa onluk ve ikilik dizgeler tutulur. Problemdeki özel sınır için bu dizgelerin uzunluğu en fazla 6 ve 20 karakterdir.
Buscamos todos los enteros \(n\) con \(1 \le n < 10^6\) cuya representación decimal usual y cuya representación binaria usual sean ambas palíndromas. El resultado pedido es la suma de todos esos números.
La condición "sin ceros a la izquierda" es esencial. En base 10 usamos la escritura decimal normal, y en base 2 usamos la expansión binaria canónica. Por eso \(10\) se evalúa como \(1010_2\), no como \(01010_2\), y solo esa forma canónica puede entrar en la prueba de palíndromo.
La cota superior es lo bastante pequeña como para permitir una búsqueda directa, pero conviene describir con precisión las estructuras matemáticas que hacen transparente el problema.
Escribamos la expansión decimal de \(n\) como
$$n=d_{m-1}10^{m-1}+d_{m-2}10^{m-2}+\cdots+d_1 10+d_0,$$
con \(d_{m-1}\neq 0\). La expansión binaria será
$$n=b_{\ell-1}2^{\ell-1}+b_{\ell-2}2^{\ell-2}+\cdots+b_1 2+b_0,$$
donde \(b_{\ell-1}=1\). Ser palíndromo en ambas bases equivale exactamente a exigir
$$d_i=d_{m-1-i}\quad\text{y}\quad b_j=b_{\ell-1-j}.$$
Así, el problema consiste en encontrar números cuya secuencia de cifras decimales y cuya secuencia de bits sean simétricas con respecto al centro.
Como la representación binaria canónica siempre empieza con \(1\), un palíndromo binario también debe terminar con \(1\). Eso significa que \(b_0=1\), y \(b_0\) es precisamente el bit de paridad. En consecuencia, todo palíndromo de doble base es impar.
Las implementaciones no aprovechan esta observación para saltarse explícitamente los pares, porque el barrido completo ya es suficientemente rápido. Aun así, esta propiedad explica de inmediato por qué ningún número par puede contribuir a la suma.
Debajo de \(10^6\), cualquier candidato tiene a lo sumo 6 cifras decimales. En binario,
$$2^{19}=524288 < 10^6 < 2^{20}=1048576,$$
de modo que cualquier candidato tiene a lo sumo 20 bits. Por eso cada comprobación individual es muy pequeña.
Además, por debajo de un millón solo hay
$$\sum_{k=1}^{6} 9\cdot 10^{\lceil k/2\rceil-1}=9+9+90+90+900+900=1998$$
palíndromos decimales. Ese conteo muestra que la restricción decimal ya es fuerte antes de imponer la condición binaria.
El ejemplo clásico del enunciado resume bien la idea. En decimal,
$$585=5\cdot 10^2+8\cdot 10+5,$$
de modo que sus cifras son \(5,8,5\), claramente simétricas.
En binario, mediante divisiones sucesivas por 2, se obtiene
$$585=2^9+2^6+2^3+2^0=1001001001_2.$$
La cadena binaria también es simétrica alrededor del centro, así que \(585\) pertenece a la suma buscada.
Se podría generar primero el conjunto de palíndromos decimales y después comprobar su forma binaria. Sin embargo, las implementaciones en C++, Python y Java eligen el procedimiento más simple y directo: recorrer todo el intervalo, probar la simetría decimal, construir la representación binaria y probar también esa simetría. Para un límite de un millón, esa solución es totalmente adecuada.
Las tres implementaciones comparten la misma estructura. Admiten un límite opcional, cuyo valor por defecto es \(10^6\), y pueden ejecutar pequeñas comprobaciones internas antes del cálculo completo.
El bucle principal recorre cada entero \(n\) con \(1 \le n < \text{limit}\). Primero convierte \(n\) en su forma decimal y compara caracteres simétricos desde los extremos hacia el centro. Si aparece una discrepancia, el número se descarta inmediatamente.
Si el test decimal se supera, la representación binaria se construye manualmente. En cada paso se toma el bit menos significativo, se añade el carácter correspondiente y luego se divide por 2. Tras \(t\) iteraciones, la secuencia acumulada contiene exactamente los \(t\) bits menos significativos de \(n\), escritos del menos significativo al más significativo. Al invertir esa secuencia se obtiene la expansión binaria usual, sin ceros a la izquierda. Sobre esa cadena se aplica exactamente la misma prueba de palíndromo.
Cuando ambas comprobaciones son correctas, el número se añade a la suma acumulada. Las comprobaciones opcionales validan dos hechos conocidos: una cadena evidentemente simétrica debe aceptarse, y la suma de todos los casos válidos menores que \(1000\) debe ser \(1772\). Eso protege tanto la lógica del espejo como la acumulación final.
Si el límite es \(L\), el programa inspecciona \(L-1\) candidatos, es decir, \(O(L)\) números. Para cada uno, la conversión decimal y su prueba de palíndromo cuestan \(O(\log_{10} L)\), mientras que la conversión binaria y su prueba cuestan \(O(\log_2 L)\). Por tanto, el tiempo total es
$$O(L\log L).$$
El espacio auxiliar por candidato es \(O(\log L)\), ya que se guardan cadenas decimales y binarias muy cortas. En la cota concreta del problema esas longitudes nunca superan 6 y 20 caracteres.
我们要找出所有满足 \(1 \le n < 10^6\) 的整数，其中 \(n\) 的十进制标准表示和二进制标准表示都必须是回文。题目要求输出所有这类数的总和。
“不允许前导零”这一点不能忽略。十进制直接使用通常写法，二进制也必须使用规范表示，因此 \(10\) 只能写成 \(1010_2\)，不能把它当成 \(01010_2\) 来制造一个假的回文。回文判断只能针对规范表示进行。
这个问题的上界很小，所以直接枚举完全可行。不过在真正实现之前，先把题目中的数学对象和约束整理清楚，会更容易看懂为什么简单做法就已经足够。
把 \(n\) 的十进制展开写成
$$n=d_{m-1}10^{m-1}+d_{m-2}10^{m-2}+\cdots+d_1 10+d_0,$$
其中最高位满足 \(d_{m-1}\neq 0\)。把二进制展开写成
$$n=b_{\ell-1}2^{\ell-1}+b_{\ell-2}2^{\ell-2}+\cdots+b_1 2+b_0,$$
其中最高位必然满足 \(b_{\ell-1}=1\)。十进制回文与二进制回文分别等价于
$$d_i=d_{m-1-i}\quad\text{以及}\quad b_j=b_{\ell-1-j}.$$
也就是说，这道题不是在寻找某种复杂递推，而是在寻找同时满足两组镜像对称条件的整数。
规范二进制表示的最高位总是 \(1\)。如果这串二进制数字还是回文，那么最低位必须和最高位相同，所以也必须是 \(1\)。而最低位正是判断奇偶性的那一位，因此任意双进制回文数都必然是奇数。
实现代码并没有专门只枚举奇数，而是直接扫描全部正整数；不过这个性质解释了为什么所有偶数都会在二进制回文测试中被自然淘汰。
因为上界是 \(10^6\)，所以十进制表示最多只有 6 位。二进制长度也很容易界定：
$$2^{19}=524288 < 10^6 < 2^{20}=1048576.$$
因此任何候选数的二进制表示都不会超过 20 位。换句话说，每次回文比较都只是在很短的字符串上进行。
如果只看十进制回文，那么小于一百万的这类数总共有
$$\sum_{k=1}^{6} 9\cdot 10^{\lceil k/2\rceil-1}=9+9+90+90+900+900=1998$$
个。这个计数本身就说明回文条件已经相当严格，再叠加二进制回文条件之后，满足要求的数会更加稀少。
题目中给出的 \(585\) 很适合作为完整例子。十进制下，
$$585=5\cdot 10^2+8\cdot 10+5,$$
对应的数字序列是 \(5,8,5\)，显然关于中心对称。
二进制下，通过不断除以 2 或按位拆解，可以得到
$$585=2^9+2^6+2^3+2^0=1001001001_2.$$
这串二进制数字从左向右和从右向左完全一致，所以 \(585\) 的确属于最终求和的集合。
理论上当然可以先只生成十进制回文，再去检查这些数的二进制形式。但这里的 C++、Python 和 Java 实现都刻意采用更直接、更容易验证正确性的路线：从 \(1\) 枚举到上界，先做十进制回文判断，再构造二进制字符串，再做一次相同的回文判断。由于题目上界只有一百万，这种做法在时间上完全没有压力。
三种语言的实现结构一致。程序支持一个可选的上界参数，默认值是 \(10^6\)，并且在正式计算之前可以选择是否执行一组很小的自检。
主循环遍历所有满足 \(1 \le n < \text{limit}\) 的整数。对于每个 \(n\)，实现先把它转成十进制字符串，然后从两端向中间比较对应字符；只要发现一对字符不同，就立刻判定十进制不是回文，不再继续处理这个 \(n\)。
如果十进制通过测试，程序会手工构造二进制表示。做法是反复读取当前最低位，把对应的字符加入序列，然后把数除以 2。经过 \(t\) 轮后，已经收集到的字符恰好是原数最低的 \(t\) 个二进制位，但顺序是从低位到高位。把这段序列反转之后，就得到没有前导零的标准二进制表示。随后再对这串二进制字符做同样的镜像比较。
只有十进制与二进制都通过时，当前数字才会加入累计总和。自检部分验证了两个已知事实：一个明显对称的字符串必须被识别为回文，而小于 \(1000\) 的所有合格数之和应当是 \(1772\)。这两个检查分别覆盖了回文判定逻辑和主求和逻辑。
设上界为 \(L\)。程序需要检查 \(1\) 到 \(L-1\) 的所有整数，因此候选数共有 \(O(L)\) 个。对每个候选数，十进制转换与十进制回文判断需要 \(O(\log_{10} L)\) 时间，二进制转换与二进制回文判断需要 \(O(\log_2 L)\) 时间，所以总时间复杂度为
$$O(L\log L).$$
辅助空间按单个候选数计算是 \(O(\log L)\)，因为实现会保存很短的十进制字符串和二进制字符串。对于本题的具体范围，这些字符串长度最多分别为 6 和 20。
Нужно найти все целые числа \(n\), для которых \(1 \le n < 10^6\), и при этом и обычная десятичная запись, и обычная двоичная запись являются палиндромами. Ответом служит сумма всех таких чисел.
Условие «без ведущих нулей» принципиально важно. В десятичной системе мы используем стандартную запись числа, а в двоичной системе только каноническое представление. Поэтому число \(10\) рассматривается как \(1010_2\), а не как \(01010_2\); только каноническая форма допускается в проверке на палиндром.
Ограничение настолько мало, что полный перебор вполне практичен. Но прежде чем обсуждать код, полезно выписать точные симметрии, которые определяют допустимые числа.
Пусть десятичная запись числа \(n\) имеет вид
$$n=d_{m-1}10^{m-1}+d_{m-2}10^{m-2}+\cdots+d_1 10+d_0,$$
где \(d_{m-1}\neq 0\). Двоичная запись имеет вид
$$n=b_{\ell-1}2^{\ell-1}+b_{\ell-2}2^{\ell-2}+\cdots+b_1 2+b_0,$$
где обязательно \(b_{\ell-1}=1\). Тогда условие палиндромности в двух системах счисления записывается как
$$d_i=d_{m-1-i}\quad\text{и}\quad b_j=b_{\ell-1-j}.$$
То есть задача сводится к поиску чисел, у которых и десятичная строка цифр, и двоичная строка битов симметричны относительно центра.
Каноническая двоичная запись всегда начинается с \(1\). Если она является палиндромом, то последний бит обязан совпадать с первым, а значит, \(b_0=1\). Но \(b_0\) и есть бит четности, следовательно, любое число, палиндромное и в базе 10, и в базе 2, обязательно нечетно.
В реализациях это наблюдение не выделено в отдельную оптимизацию: диапазон и так просматривается целиком. Однако математически оно сразу объясняет, почему ни одно четное число не может попасть в итоговую сумму.
Поскольку поиск ведется ниже \(10^6\), десятичная запись кандидата содержит не более 6 цифр. Для двоичной длины имеем
$$2^{19}=524288 < 10^6 < 2^{20}=1048576,$$
поэтому двоичная запись содержит не более 20 битов. Значит, каждая отдельная проверка палиндрома выполняется на очень коротких строках.
Если смотреть только на десятичные палиндромы, то их ниже миллиона всего
$$\sum_{k=1}^{6} 9\cdot 10^{\lceil k/2\rceil-1}=9+9+90+90+900+900=1998.$$
Это число само по себе показывает, насколько жестким уже является условие симметрии в десятичной записи.
Пример \(585\) удобен тем, что обе симметрии видны сразу. В десятичной записи
$$585=5\cdot 10^2+8\cdot 10+5,$$
поэтому последовательность цифр \(5,8,5\) читается одинаково слева направо и справа налево.
В двоичной записи получаем
$$585=2^9+2^6+2^3+2^0=1001001001_2.$$
Последовательность битов снова симметрична, так что \(585\) действительно входит в искомую сумму.
Можно было бы сначала генерировать только десятичные палиндромы, а затем проверять их двоичную форму. Но реализации на C++, Python и Java выбирают более прямой и прозрачный путь: просмотреть весь диапазон, выполнить проверку десятичной записи, затем построить двоичную запись и проверить уже ее. Для границы в один миллион этого более чем достаточно.
Во всех трех языках используется одна и та же схема. Программа принимает необязательную верхнюю границу, по умолчанию равную \(10^6\), и при желании запускает короткие контрольные проверки до основного вычисления.
Основной цикл проходит по всем \(n\) таким, что \(1 \le n < \text{limit}\). Сначала число переводится в десятичную строку, после чего сравниваются симметричные символы с начала и конца строки. Если найдено несовпадение, обработка текущего числа прекращается сразу.
Если десятичная запись прошла проверку, двоичная строка строится вручную. На каждом шаге извлекается младший бит, в последовательность добавляется соответствующий символ, а само число делится на 2. После \(t\) шагов накопленная последовательность содержит ровно \(t\) младших битов исходного числа, записанных от младшего к старшему. Разворот этой последовательности дает обычную двоичную запись без ведущих нулей. Затем к ней применяется точно такая же зеркальная проверка.
Если обе записи оказываются палиндромами, число добавляется к текущей сумме. Дополнительные контрольные проверки подтверждают два известных факта: очевидно симметричная строка должна распознаваться как палиндром, а сумма всех подходящих чисел меньше \(1000\) должна быть равна \(1772\). Тем самым отдельно проверяются и тест симметрии, и логика суммирования.
Пусть верхняя граница равна \(L\). Тогда просматриваются \(L-1\) кандидатов, то есть \(O(L)\) чисел. Для каждого из них перевод в десятичную форму и проверка десятичного палиндрома стоят \(O(\log_{10} L)\), а построение двоичной формы и ее проверка стоят \(O(\log_2 L)\). Следовательно, суммарная временная сложность равна
$$O(L\log L).$$
Дополнительная память на один кандидат равна \(O(\log L)\), потому что сохраняются короткие десятичная и двоичная строки. Для задачи с \(L=10^6\) это не более 6 и 20 символов соответственно.
نريد إيجاد كل عدد صحيح \(n\) يحقق \(1 \le n < 10^6\) بحيث تكون كتابته العشرية القياسية وكتابته الثنائية القياسية كلتاهما متناظرتين. المطلوب في النهاية هو مجموع جميع هذه الأعداد.
شرط «من دون أصفار بادئة» أساسي هنا. في النظام العشري نستخدم الكتابة المعتادة، وفي النظام الثنائي نستخدم التمثيل القياسي فقط. لذلك فالعدد \(10\) يكتب \(1010_2\) وليس \(01010_2\)، ولا يجوز اختبار التماثل إلا على هذه الصيغة القياسية.
الحد الأعلى صغير بما يكفي لكي يكون الفحص المباشر عمليًا جدًا، لكن من المفيد أولًا تحديد البنية الرياضية الدقيقة التي تجعل المسألة واضحة.
لنكتب التمثيل العشري للعدد \(n\) على الصورة
$$n=d_{m-1}10^{m-1}+d_{m-2}10^{m-2}+\cdots+d_1 10+d_0,$$
حيث \(d_{m-1}\neq 0\). ونكتب تمثيله الثنائي على الصورة
$$n=b_{\ell-1}2^{\ell-1}+b_{\ell-2}2^{\ell-2}+\cdots+b_1 2+b_0,$$
مع \(b_{\ell-1}=1\). عندئذ يكون شرط التناظر في النظامين هو
$$d_i=d_{m-1-i},\qquad b_j=b_{\ell-1-j}.$$
إذن المسألة تبحث عن أعداد تكون فيها سلسلة الأرقام العشرية وسلسلة البتات الثنائية متناظرتين حول المركز في الوقت نفسه.
بما أن التمثيل الثنائي القياسي يبدأ دائمًا بالبت \(1\)، فإن كون السلسلة الثنائية متناظرة يفرض أن يكون آخر بت مساويًا له أيضًا، أي \(b_0=1\). وهذا البت الأخير هو الذي يحدد الزوجية أو الفردية، وبالتالي فإن كل عدد متناظر في الأساسين معًا يجب أن يكون فرديًا.
التنفيذات لا تستخدم هذه الملاحظة لتقليص الحلقة بشكل صريح، لأن المرور على كامل المجال سريع أصلًا، لكنها تفسر مباشرة لماذا لا يمكن لأي عدد زوجي أن يساهم في المجموع.
لأن البحث ينتهي قبل \(10^6\)، فإن الكتابة العشرية لأي مرشح لا تتجاوز 6 خانات. أما في الثنائي فلدينا
$$2^{19}=524288 < 10^6 < 2^{20}=1048576,$$
ولذلك لا يتجاوز طول التمثيل الثنائي 20 بتًا. هذا يعني أن كل اختبار تماثل يجري على سلاسل قصيرة جدًا.
وإذا نظرنا فقط إلى المتناظرات العشرية الأقل من مليون، فإن عددها هو
$$\sum_{k=1}^{6} 9\cdot 10^{\lceil k/2\rceil-1}=9+9+90+90+900+900=1998.$$
هذا العد يبين أن شرط التناظر العشري وحده يضيق مجموعة المرشحين كثيرًا قبل إضافة الشرط الثنائي.
العدد \(585\) مثال ممتاز لأن التناظر يظهر بوضوح في النظامين. في العشري لدينا
$$585=5\cdot 10^2+8\cdot 10+5,$$
فتكون الخانات \(5,8,5\) متناظرة حول الوسط.
وفي الثنائي نحصل على
$$585=2^9+2^6+2^3+2^0=1001001001_2.$$
وسلسلة البتات هنا متناظرة أيضًا، ولذلك فإن \(585\) واحد من الأعداد التي تدخل في المجموع النهائي.
يمكن نظريًا توليد المتناظرات العشرية أولًا ثم اختبار تمثيلها الثنائي فقط. لكن تطبيقات C++ وPython وJava تختار الخوارزمية الأبسط: المرور على جميع الأعداد من \(1\) حتى الحد الأعلى، اختبار التناظر العشري، بناء التمثيل الثنائي، ثم اختبار التناظر الثنائي. ومع حد أعلى يساوي مليونًا فقط، فهذه الخطة المباشرة أكثر من كافية.
تتبع التطبيقات الثلاثة البنية نفسها. يمكن تمرير حد أعلى اختياري، والقيمة الافتراضية هي \(10^6\)، كما يمكن الإبقاء على اختبارات تحقق صغيرة قبل الحساب الكامل أو تجاوزها.
تدور الحلقة الرئيسية على كل \(n\) يحقق \(1 \le n < \text{limit}\). أولًا يُحوَّل العدد إلى سلسلة عشرية، ثم تُقارَن الخانات المتقابلة من الطرفين باتجاه المركز. إذا وُجد زوج غير متطابق يُرفض العدد فورًا.
إذا نجح الاختبار العشري، يُبنى التمثيل الثنائي يدويًا. في كل خطوة يُستخرج أقل بت أهمية، ويضاف رمزه إلى السلسلة، ثم يُقسَم العدد على 2. بعد \(t\) خطوات تكون السلسلة المجمعة قد احتوت بالضبط على أقل \(t\) بتات من العدد، لكنها تكون مرتبة من الأقل أهمية إلى الأعلى. وعند عكسها نحصل على التمثيل الثنائي القياسي من دون أصفار بادئة. بعد ذلك تُطبَّق عليها نفس مقارنة التناظر.
إذا نجح الاختباران معًا يُضاف العدد إلى المجموع التراكمي. وتتحقق اختبارات السلامة الاختيارية من حقيقتين معلومتين: أن سلسلة متناظرة معروفة يجب أن تُقبل، وأن مجموع الأعداد الصحيحة المطلوبة الأصغر من \(1000\) يساوي \(1772\). بذلك يتم فحص منطق اختبار التناظر ومنطق التجميع معًا.
إذا كان الحد الأعلى هو \(L\)، فإن التنفيذ يفحص \(L-1\) عددًا، أي \(O(L)\) مرشحًا. ولكل مرشح تحتاج عملية التحويل العشري واختبار التناظر العشري إلى \(O(\log_{10} L)\)، بينما يحتاج بناء التمثيل الثنائي واختبار تناظره إلى \(O(\log_2 L)\). لذلك يكون التعقيد الزمني الكلي
$$O(L\log L).$$
أما الذاكرة الإضافية لكل مرشح فهي \(O(\log L)\)، لأن التنفيذ يحتفظ بسلاسل عشرية وثنائية قصيرة. وفي حدود هذه المسألة تحديدًا لا يتجاوز طول هاتين السلسلتين 6 و20 محرفًا على الترتيب.