A repunit in base \(b\) is a number whose digits are all 1, such as \(111_b\) or \(11111_b\). Problem 346 asks for the sum of all strong repunits below a limit \(L\). A positive integer is called strong if it is a repunit in at least two bases \(b \gt 1\). The published sample below \(50\) is \(\{1,7,13,15,21,31,40,43\}\), so the goal is to generate exactly those values without scanning every integer below the limit.
For base \(b \ge 2\) and length \(k \ge 1\), the repunit value is
$$R_{b,k}=1+b+b^2+\cdots+b^{k-1}=\frac{b^k-1}{b-1}.$$
This is the finite geometric-series formula, and it shows immediately that for fixed \(b\), repunits grow strictly as \(k\) increases.
Every integer \(n \gt 2\) already has the trivial two-digit representation \(11_{n-1}\), because
$$11_{n-1}=(n-1)+1=n.$$
So a number is a strong repunit precisely when it has at least one additional repunit representation with \(k \ge 3\). That lets us skip all length-2 cases and enumerate only nontrivial representations. The value \(1\) is added separately because Project Euler explicitly includes it in the sample set of strong repunits.
Conversely, if \(n \gt 1\) is a strong repunit, then by definition it has some representation \(n=R_{b,k}\) with \(b \gt 1\) and \(k \ge 3\), so direct generation of all such pairs \((b,k)\) is complete.
For a fixed base \(b\), the smallest nontrivial repunit is the length-3 value
$$R_{b,3}=1+b+b^2.$$
If even this value is not below the limit, then every longer repunit in the same base is larger and can be ignored. Therefore we only need bases satisfying
$$1+b+b^2 \lt L.$$
Equivalently, \(b \le \left\lfloor\frac{\sqrt{4L-3}-1}{2}\right\rfloor\). In practice the code simply tests the inequality directly, which keeps the loop simple and safe.
After computing \(R_{b,3}\), the next repunit in the same base can be obtained without recomputing powers:
$$R_{b,k+1}=bR_{b,k}+1.$$
This follows immediately from the definition, since
$$b(1+b+\cdots+b^{k-1})+1=1+b+\cdots+b^k.$$
Operationally, multiplying by \(b\) shifts the base-\(b\) digits left, and adding 1 appends another trailing digit 1. This recurrence is the key reason the algorithm is fast.
The admissible bases are those with \(1+b+b^2 \lt 50\), namely \(b=2,3,4,5,6\).
Base \(2\) gives \(7,15,31\). Base \(3\) gives \(13,40\). Base \(4\) gives \(21\). Base \(5\) gives \(31\) again. Base \(6\) gives \(43\). For \(b=7\), we already have \(1+7+49=57 \ge 50\), so the enumeration stops.
After deduplication and after inserting \(1\), the set is
$$\{1,7,13,15,21,31,40,43\},$$
exactly the sample from the statement. The duplicate \(31\) is a useful sanity check: \(31=11111_2=111_5\).
The implementation first inserts \(1\) when \(L \gt 1\). Then it loops over bases starting from \(2\). The C++ and Java versions defensively stop if \(b^2\) could overflow, while the main structural stop condition is \(1+b+b^2 \ge L\).
For each base, the code starts with \(R_{b,3}\), repeatedly applies repunit = repunit * base + 1, and records every value below the limit. Before the multiplication, it checks whether repunit > (L-1)/base; if so, the next recurrence step would exceed the safe range, so the inner loop ends.
Because different \((b,k)\) pairs can yield the same number, the generated values must be deduplicated. The C++ version pushes candidates into a vector and later uses sort plus unique; the Python and Java versions use sets during generation and then sort the final collection before summing. The C++ file also includes checkpoints for the published examples: the list below \(50\) and the sum \(15864\) below \(1000\).
The outer loop runs for only \(O(\sqrt{L})\) bases. For each fixed base \(b\), the recurrence produces about \(O(\log_b L)\) repunits before crossing the limit. Hence the total work is
$$\sum_{b=2}^{O(\sqrt{L})} O(\log_b L),$$
which is far smaller than testing all integers below \(L\). Memory usage is \(O(M)\), where \(M\) is the number of generated candidate values before or during deduplication.
Ein Repunit zur Basis \(b\) ist eine Zahl, deren Zifferndarstellung nur aus Einsen besteht, etwa \(111_b\) oder \(11111_b\). Problem 346 verlangt die Summe aller starken Repunits unter einer Schranke \(L\). Eine positive ganze Zahl heißt stark, wenn sie in mindestens zwei Basen \(b \gt 1\) ein Repunit ist. Die veröffentlichte Beispielmenge unter \(50\) lautet \(\{1,7,13,15,21,31,40,43\}\); genau diese Werte soll der Algorithmus erzeugen, ohne alle Zahlen unterhalb der Schranke einzeln zu testen.
Für Basis \(b \ge 2\) und Länge \(k \ge 1\) hat ein Repunit den Wert
$$R_{b,k}=1+b+b^2+\cdots+b^{k-1}=\frac{b^k-1}{b-1}.$$
Das ist die endliche geometrische Reihe; zugleich sieht man sofort, dass für festes \(b\) die Werte mit wachsender Länge \(k\) streng ansteigen.
Jede Zahl \(n \gt 2\) besitzt bereits die triviale zweistellige Darstellung \(11_{n-1}\), denn
$$11_{n-1}=(n-1)+1=n.$$
Eine Zahl ist also genau dann ein starkes Repunit, wenn sie mindestens eine zusätzliche Repunit-Darstellung mit \(k \ge 3\) besitzt. Deshalb kann die Suche alle Fälle der Länge 2 überspringen und nur nichttriviale Darstellungen erzeugen. Der Wert \(1\) wird separat hinzugefügt, weil Project Euler ihn in der Beispielmenge ausdrücklich mitzählt.
Umgekehrt gilt: Ist \(n \gt 1\) ein starkes Repunit, dann existiert definitionsgemäß eine Darstellung \(n=R_{b,k}\) mit \(b \gt 1\) und \(k \ge 3\). Das direkte Erzeugen aller solchen Paare \((b,k)\) ist daher vollständig.
Für eine feste Basis \(b\) ist das kleinste nichttriviale Repunit der Wert der Länge 3:
$$R_{b,3}=1+b+b^2.$$
Liegt bereits dieser Wert nicht unter der Schranke, dann sind alle längeren Repunits derselben Basis noch größer und damit irrelevant. Also müssen nur Basen betrachtet werden, für die
$$1+b+b^2 \lt L$$
gilt. Äquivalent dazu ist \(b \le \left\lfloor\frac{\sqrt{4L-3}-1}{2}\right\rfloor\). Der Code berechnet diese Formel jedoch nicht explizit, sondern prüft die Ungleichung direkt.
Sobald \(R_{b,3}\) bekannt ist, kann das nächste Repunit derselben Basis ohne erneutes Potenzieren erzeugt werden:
$$R_{b,k+1}=bR_{b,k}+1.$$
Das folgt unmittelbar aus der Definition, denn
$$b(1+b+\cdots+b^{k-1})+1=1+b+\cdots+b^k.$$
Anschaulich verschiebt die Multiplikation mit \(b\) die Basis-\(b\)-Ziffern um eine Stelle nach links, und das anschließende \(+1\) hängt rechts eine weitere Eins an. Genau diese Rekurrenz macht die Implementierung effizient.
Zulässig sind genau die Basen mit \(1+b+b^2 \lt 50\), also \(b=2,3,4,5,6\).
Basis \(2\) liefert \(7,15,31\). Basis \(3\) liefert \(13,40\). Basis \(4\) liefert \(21\). Basis \(5\) liefert nochmals \(31\). Basis \(6\) liefert \(43\). Für \(b=7\) gilt bereits \(1+7+49=57 \ge 50\), also endet die Enumeration dort.
Nach dem Entfernen von Duplikaten und dem zusätzlichen Einfügen von \(1\) erhält man
$$\{1,7,13,15,21,31,40,43\},$$
also exakt die Beispielmenge aus der Aufgabenstellung. Das doppelte Auftreten von \(31\) ist ein guter Plausibilitätstest: \(31=11111_2=111_5\).
Die Implementierung fügt zuerst \(1\) ein, falls \(L \gt 1\). Danach werden die Basen beginnend bei \(2\) durchlaufen. Die C++- und Java-Versionen brechen vorsorglich ab, falls \(b^2\) überlaufen könnte; die eigentliche strukturelle Abbruchbedingung ist jedoch \(1+b+b^2 \ge L\).
Für jede Basis startet der Code mit \(R_{b,3}\), wendet wiederholt repunit = repunit * base + 1 an und speichert alle Werte unterhalb der Schranke. Vor der Multiplikation prüft er, ob repunit > (L-1)/base gilt; dann würde der nächste Rekurrenzschritt den sicheren Bereich überschreiten, also endet die innere Schleife.
Da verschiedene Paare \((b,k)\) dieselbe Zahl erzeugen können, müssen die Kandidaten dedupliziert werden. Die C++-Version sammelt sie zunächst in einem Vektor und verwendet danach sort plus unique; Python und Java verwenden schon während der Erzeugung Mengen und sortieren erst die Endmenge vor dem Summieren. Die C++-Datei enthält außerdem Kontrolltests für die publizierten Beispiele: die Liste unter \(50\) und die Summe \(15864\) unter \(1000\).
Die äußere Schleife besucht nur \(O(\sqrt{L})\) Basen. Für eine feste Basis \(b\) erzeugt die Rekurrenz ungefähr \(O(\log_b L)\) Repunits, bevor die Schranke überschritten wird. Damit ergibt sich insgesamt
$$\sum_{b=2}^{O(\sqrt{L})} O(\log_b L),$$
also deutlich weniger Arbeit als ein Test aller Zahlen unter \(L\). Der Speicherverbrauch ist \(O(M)\), wobei \(M\) die Anzahl der erzeugten Kandidaten vor oder während der Deduplikation bezeichnet.
Taban \(b\)'de bir repunit, tüm basamakları 1 olan sayıdır; örneğin \(111_b\) veya \(11111_b\). Problem 346, üst sınır \(L\) altındaki tüm güçlü repunit sayıların toplamını ister. Bir pozitif tamsayı, \(1\)'den büyük en az iki farklı tabanda repunit olarak yazılabiliyorsa güçlü kabul edilir. Sorudaki \(50\) altı örnek küme \(\{1,7,13,15,21,31,40,43\}\) olduğuna göre amaç, limit altındaki her sayıyı tek tek denemeden tam olarak bu değerleri üretebilmektir.
Taban \(b \ge 2\) ve uzunluk \(k \ge 1\) için repunit değeri
$$R_{b,k}=1+b+b^2+\cdots+b^{k-1}=\frac{b^k-1}{b-1}.$$
Bu, sonlu geometrik seri formülüdür. Aynı zamanda sabit bir \(b\) için, \(k\) arttıkça repunit değerlerinin sıkı biçimde büyüdüğünü de gösterir.
Her \(n \gt 2\) sayısı zaten şu önemsiz iki basamaklı gösterime sahiptir:
$$11_{n-1}=(n-1)+1=n.$$
Dolayısıyla bir sayının güçlü repunit olması, en az bir tane daha \(k \ge 3\) uzunluklu repunit gösterimine sahip olması demektir. Bu yüzden arama sırasında uzunluk 2 olan tüm durumlar atlanabilir; yalnızca önemsiz olmayan temsiller üretilir. \(1\) değeri ayrıca eklenir, çünkü Project Euler problem metnindeki örnek kümede \(1\)'i açıkça dahil eder.
Ters yönde de şu doğrudur: \(n \gt 1\) güçlü bir repunit ise tanım gereği \(n=R_{b,k}\) olacak şekilde \(b \gt 1\) ve \(k \ge 3\) vardır. Yani tüm böyle \((b,k)\) çiftlerini üretmek eksiksiz bir tarama yapar.
Sabit bir \(b\) tabanı için en küçük önemsiz repunit, uzunluk 3 olan değerdir:
$$R_{b,3}=1+b+b^2.$$
Eğer bu değer bile limitin altına düşmüyorsa, aynı tabandaki daha uzun repunitlerin hepsi daha büyük olacağı için o tabanı tamamen atlayabiliriz. Bu nedenle yalnızca
$$1+b+b^2 \lt L$$
eşitsizliğini sağlayan tabanlara bakmak yeterlidir. Eşdeğer olarak \(b \le \left\lfloor\frac{\sqrt{4L-3}-1}{2}\right\rfloor\) elde edilir. Kod bu kapalı formu hesaplamak yerine eşitsizliği doğrudan kontrol eder.
\(R_{b,3}\) bulunduktan sonra, aynı tabandaki sonraki repunit değeri üsleri yeniden hesaplamadan üretilebilir:
$$R_{b,k+1}=bR_{b,k}+1.$$
Bu bağıntı doğrudan tanımdan gelir; çünkü
$$b(1+b+\cdots+b^{k-1})+1=1+b+\cdots+b^k.$$
İşlemsel olarak bakıldığında \(b\) ile çarpmak taban-\(b\) gösterimini sola kaydırır, sonradan eklenen \(+1\) ise sağa yeni bir 1 basamağı iliştirir. Algoritmanın hızlı olmasının ana nedeni bu yinelemedir.
\(1+b+b^2 \lt 50\) koşulunu sağlayan tabanlar yalnızca \(b=2,3,4,5,6\) değerleridir.
Taban \(2\): \(7,15,31\). Taban \(3\): \(13,40\). Taban \(4\): \(21\). Taban \(5\): yeniden \(31\). Taban \(6\): \(43\). \(b=7\) için ise \(1+7+49=57 \ge 50\) olduğundan arama burada biter.
Tekrarlı değerler çıkarılıp \(1\) de eklendiğinde küme
$$\{1,7,13,15,21,31,40,43\},$$
yani problem metnindeki örnekle tam olarak aynıdır. Buradaki \(31\) tekrarı iyi bir kontrol örneğidir: \(31=11111_2=111_5\).
Uygulama önce \(L \gt 1\) ise \(1\)'i ekler. Sonra tabanlar \(2\)'den başlayarak denenir. C++ ve Java sürümleri, \(b^2\) hesabında taşma ihtimali oluşursa savunmacı biçimde durur; asıl yapısal durma koşulu ise \(1+b+b^2 \ge L\) olmasıdır.
Her taban için kod \(R_{b,3}\) ile başlar, tekrar tekrar repunit = repunit * base + 1 uygular ve limit altındaki her değeri kaydeder. Çarpımdan önce repunit > (L-1)/base kontrolü yapılır; bu doğruysa bir sonraki yineleme adımı güvenli aralığı aşacağından iç döngü sonlandırılır.
Farklı \((b,k)\) çiftleri aynı sayıyı verebildiği için değerlerin tekilleştirilmesi gerekir. C++ sürümü adayları önce bir vektöre atar, sonra sıralayıp unique uygular; Python ve Java ise üretim sırasında kümeler kullanır, ardından son koleksiyonu sıralayıp toplar. C++ dosyasında ayrıca yayınlanmış örnekleri doğrulayan kontroller bulunur: \(50\) altındaki liste ve \(1000\) altındaki \(15864\) toplamı.
Dış döngü yalnızca \(O(\sqrt{L})\) kadar taban gezer. Sabit bir \(b\) tabanı için yineleme, limit aşılana kadar yaklaşık \(O(\log_b L)\) repunit üretir. Böylece toplam iş yükü
$$\sum_{b=2}^{O(\sqrt{L})} O(\log_b L),$$
olur; bu da \(L\) altındaki tüm sayıları denemekten çok daha küçüktür. Bellek kullanımı \(O(M)\)'dir; burada \(M\), tekilleştirme öncesinde ya da tekilleştirme sırasında üretilen aday değer sayısını gösterir.
Un repunit en base \(b\) es un número cuya representación tiene solo dígitos 1, como \(111_b\) o \(11111_b\). El problema 346 pide la suma de todos los repunits fuertes menores que un límite \(L\). Un entero positivo se llama fuerte si es repunit en al menos dos bases \(b \gt 1\). El ejemplo publicado por debajo de \(50\) es \(\{1,7,13,15,21,31,40,43\}\), así que el objetivo es generar exactamente esos valores sin probar uno por uno todos los enteros menores que el límite.
Para base \(b \ge 2\) y longitud \(k \ge 1\), el valor de un repunit es
$$R_{b,k}=1+b+b^2+\cdots+b^{k-1}=\frac{b^k-1}{b-1}.$$
Esta es la fórmula de la serie geométrica finita, y muestra de inmediato que, para una base fija \(b\), los repunits crecen estrictamente cuando aumenta \(k\).
Todo entero \(n \gt 2\) ya tiene la representación trivial de dos dígitos \(11_{n-1}\), porque
$$11_{n-1}=(n-1)+1=n.$$
Por tanto, un número es un repunit fuerte exactamente cuando tiene al menos otra representación repunit con \(k \ge 3\). Eso permite ignorar todos los casos de longitud 2 y enumerar solo las representaciones no triviales. El valor \(1\) se añade aparte porque Project Euler lo incluye explícitamente en el conjunto de ejemplo.
En sentido inverso, si \(n \gt 1\) es un repunit fuerte, entonces por definición existe una representación \(n=R_{b,k}\) con \(b \gt 1\) y \(k \ge 3\); por ello, generar todos esos pares \((b,k)\) cubre todos los casos posibles.
Para una base fija \(b\), el menor repunit no trivial es el de longitud 3:
$$R_{b,3}=1+b+b^2.$$
Si ni siquiera este valor queda por debajo del límite, entonces cualquier repunit más largo en la misma base será aún mayor. Por eso solo hace falta considerar bases que cumplan
$$1+b+b^2 \lt L.$$
De forma equivalente, \(b \le \left\lfloor\frac{\sqrt{4L-3}-1}{2}\right\rfloor\). En la práctica, el código no usa esa fórmula cerrada y se limita a comprobar la desigualdad directamente.
Una vez calculado \(R_{b,3}\), el siguiente repunit en la misma base se obtiene sin volver a calcular potencias:
$$R_{b,k+1}=bR_{b,k}+1.$$
Esto sale directamente de la definición, ya que
$$b(1+b+\cdots+b^{k-1})+1=1+b+\cdots+b^k.$$
En términos operativos, multiplicar por \(b\) desplaza la representación en base \(b\) una posición a la izquierda y sumar 1 añade otro dígito final 1. Esta recurrencia es la optimización central del algoritmo.
Las bases admisibles son las que satisfacen \(1+b+b^2 \lt 50\), es decir, \(b=2,3,4,5,6\).
La base \(2\) produce \(7,15,31\). La base \(3\) produce \(13,40\). La base \(4\) produce \(21\). La base \(5\) vuelve a producir \(31\). La base \(6\) produce \(43\). Para \(b=7\), ya se tiene \(1+7+49=57 \ge 50\), así que la enumeración termina.
Tras eliminar duplicados y añadir \(1\), el conjunto es
$$\{1,7,13,15,21,31,40,43\},$$
exactamente el ejemplo del enunciado. El duplicado \(31\) es una buena comprobación: \(31=11111_2=111_5\).
La implementación añade primero \(1\) si \(L \gt 1\). Después recorre las bases a partir de \(2\). Las versiones en C++ y Java se detienen de forma defensiva si \(b^2\) pudiera desbordarse; la condición estructural principal de parada es \(1+b+b^2 \ge L\).
Para cada base, el código empieza en \(R_{b,3}\), aplica repetidamente repunit = repunit * base + 1 y guarda todos los valores menores que el límite. Antes de multiplicar, comprueba si repunit > (L-1)/base; en ese caso, el siguiente paso de la recurrencia saldría del rango seguro y se corta el bucle interno.
Como distintos pares \((b,k)\) pueden producir el mismo entero, es necesario eliminar duplicados. La versión C++ guarda los candidatos en un vector y luego usa sort más unique; Python y Java emplean conjuntos durante la generación y ordenan la colección final antes de sumar. El archivo C++ también incorpora comprobaciones para los ejemplos publicados: la lista bajo \(50\) y la suma \(15864\) bajo \(1000\).
El bucle exterior recorre solo \(O(\sqrt{L})\) bases. Para una base fija \(b\), la recurrencia genera alrededor de \(O(\log_b L)\) repunits antes de superar el límite. Por tanto, el trabajo total es
$$\sum_{b=2}^{O(\sqrt{L})} O(\log_b L),$$
muy inferior a comprobar todos los enteros menores que \(L\). El uso de memoria es \(O(M)\), donde \(M\) es el número de candidatos generados antes o durante la deduplicación.
在基数 \(b\) 下，repunit 是各位数字都为 1 的数，例如 \(111_b\) 或 \(11111_b\)。第 346 题要求求出所有小于上界 \(L\) 的强 repunit 之和。一个正整数如果能在至少两个大于 1 的进制中写成 repunit，就称为强 repunit。题目给出的 \(50\) 以下样例集合是 \(\{1,7,13,15,21,31,40,43\}\)，因此我们的目标是在不枚举所有小于 \(L\) 的整数的前提下，精确生成这些数。
对基数 \(b \ge 2\)、长度 \(k \ge 1\)，repunit 的数值为
$$R_{b,k}=1+b+b^2+\cdots+b^{k-1}=\frac{b^k-1}{b-1}.$$
这就是有限等比数列求和公式，同时也说明：在固定基数 \(b\) 时，repunit 会随着长度 \(k\) 的增加而严格增大。
任何 \(n \gt 2\) 都已经有一个平凡的两位表示 \(11_{n-1}\)，因为
$$11_{n-1}=(n-1)+1=n.$$
所以，一个数是强 repunit，当且仅当它还至少存在一个长度 \(k \ge 3\) 的 repunit 表示。这意味着搜索时可以完全跳过长度 2 的情况，只生成非平凡表示。数值 \(1\) 需要单独加入，因为 Project Euler 在样例强 repunit 集合中明确把它算进去了。
反过来说，如果 \(n \gt 1\) 是强 repunit，那么按定义必然存在某个 \(b \gt 1\)、\(k \ge 3\)，使得 \(n=R_{b,k}\)。因此，直接枚举所有这样的 \((b,k)\) 对是完备的。
对固定基数 \(b\)，最小的非平凡 repunit 是长度为 3 的值
$$R_{b,3}=1+b+b^2.$$
如果这个值都已经不小于上界，那么同一基数下更长的 repunit 只会更大，因此该基数可以整体跳过。于是只需考虑满足
$$1+b+b^2 \lt L$$
的基数。等价地，\(b \le \left\lfloor\frac{\sqrt{4L-3}-1}{2}\right\rfloor\)。实际代码并不会显式计算这个闭式上界，而是直接检查上述不等式。
一旦算出 \(R_{b,3}\)，同一基数下的下一个 repunit 就不必重新计算幂：
$$R_{b,k+1}=bR_{b,k}+1.$$
这直接来自定义，因为
$$b(1+b+\cdots+b^{k-1})+1=1+b+\cdots+b^k.$$
从进制表示的角度看，乘以 \(b\) 相当于把基数 \(b\) 表示整体左移一位，再加 1 就在末尾补上一个新的数字 1。这正是算法高效的核心。
满足 \(1+b+b^2 \lt 50\) 的基数只有 \(b=2,3,4,5,6\)。
基数 \(2\) 产生 \(7,15,31\)；基数 \(3\) 产生 \(13,40\)；基数 \(4\) 产生 \(21\)；基数 \(5\) 再次产生 \(31\)；基数 \(6\) 产生 \(43\)。当 \(b=7\) 时，已经有 \(1+7+49=57 \ge 50\)，因此枚举到此结束。
去重并补上 \(1\) 之后，得到集合
$$\{1,7,13,15,21,31,40,43\},$$
与题目样例完全一致。重复出现的 \(31\) 是一个很好的校验点：\(31=11111_2=111_5\)。
实现首先在 \(L \gt 1\) 时加入 \(1\)。随后从基数 \(2\) 开始循环。C++ 和 Java 版本会额外做防御性检查，避免 \(b^2\) 发生溢出；真正决定停止外层循环的结构条件是 \(1+b+b^2 \ge L\)。
对于每个基数，代码从 \(R_{b,3}\) 出发，反复执行 repunit = repunit * base + 1，并记录所有小于上界的值。在乘法之前，它会先检查 repunit > (L-1)/base；如果成立，说明下一次递推会超出安全范围，因此内层循环结束。
由于不同的 \((b,k)\) 可能生成同一个整数，所以必须去重。C++ 版本先把候选值存入向量，再排序并调用 unique；Python 和 Java 则在生成阶段直接使用集合，最后再对结果排序求和。C++ 文件还包含题目公开样例的检查：\(50\) 以下的列表，以及 \(1000\) 以下总和 \(15864\)。
外层循环只需要遍历 \(O(\sqrt{L})\) 个基数。对于固定基数 \(b\)，递推在超过上界之前大约会生成 \(O(\log_b L)\) 个 repunit。因此总工作量为
$$\sum_{b=2}^{O(\sqrt{L})} O(\log_b L),$$
远小于逐个检查所有小于 \(L\) 的整数。空间复杂度为 \(O(M)\)，其中 \(M\) 是去重之前或去重过程中生成的候选值数量。
Repunit в системе счисления с основанием \(b\) - это число, запись которого состоит только из единиц, например \(111_b\) или \(11111_b\). В задаче 346 требуется найти сумму всех сильных repunit, меньших заданной границы \(L\). Положительное целое число называется сильным, если оно является repunit хотя бы в двух основаниях \(b \gt 1\). Опубликованный пример для чисел меньше \(50\) равен \(\{1,7,13,15,21,31,40,43\}\), значит алгоритм должен получать именно это множество, не перебирая все числа по одному.
Для основания \(b \ge 2\) и длины \(k \ge 1\) значение repunit равно
$$R_{b,k}=1+b+b^2+\cdots+b^{k-1}=\frac{b^k-1}{b-1}.$$
Это формула суммы конечной геометрической прогрессии. Она сразу показывает, что при фиксированном \(b\) значения repunit строго возрастают с ростом длины \(k\).
Любое число \(n \gt 2\) уже имеет тривиальное двузначное представление \(11_{n-1}\), поскольку
$$11_{n-1}=(n-1)+1=n.$$
Следовательно, число является сильным repunit тогда и только тогда, когда у него есть хотя бы еще одно представление repunit длины \(k \ge 3\). Поэтому можно полностью отбросить все случаи длины 2 и перечислять только нетривиальные представления. Значение \(1\) добавляется отдельно, потому что Project Euler явно включает его в примерный набор сильных repunit.
В обратную сторону рассуждение тоже верно: если \(n \gt 1\) является сильным repunit, то по определению существует представление \(n=R_{b,k}\) для некоторых \(b \gt 1\) и \(k \ge 3\). Значит, прямое перечисление всех таких пар \((b,k)\) является полным.
Для фиксированного основания \(b\) наименьший нетривиальный repunit имеет длину 3:
$$R_{b,3}=1+b+b^2.$$
Если даже это значение не меньше границы, то любой более длинный repunit в том же основании будет еще больше. Поэтому нужно рассматривать только основания, удовлетворяющие
$$1+b+b^2 \lt L.$$
Эквивалентно, \(b \le \left\lfloor\frac{\sqrt{4L-3}-1}{2}\right\rfloor\). На практике код не вычисляет эту формулу явно, а просто проверяет неравенство напрямую.
После вычисления \(R_{b,3}\) следующий repunit в том же основании можно получить без повторного вычисления степеней:
$$R_{b,k+1}=bR_{b,k}+1.$$
Это напрямую следует из определения, потому что
$$b(1+b+\cdots+b^{k-1})+1=1+b+\cdots+b^k.$$
С точки зрения записи числа умножение на \(b\) сдвигает цифры в системе счисления с основанием \(b\) влево, а добавление 1 приписывает еще одну конечную единицу. Именно эта рекурсия делает алгоритм быстрым.
Условию \(1+b+b^2 \lt 50\) удовлетворяют только основания \(b=2,3,4,5,6\).
Основание \(2\) дает \(7,15,31\). Основание \(3\) дает \(13,40\). Основание \(4\) дает \(21\). Основание \(5\) снова дает \(31\). Основание \(6\) дает \(43\). Для \(b=7\) уже имеем \(1+7+49=57 \ge 50\), поэтому перебор заканчивается.
После удаления повторов и добавления \(1\) получаем
$$\{1,7,13,15,21,31,40,43\},$$
то есть ровно пример из условия. Повтор числа \(31\) служит хорошей проверкой: \(31=11111_2=111_5\).
Сначала реализация добавляет \(1\), если \(L \gt 1\). Затем она перебирает основания, начиная с \(2\). Версии на C++ и Java дополнительно делают защитную проверку, чтобы вычисление \(b^2\) не переполнило тип; главная структурная остановка внешнего цикла - это условие \(1+b+b^2 \ge L\).
Для каждого основания код стартует с \(R_{b,3}\), многократно применяет repunit = repunit * base + 1 и сохраняет все значения ниже границы. Перед умножением он проверяет условие repunit > (L-1)/base; если оно выполнено, следующий шаг рекурсии выйдет за безопасный диапазон, и внутренний цикл завершается.
Поскольку разные пары \((b,k)\) могут порождать одно и то же число, требуется удаление дублей. В версии C++ кандидаты сначала складываются в вектор, затем сортируются и пропускаются через unique; Python и Java используют множества уже на этапе генерации и сортируют итоговую коллекцию перед суммированием. В C++-файле также есть проверки для опубликованных примеров: список ниже \(50\) и сумма \(15864\) ниже \(1000\).
Внешний цикл проходит только по \(O(\sqrt{L})\) основаниям. Для фиксированного основания \(b\) рекурсия порождает примерно \(O(\log_b L)\) repunit до выхода за предел \(L\). Следовательно, общий объем работы равен
$$\sum_{b=2}^{O(\sqrt{L})} O(\log_b L),$$
что намного меньше, чем проверять все числа ниже \(L\). Память составляет \(O(M)\), где \(M\) - число сгенерированных кандидатов до или во время удаления дублей.
الـ repunit في أساس \(b\) هو عدد كل خاناته 1، مثل \(111_b\) أو \(11111_b\). تطلب المسألة 346 إيجاد مجموع جميع الأعداد القوية من هذا النوع الأصغر من حد \(L\). ويُسمى العدد الصحيح الموجب قويًا إذا كان repunit في قاعدتين على الأقل أكبر من 1. المثال المنشور للأعداد الأصغر من \(50\) هو \(\{1,7,13,15,21,31,40,43\}\)، ولذلك يجب أن يولد الحل هذه القيم نفسها من غير فحص كل عدد أقل من الحد واحدًا واحدًا.
لأساس \(b \ge 2\) وطول \(k \ge 1\)، تكون قيمة repunit هي
$$R_{b,k}=1+b+b^2+\cdots+b^{k-1}=\frac{b^k-1}{b-1}.$$
هذه هي صيغة مجموع المتسلسلة الهندسية المنتهية، وهي توضح مباشرة أنه عند تثبيت الأساس \(b\)، فإن قيم repunit تزداد بصرامة كلما ازداد الطول \(k\).
كل عدد \(n \gt 2\) يملك أصلًا التمثيل التافه ذي الخانتين \(11_{n-1}\)، لأن
$$11_{n-1}=(n-1)+1=n.$$
إذن يكون العدد repunit قويًا إذا وفقط إذا امتلك تمثيل repunit إضافيًا واحدًا على الأقل بطول \(k \ge 3\). وهذا يسمح لنا بتجاهل جميع الحالات ذات الطول 2 وتوليد التمثيلات غير التافهة فقط. وتُضاف القيمة \(1\) على نحو منفصل لأن Project Euler يضمها صراحة في مجموعة المثال.
وبالعكس، إذا كان \(n \gt 1\) repunit قويًا، فبحسب التعريف توجد كتابة من الشكل \(n=R_{b,k}\) لبعض \(b \gt 1\) و\(k \ge 3\). لذلك فإن توليد جميع الأزواج \((b,k)\) من هذا النوع يغطي جميع الحالات الممكنة.
لأساس ثابت \(b\)، أصغر repunit غير تافه هو القيمة ذات الطول 3:
$$R_{b,3}=1+b+b^2.$$
إذا كانت هذه القيمة نفسها لا تقع تحت الحد، فإن كل repunit أطول في الأساس نفسه سيكون أكبر منها، وبالتالي يمكن تجاهل هذا الأساس بالكامل. لذا يكفي أن ننظر إلى الأسس التي تحقق
$$1+b+b^2 \lt L.$$
وبصورة مكافئة، \(b \le \left\lfloor\frac{\sqrt{4L-3}-1}{2}\right\rfloor\). عمليًا لا يحسب الكود هذا الحد المغلق صراحة، بل يختبر المتباينة مباشرة.
بعد حساب \(R_{b,3}\)، يمكن الحصول على repunit التالي في الأساس نفسه من غير إعادة حساب القوى:
$$R_{b,k+1}=bR_{b,k}+1.$$
وهذا ينتج مباشرة من التعريف، لأن
$$b(1+b+\cdots+b^{k-1})+1=1+b+\cdots+b^k.$$
ومن زاوية التمثيل العددي، فإن الضرب في \(b\) يزيح الخانات في الأساس \(b\) خانة إلى اليسار، ثم تضيف \(+1\) خانة أخيرة قيمتها 1. وهذه العلاقة هي جوهر السرعة في الخوارزمية.
الأسس المسموح بها هي فقط تلك التي تحقق \(1+b+b^2 \lt 50\)، أي \(b=2,3,4,5,6\).
الأساس \(2\) يعطي \(7,15,31\). والأساس \(3\) يعطي \(13,40\). والأساس \(4\) يعطي \(21\). والأساس \(5\) يعطي \(31\) مرة أخرى. والأساس \(6\) يعطي \(43\). أما عند \(b=7\) فنحصل بالفعل على \(1+7+49=57 \ge 50\)، لذا يتوقف التعداد عند هذه النقطة.
بعد إزالة التكرارات وإضافة \(1\)، تصبح المجموعة
$$\{1,7,13,15,21,31,40,43\},$$
وهي تمامًا مجموعة المثال في نص المسألة. وتكرار \(31\) اختبار جيد للصحة: \(31=11111_2=111_5\).
تبدأ الخوارزمية بإضافة \(1\) إذا كان \(L \gt 1\). ثم تمر على الأسس ابتداءً من \(2\). وتضيف نسختا C++ وJava فحصًا دفاعيًا لتجنب فيض \(b^2\)، بينما يبقى شرط التوقف البنيوي الأساسي هو \(1+b+b^2 \ge L\).
لكل أساس يبدأ الكود من \(R_{b,3}\)، ثم يكرر العملية repunit = repunit * base + 1 ويسجل كل قيمة أصغر من الحد. وقبل الضرب يفحص الشرط repunit > (L-1)/base؛ فإذا تحقق، فهذا يعني أن خطوة التكرار التالية ستتجاوز المجال الآمن، فتتوقف الحلقة الداخلية.
ولأن الأزواج المختلفة \((b,k)\) قد تنتج العدد نفسه، فلا بد من إزالة التكرارات. نسخة C++ تجمع القيم أولًا في متجه ثم تطبق sort وunique، بينما تستخدم Python وJava مجموعات أثناء التوليد ثم ترتبان المجموعة النهائية قبل الجمع. كما يتضمن ملف C++ اختبارات تحقق للأمثلة المنشورة: القائمة تحت \(50\) والمجموع \(15864\) تحت \(1000\).
الحلقة الخارجية تمر على \(O(\sqrt{L})\) من الأسس فقط. وبالنسبة إلى أساس ثابت \(b\)، تنتج العلاقة التكرارية نحو \(O(\log_b L)\) من قيم repunit قبل تجاوز الحد. لذلك يكون العمل الكلي
$$\sum_{b=2}^{O(\sqrt{L})} O(\log_b L),$$
وهو أقل بكثير من اختبار جميع الأعداد الأصغر من \(L\). أما استهلاك الذاكرة فهو \(O(M)\)، حيث تمثل \(M\) عدد القيم المرشحة المولدة قبل إزالة التكرار أو أثناءها.