For a positive integer \(n\), let \(s(n)\) denote the sum of its proper divisors. A number is called abundant when \(s(n) \gt n\). The task is to add all positive integers that cannot be written as \(a+b\) with both \(a\) and \(b\) abundant.
The crucial reduction is given in the problem statement itself: every integer greater than \(28123\) can be written as the sum of two abundant numbers. Therefore the computation only needs the finite interval \(1 \le n \le L\) with \(L=28123\).
The solution has two mathematical ingredients. First, classify every integer up to \(L\) by its proper-divisor sum. Second, build the set of all sums of two abundant numbers up to the same limit. Once those reachable sums are known, the answer is just the sum of the numbers that were never reached.
Define the aliquot sum by
$$s(n)=\sum_{\substack{d \mid n \\ 1 \le d \lt n}} d.$$
Then \(n\) is deficient if \(s(n) \lt n\), perfect if \(s(n)=n\), and abundant if \(s(n) \gt n\). The first abundant number is \(12\), because
$$s(12)=1+2+3+4+6=16 \gt 12.$$
This already gives one useful observation: no integer below \(24\) can be a sum of two abundant numbers, since the smallest possible such sum is \(12+12\).
Let
$$A=\{a\in\{1,2,\dots,L\}: s(a)\gt a\}$$
be the set of abundant numbers up to the search limit. We only care whether a value \(n\le L\) belongs to
$$E=(A+A)\cap\{1,2,\dots,L\}=\{a_i+a_j:\ a_i,a_j\in A,\ a_i+a_j\le L\}.$$
The requested total is therefore
$$\sum_{\substack{1 \le n \le L \\ n\notin E}} n.$$
That formula is the whole problem in compact form: build \(A\), mark every element of \(E\), and add the integers that remain outside \(E\).
The implementations do not factor each number independently. Instead, they use a divisor sieve. For each possible proper divisor \(d\), add \(d\) to every multiple \(2d,3d,4d,\dots\le L\). When this process finishes, the entry at position \(n\) has received exactly the contribution of every proper divisor of \(n\), so it equals \(s(n)\).
The running time of this phase is controlled by the harmonic series:
$$\sum_{d=1}^{\lfloor L/2 \rfloor}\left\lfloor \frac{L}{d}\right\rfloor = O(L\log L).$$
For \(L=28123\), this preprocessing is small enough that a simple array-based sieve is entirely sufficient.
After the sieve, the abundant numbers are collected in increasing order. Suppose we fix one abundant number \(a_i\) and then try partners \(a_j\) with \(j\ge i\). Because the list is sorted, the sums \(a_i+a_j\) grow as \(j\) grows. Therefore, once \(a_i+a_j\gt L\), every later partner also produces a sum above \(L\), so the inner scan can stop immediately.
This monotonicity is the key invariant behind the second phase. It means the algorithm never examines useless pairs beyond the search limit, even though it still conceptually explores the sumset \(A+A\).
Up to \(25\), the abundant numbers are \(12,18,20,24\). The first reachable sum is
$$12+12=24.$$
The next partner already gives
$$12+18=30 \gt 25,$$
so there is no reason to test \(12+20\) or \(12+24\) when the limit is \(25\). Thus \(24\) is marked as expressible, while \(25\) is never marked and must be included in the final answer.
The C++, Python, and Java implementations allocate an integer table of length \(L+1\) and fill it by the divisor sieve. A single left-to-right pass over that table then identifies every abundant number from \(12\) to \(L\). Because this pass is increasing, the abundant list is automatically sorted.
A Boolean table indexed by \(0,1,\dots,L\) records whether a number can be written as the sum of two abundant numbers. The implementations loop over abundant pairs with the second index starting at the first, so each unordered pair is handled once. If the sum stays within the limit, the Boolean entry is marked; if the sum exceeds the limit, the inner loop breaks immediately.
The final pass simply adds all \(n\) with \(1 \le n \le L\) whose Boolean entry is still false. The implementations also verify two checkpoint cases before using the default bound, confirming that the partial answers for \(L=50\) and \(L=100\) are \(891\) and \(2766\).
The divisor sieve costs \(O(L\log L)\). If \(k=|A|\) is the number of abundant numbers up to \(L\), then the marking phase is \(O(k^2)\) in the worst case, with practical savings from the early break in the sorted list. The final accumulation is \(O(L)\).
Space usage is \(O(L)\): one integer array for proper-divisor sums, one Boolean array for representability, and the list of abundant numbers. For \(L=28123\), these structures are easily small enough for a straightforward implementation in all three languages.
Für eine positive ganze Zahl \(n\) bezeichne \(s(n)\) die Summe ihrer echten Teiler. Eine Zahl heißt abundant, wenn \(s(n) \gt n\) gilt. Gesucht ist die Summe aller positiven ganzen Zahlen, die sich nicht als \(a+b\) mit zwei abundanten Zahlen \(a\) und \(b\) darstellen lassen.
Die entscheidende Endlichkeitsreduktion steht bereits in der Aufgabenstellung: Jede ganze Zahl größer als \(28123\) ist eine Summe zweier abundanter Zahlen. Daher genügt es, nur den Bereich \(1 \le n \le L\) mit \(L=28123\) zu untersuchen.
Die Lösung verbindet zwei einfache Ideen. Zuerst wird für jede Zahl bis \(L\) die Summe der echten Teiler berechnet, um alle abundanten Zahlen zu klassifizieren. Danach wird die Menge aller Summen zweier abundanter Zahlen bis zur gleichen Schranke markiert. Alles, was unmarkiert bleibt, gehört zur gesuchten Gesamtsumme.
Wir definieren die Aliquotsumme durch
$$s(n)=\sum_{\substack{d \mid n \\ 1 \le d \lt n}} d.$$
Dann ist \(n\) defizient für \(s(n) \lt n\), vollkommen für \(s(n)=n\) und abundant für \(s(n) \gt n\). Die erste abundante Zahl ist \(12\), denn
$$s(12)=1+2+3+4+6=16 \gt 12.$$
Daraus folgt sofort eine kleine, aber nützliche Beobachtung: Keine Zahl unter \(24\) kann eine Summe zweier abundanter Zahlen sein, weil die kleinste solche Summe gleich \(12+12\) ist.
Sei
$$A=\{a\in\{1,2,\dots,L\}: s(a)\gt a\}$$
die Menge aller abundanten Zahlen bis zur Schranke. Relevant ist dann nur, ob ein Wert \(n\le L\) in der Menge
$$E=(A+A)\cap\{1,2,\dots,L\}=\{a_i+a_j:\ a_i,a_j\in A,\ a_i+a_j\le L\}$$
liegt. Gesucht ist also
$$\sum_{\substack{1 \le n \le L \\ n\notin E}} n.$$
In dieser Form ist das Problem vollständig sichtbar: Bestimme \(A\), markiere alle Werte aus \(E\), und addiere die Zahlen, die außerhalb von \(E\) bleiben.
Die Implementierungen faktorisieren die Zahlen nicht einzeln. Stattdessen verwenden sie ein Teilersieb. Für jeden möglichen echten Teiler \(d\) wird \(d\) zu allen Vielfachen \(2d,3d,4d,\dots\le L\) addiert. Am Ende hat der Eintrag an Position \(n\) genau die Beiträge aller echten Teiler von \(n\) erhalten und ist somit gleich \(s(n)\).
Die Laufzeit dieser Phase wird durch die harmonische Reihe beschrieben:
$$\sum_{d=1}^{\lfloor L/2 \rfloor}\left\lfloor \frac{L}{d}\right\rfloor = O(L\log L).$$
Für \(L=28123\) ist diese Vorverarbeitung so klein, dass ein schlichtes arraybasiertes Sieb völlig ausreicht.
Nach dem Sieb werden die abundanten Zahlen in aufsteigender Reihenfolge gesammelt. Fixiert man eine abundante Zahl \(a_i\) und probiert Partner \(a_j\) mit \(j\ge i\), dann wachsen die Summen \(a_i+a_j\) mit wachsendem \(j\). Sobald also \(a_i+a_j\gt L\) gilt, liefern alle späteren Partner ebenfalls nur noch Werte oberhalb der Schranke, und die innere Schleife kann sofort beendet werden.
Diese Monotonie ist die zentrale Invariante der zweiten Phase. Sie sorgt dafür, dass keine nutzlosen Paare jenseits der Suchgrenze betrachtet werden müssen.
Bis \(25\) lauten die abundanten Zahlen \(12,18,20,24\). Die erste erreichbare Summe ist
$$12+12=24.$$
Schon der nächste Partner liefert
$$12+18=30 \gt 25,$$
also müssen \(12+20\) und \(12+24\) bei einer Schranke von \(25\) gar nicht mehr geprüft werden. Damit wird \(24\) als darstellbar markiert, \(25\) hingegen bleibt unmarkiert und trägt zur Endsumme bei.
Die C++-, Python- und Java-Implementierungen legen ein ganzzahliges Feld der Länge \(L+1\) an und füllen es mit dem beschriebenen Teilersieb. Ein anschließender Durchlauf von links nach rechts erkennt alle abundanten Zahlen zwischen \(12\) und \(L\). Da dieser Durchlauf numerisch sortiert ist, ist auch die entstehende Liste automatisch sortiert.
Eine Boolesche Tabelle für die Indizes \(0,1,\dots,L\) speichert, welche Werte als Summe zweier abundanter Zahlen darstellbar sind. Das Programm durchläuft Paare aus der abundanten Liste, wobei der zweite Index beim ersten beginnt, sodass jedes ungeordnete Paar genau einmal behandelt wird. Bleibt die Summe innerhalb der Grenze, wird der entsprechende Eintrag markiert; überschreitet sie die Grenze, endet die innere Schleife sofort.
Zum Schluss werden alle \(n\) mit \(1 \le n \le L\) addiert, deren Boolescher Eintrag weiterhin false ist. Zusätzlich prüfen die Implementierungen zwei kleine Kontrollfälle und bestätigen, dass die partiellen Antworten für \(L=50\) und \(L=100\) gleich \(891\) beziehungsweise \(2766\) sind.
Das Teilersieb benötigt \(O(L\log L)\). Ist \(k=|A|\) die Anzahl abundanter Zahlen bis \(L\), dann kostet die Markierungsphase im Worst Case \(O(k^2)\), mit praktischen Einsparungen durch den frühen Abbruch in der sortierten Liste. Die abschließende Aufsummierung ist \(O(L)\).
Der Speicherbedarf beträgt \(O(L)\): ein Integer-Feld für die echten Teilersummen, ein Boolesches Feld für die Darstellbarkeit und die Liste der abundanten Zahlen. Für \(L=28123\) sind diese Datenstrukturen in allen drei Sprachen ohne Weiteres klein genug.
Pozitif bir tam sayı \(n\) için \(s(n)\), \(n\)'in öz bölenleri toplamı olsun. \(s(n)\gt n\) ise bu sayıya bol sayı denir. İstenen şey, iki bol sayının toplamı olarak yazılamayan bütün pozitif tam sayıların toplamıdır.
Problemin sonlu hale gelmesini sağlayan kilit bilgi doğrudan soru metnindedir: \(28123\)'ten büyük her tam sayı iki bol sayının toplamı olarak yazılabilir. Bu nedenle hesaplama yalnızca \(1 \le n \le L\) aralığında, \(L=28123\) için yapılır.
Çözüm iki basit fikrin birleşimidir. Önce \(L\)'ye kadar olan tüm sayılar öz bölen toplamlarına göre sınıflandırılır. Sonra aynı sınıra kadar elde edilebilen bütün iki-bol-sayı toplamları işaretlenir. İşaretlenmeyen değerlerin toplamı doğrudan cevabı verir.
Aliquot toplamını
$$s(n)=\sum_{\substack{d \mid n \\ 1 \le d \lt n}} d$$
şeklinde tanımlayalım. Buna göre \(s(n)\lt n\) ise sayı eksik, \(s(n)=n\) ise mükemmel, \(s(n)\gt n\) ise boldur. İlk bol sayı \(12\)'dir; çünkü
$$s(12)=1+2+3+4+6=16 \gt 12.$$
Buradan hemen küçük ama önemli bir sonuç çıkar: iki bol sayının en küçük toplamı \(12+12=24\) olduğundan, \(24\)'ten küçük hiçbir sayı böyle bir toplam olamaz.
$$A=\{a\in\{1,2,\dots,L\}: s(a)\gt a\}$$
olsun. O zaman yalnızca şu kümede olup olmadığı önemlidir:
$$E=(A+A)\cap\{1,2,\dots,L\}=\{a_i+a_j:\ a_i,a_j\in A,\ a_i+a_j\le L\}.$$
Aranan toplam da
$$\sum_{\substack{1 \le n \le L \\ n\notin E}} n$$
biçimindedir. Yani problem, \(A\)'yı kurup \(E\)'deki bütün değerleri işaretlemek ve geriye kalanları toplamak şeklinde yeniden yazılmış olur.
Uygulamalar her sayıyı ayrı ayrı çarpanlarına ayırmaz. Bunun yerine bir bölen eleği kullanır. Her olası öz bölen \(d\) için, \(d\) değeri \(2d,3d,4d,\dots\le L\) biçimindeki tüm katlara eklenir. Süreç bittiğinde \(n\) konumundaki toplam, \(n\)'in tüm öz bölenlerinden gelen katkıların toplamı yani \(s(n)\) olur.
Bu aşamanın maliyeti harmonik seriyle kontrol edilir:
$$\sum_{d=1}^{\lfloor L/2 \rfloor}\left\lfloor \frac{L}{d}\right\rfloor = O(L\log L).$$
\(L=28123\) için bu ön işlem son derece küçüktür; düz bir dizi tabanlı yaklaşım yeterlidir.
Elekten sonra bol sayılar artan sırayla toplanır. Sabit bir \(a_i\) bol sayısı seçilip \(j\ge i\) olacak biçimde ortaklar denenirse, \(a_i+a_j\) toplamı \(j\) arttıkça büyür. Dolayısıyla bir noktada \(a_i+a_j\gt L\) olursa, sonraki bütün ortaklar da sınırı aşar ve iç döngü güvenle durdurulabilir.
İkinci aşamanın temel değişmezi budur. Algoritma teorik olarak \(A+A\) kümesini tarasa da, sınırın üstüne çıkan gereksiz eşleşmeleri hiç incelemez.
\(25\)'e kadar olan bol sayılar \(12,18,20,24\) olur. İlk ulaşılabilir toplam
$$12+12=24$$
iken, bir sonraki ortak hemen
$$12+18=30 \gt 25$$
verir. Liste sıralı olduğu için \(25\) sınırında artık \(12+20\) ve \(12+24\) denenmez. Böylece \(24\) ifade edilebilir olarak işaretlenir, \(25\) ise hiç işaretlenmez ve son toplama eklenir.
C++, Python ve Java uygulamaları uzunluğu \(L+1\) olan bir tamsayı dizisi ayırır ve bunu bölen eleğiyle doldurur. Ardından soldan sağa tek bir tarama ile \(12\) ile \(L\) arasındaki bütün bol sayılar seçilir. Bu tarama zaten artan sırada olduğu için elde edilen bol sayı listesi otomatik olarak sıralıdır.
\(0,1,\dots,L\) indisleri için bir Boole tablosu, hangi değerlerin iki bol sayının toplamı olduğunu tutar. Uygulamalar bol sayı çiftlerini, ikinci indis birinciden başlayacak şekilde dolaşır; böylece her sırasız çift yalnızca bir kez ele alınır. Toplam sınır içinde kalırsa ilgili hücre işaretlenir, sınırı aşarsa iç döngü hemen kırılır.
Son aşamada, \(1 \le n \le L\) aralığında Boole değeri hâlâ false olan her sayı toplamaya eklenir. Uygulamalar varsayılan sınıra geçmeden önce iki küçük kontrol de yapar ve \(L=50\) ile \(L=100\) için kısmi sonuçların sırasıyla \(891\) ve \(2766\) olduğunu doğrular.
Bölen eleği \(O(L\log L)\) maliyetlidir. \(k=|A|\), \(L\)'ye kadar olan bol sayı sayısı olsun. O zaman işaretleme aşaması en kötü durumda \(O(k^2)\) sürer; fakat sıralı listedeki erken durma pratikte önemli tasarruf sağlar. Son toplama taraması ise \(O(L)\) zaman alır.
Bellek kullanımı \(O(L)\) düzeyindedir: öz bölen toplamları için bir tamsayı dizisi, ifade edilebilirlik için bir Boole dizisi ve bol sayı listesi tutulur. \(L=28123\) için bu veri yapıları üç dilde de rahatlıkla küçüktür.
Para un entero positivo \(n\), sea \(s(n)\) la suma de sus divisores propios. Un número es abundante cuando \(s(n)\gt n\). La tarea consiste en sumar todos los enteros positivos que no pueden escribirse como \(a+b\) con \(a\) y \(b\) abundantes.
La reducción decisiva ya aparece en el enunciado: todo entero mayor que \(28123\) puede expresarse como suma de dos números abundantes. Por eso basta trabajar en el intervalo finito \(1 \le n \le L\), con \(L=28123\).
La solución combina dos ideas. Primero se clasifica cada entero hasta \(L\) mediante la suma de sus divisores propios. Después se construye el conjunto de todas las sumas de dos abundantes dentro de la misma cota. Una vez marcadas esas sumas alcanzables, la respuesta es la suma de los valores que nunca fueron marcados.
Definimos la suma alícuota por
$$s(n)=\sum_{\substack{d \mid n \\ 1 \le d \lt n}} d.$$
Entonces \(n\) es deficiente si \(s(n)\lt n\), perfecto si \(s(n)=n\) y abundante si \(s(n)\gt n\). El primer número abundante es \(12\), porque
$$s(12)=1+2+3+4+6=16 \gt 12.$$
Esto da de inmediato una observación útil: ningún entero menor que \(24\) puede ser suma de dos abundantes, ya que la suma mínima posible es \(12+12\).
Sea
$$A=\{a\in\{1,2,\dots,L\}: s(a)\gt a\}$$
el conjunto de abundantes hasta el límite. Solo importa saber si un valor \(n\le L\) pertenece a
$$E=(A+A)\cap\{1,2,\dots,L\}=\{a_i+a_j:\ a_i,a_j\in A,\ a_i+a_j\le L\}.$$
La cantidad pedida es, por tanto,
$$\sum_{\substack{1 \le n \le L \\ n\notin E}} n.$$
En esta forma el problema queda completamente descrito: construir \(A\), marcar todos los elementos de \(E\) y sumar los enteros que permanecen fuera de \(E\).
Las implementaciones no factorizan cada número por separado. En su lugar usan un tamiz de divisores. Para cada posible divisor propio \(d\), se suma \(d\) a todos los múltiplos \(2d,3d,4d,\dots\le L\). Al terminar, la casilla correspondiente a \(n\) contiene exactamente la suma de todos los divisores propios de \(n\), es decir, \(s(n)\).
El coste temporal de esta fase viene dado por la serie armónica:
$$\sum_{d=1}^{\lfloor L/2 \rfloor}\left\lfloor \frac{L}{d}\right\rfloor = O(L\log L).$$
Para \(L=28123\), este preprocesamiento es lo bastante pequeño como para resolverse con un arreglo sencillo.
Después del tamiz, los abundantes se almacenan en orden creciente. Si fijamos un abundante \(a_i\) y probamos compañeros \(a_j\) con \(j\ge i\), las sumas \(a_i+a_j\) crecen con \(j\). Por eso, en cuanto \(a_i+a_j\gt L\), todos los compañeros posteriores también superarán la cota, y el bucle interior puede detenerse sin perder ninguna suma válida.
Esa monotonía es la invariante clave de la segunda fase. Gracias a ella, el algoritmo no sigue explorando pares que ya están fuera del rango útil.
Hasta \(25\), los números abundantes son \(12,18,20,24\). La primera suma alcanzable es
$$12+12=24.$$
El siguiente compañero ya produce
$$12+18=30 \gt 25,$$
de modo que, con límite \(25\), no hace falta probar \(12+20\) ni \(12+24\). Así, \(24\) queda marcado como expresable, mientras que \(25\) nunca se marca y debe añadirse a la suma final.
Las implementaciones en C++, Python y Java reservan un arreglo entero de longitud \(L+1\) y lo llenan con el tamiz de divisores. Luego recorren ese arreglo de izquierda a derecha para identificar todos los abundantes entre \(12\) y \(L\). Como el recorrido es creciente, la lista resultante queda ordenada automáticamente.
Una tabla booleana indexada por \(0,1,\dots,L\) registra qué valores son suma de dos abundantes. La implementación recorre pares de la lista abundante comenzando el segundo índice en el primero, de modo que cada par no ordenado se procesa una sola vez. Si la suma no supera el límite, se marca la entrada; si lo supera, el bucle interior termina en ese punto.
El último recorrido suma todos los \(n\) con \(1 \le n \le L\) cuya entrada booleana sigue siendo false. Además, las implementaciones validan dos casos de control antes de usar el límite por defecto y comprueban que las respuestas parciales para \(L=50\) y \(L=100\) son \(891\) y \(2766\).
El tamiz de divisores cuesta \(O(L\log L)\). Si \(k=|A|\) es el número de abundantes hasta \(L\), la fase de marcado cuesta \(O(k^2)\) en el peor caso, aunque la interrupción temprana en la lista ordenada reduce el trabajo real. El barrido final cuesta \(O(L)\).
El uso de memoria es \(O(L)\): un arreglo entero para las sumas de divisores propios, un arreglo booleano para la representabilidad y la lista de abundantes. Para \(L=28123\), estas estructuras son pequeñas en las tres implementaciones.
对正整数 \(n\)，记 \(s(n)\) 为它的真因子和。若 \(s(n)\gt n\)，则称 \(n\) 为丰数。题目要求把所有 不能表示成两个丰数之和的正整数全部加起来。
真正让问题变得有限的是题目给出的结论：所有大于 \(28123\) 的整数都可以写成两个丰数之和。因此只需要在 \(1 \le n \le L\) 的范围内计算，其中 \(L=28123\)。
这道题的数学结构并不复杂，但非常适合一次性预处理。第一步是为 \(1\) 到 \(L\) 的每个整数求真因子和，从而判定哪些数是丰数。第二步是把所有不超过 \(L\) 的“两丰数之和”全部标记出来。最后把没有被标记到的整数相加即可。
定义
$$s(n)=\sum_{\substack{d \mid n \\ 1 \le d \lt n}} d.$$
若 \(s(n)\lt n\)，则 \(n\) 是亏数；若 \(s(n)=n\)，则 \(n\) 是完全数；若 \(s(n)\gt n\)，则 \(n\) 是丰数。 最小的丰数是 \(12\)，因为
$$s(12)=1+2+3+4+6=16 \gt 12.$$
这个例子立刻带来一个简单结论：小于 \(24\) 的整数不可能写成两个丰数之和，因为最小的两丰数之和就是 \(12+12\)。
设
$$A=\{a\in\{1,2,\dots,L\}: s(a)\gt a\}$$
为不超过 \(L\) 的全部丰数集合。我们真正关心的是某个 \(n\le L\) 是否属于
$$E=(A+A)\cap\{1,2,\dots,L\}=\{a_i+a_j:\ a_i,a_j\in A,\ a_i+a_j\le L\}.$$
于是目标和可以写成
$$\sum_{\substack{1 \le n \le L \\ n\notin E}} n.$$
写成这个形式以后，题目的本质就很清楚了：先求出丰数集合 \(A\)，再把所有能由两项丰数得到的值放进 \(E\)，最后把不在 \(E\) 中的整数加起来。
实现并不会对每个 \(n\) 单独分解质因数。它采用的是“按因子贡献”的筛法。对每个可能的真因子 \(d\)，把 \(d\) 加到所有倍数 \(2d,3d,4d,\dots\le L\) 上。处理结束后，位置 \(n\) 上累计到的正好就是 \(n\) 所有真因子的和，也就是 \(s(n)\)。
这一阶段的时间复杂度来自调和级数：
$$\sum_{d=1}^{\lfloor L/2 \rfloor}\left\lfloor \frac{L}{d}\right\rfloor = O(L\log L).$$
在 \(L=28123\) 的规模下，这样的预处理非常轻量，用普通数组就足够了。
筛完以后，所有丰数按从小到大的顺序收集起来。固定一个丰数 \(a_i\) 后，再依次尝试 \(a_j\)，其中 \(j\ge i\)。由于列表有序，\(a_i+a_j\) 会随着 \(j\) 的增大而单调增大。一旦某次出现 \(a_i+a_j\gt L\)，后面更大的 \(a_j\) 只会让和更大，所以内层循环可以立刻停止。
这就是第二阶段最重要的不变量。算法虽然表面上是在枚举丰数对，但它不会继续检查那些已经超过上界的无效组合。
若只看 \(25\) 以内，丰数为 \(12,18,20,24\)。第一项可达和是
$$12+12=24.$$
再往后马上得到
$$12+18=30 \gt 25,$$
所以在上界是 \(25\) 时，不必继续尝试 \(12+20\) 和 \(12+24\)。因此 \(24\) 会被标记为“可表示”，而 \(25\) 从头到尾都不会被标记，最后自然要计入答案。
C++、Python 和 Java 实现都会先申请一个长度为 \(L+1\) 的整数数组，并用上面的筛法填充它。随后从左到右扫一遍数组，把 \(12\) 到 \(L\) 之间所有满足 \(s(n)\gt n\) 的数收集出来。由于扫描本身就是递增的，所以得到的丰数列表天然有序。
接着建立一个下标范围为 \(0,1,\dots,L\) 的布尔表，用来记录某个值能否表示成两个丰数之和。实现里让第二个下标从第一个下标开始，这样每个无序丰数对只处理一次。如果某对的和不超过上界，就把对应位置标记为 true；如果超过上界，就立刻结束当前内层循环。
最后再从 \(1\) 扫到 \(L\)，把布尔表中仍为 false 的所有整数加起来。实现还会先检查两个小规模验证点，确认当 \(L=50\) 和 \(L=100\) 时，部分结果分别为 \(891\) 与 \(2766\)。
真因子筛的复杂度是 \(O(L\log L)\)。设 \(k=|A|\) 为不超过 \(L\) 的丰数个数，则“标记两丰数之和”的阶段在最坏情况下是 \(O(k^2)\)，不过由于列表有序且可以提前停止，实际工作量会更小。最后一次求和扫描是 \(O(L)\)。
空间复杂度为 \(O(L)\)：需要一个整数数组保存真因子和，一个布尔数组保存可表示性，再加上一份丰数列表。对 \(L=28123\) 而言，这些结构在三种语言实现中都非常轻量。
Для положительного целого числа \(n\) обозначим через \(s(n)\) сумму его собственных делителей. Число называется избыточным, если \(s(n)\gt n\). Требуется найти сумму всех положительных целых чисел, которые нельзя представить в виде \(a+b\), где и \(a\), и \(b\) избыточны.
Ключевое упрощение уже дано в условии: каждое целое число больше \(28123\) представимо как сумма двух избыточных чисел. Значит, достаточно рассматривать только конечный диапазон \(1 \le n \le L\), где \(L=28123\).
Идея решения состоит из двух частей. Сначала для каждого числа до \(L\) вычисляется сумма собственных делителей, и тем самым определяется, является ли оно избыточным. Затем строится множество всех сумм двух избыточных чисел, не превышающих тот же предел. После этого остается просуммировать те значения, которые ни разу не были отмечены.
Определим аликвотную сумму формулой
$$s(n)=\sum_{\substack{d \mid n \\ 1 \le d \lt n}} d.$$
Тогда число \(n\) является недостаточным при \(s(n)\lt n\), совершенным при \(s(n)=n\) и избыточным при \(s(n)\gt n\). Наименьшее избыточное число равно \(12\), потому что
$$s(12)=1+2+3+4+6=16 \gt 12.$$
Отсюда сразу следует полезный факт: ни одно число меньше \(24\) не может быть суммой двух избыточных чисел, так как минимальная такая сумма равна \(12+12\).
Пусть
$$A=\{a\in\{1,2,\dots,L\}: s(a)\gt a\}$$
обозначает множество всех избыточных чисел до границы \(L\). Нас интересует лишь принадлежность значения \(n\le L\) множеству
$$E=(A+A)\cap\{1,2,\dots,L\}=\{a_i+a_j:\ a_i,a_j\in A,\ a_i+a_j\le L\}.$$
Искомая сумма записывается как
$$\sum_{\substack{1 \le n \le L \\ n\notin E}} n.$$
В этом виде задача полностью прозрачна: построить \(A\), отметить все элементы \(E\), а затем сложить числа, оставшиеся вне \(E\).
Реализации не раскладывают каждое число на множители отдельно. Вместо этого используется решето по делителям. Для каждого возможного собственного делителя \(d\) значение \(d\) добавляется ко всем кратным \(2d,3d,4d,\dots\le L\). После завершения процесса в позиции \(n\) накопится ровно сумма всех собственных делителей числа \(n\), то есть \(s(n)\).
Временная сложность этой стадии описывается гармоническим рядом:
$$\sum_{d=1}^{\lfloor L/2 \rfloor}\left\lfloor \frac{L}{d}\right\rfloor = O(L\log L).$$
Для \(L=28123\) такое предварительное вычисление достаточно мало, чтобы обойтись самым прямым массивным подходом.
После решета избыточные числа собираются в возрастающем порядке. Если зафиксировать одно избыточное число \(a_i\) и перебирать партнеров \(a_j\) при \(j\ge i\), то суммы \(a_i+a_j\) растут вместе с \(j\). Поэтому, как только выполнится \(a_i+a_j\gt L\), все более поздние партнеры тоже будут давать суммы выше границы, и внутренний цикл можно немедленно остановить.
Именно эта монотонность является главным инвариантом второй фазы. Благодаря ей алгоритм не тратит время на пары, которые уже вышли за предел полезного диапазона.
До \(25\) избыточными являются числа \(12,18,20,24\). Первая достижимая сумма равна
$$12+12=24.$$
Следующий партнер сразу дает
$$12+18=30 \gt 25,$$
поэтому при границе \(25\) уже не нужно проверять \(12+20\) и \(12+24\). Значение \(24\) будет отмечено как представимое, а \(25\) так и останется неотмеченным и войдет в итоговую сумму.
Реализации на C++, Python и Java создают целочисленный массив длины \(L+1\) и заполняют его описанным решетом. Затем выполняется один проход слева направо, который выделяет все избыточные числа от \(12\) до \(L\). Поскольку проход идет по возрастанию, список избыточных чисел сразу получается отсортированным.
Булева таблица с индексами \(0,1,\dots,L\) хранит, какие значения представимы в виде суммы двух избыточных чисел. Перебор идет по парам из списка избыточных чисел, причем второй индекс начинается с первого, так что каждая неупорядоченная пара рассматривается только один раз. Если сумма не превышает предел, соответствующая клетка помечается; если превышает, внутренний цикл сразу завершается.
На последнем проходе суммируются все \(n\) из диапазона \(1 \le n \le L\), для которых булева отметка по-прежнему равна false. Перед запуском с основной границей реализации также проверяют два контрольных случая и подтверждают, что частичные ответы для \(L=50\) и \(L=100\) равны \(891\) и \(2766\).
Решето по делителям требует \(O(L\log L)\). Если \(k=|A|\) обозначает количество избыточных чисел до \(L\), то этап пометки в худшем случае имеет сложность \(O(k^2)\), хотя ранний выход в отсортированном списке уменьшает фактическую работу. Заключительный проход суммирования занимает \(O(L)\).
По памяти требуется \(O(L)\): один целочисленный массив для сумм собственных делителей, один булев массив для представимости и сам список избыточных чисел. Для \(L=28123\) все эти структуры очень малы во всех трех реализациях.
لعدد صحيح موجب \(n\)، نرمز بـ \(s(n)\) إلى مجموع قواسِمه الصحيحة غير نفسه. ويُسمى العدد وافرًا إذا كان \(s(n)\gt n\). المطلوب هو جمع جميع الأعداد الصحيحة الموجبة التي لا يمكن كتابتها على صورة \(a+b\) حيث يكون كل من \(a\) و\(b\) عددًا وافرًا.
الخطوة الحاسمة التي تجعل المسألة منتهية مذكورة في نص السؤال نفسه: كل عدد صحيح أكبر من \(28123\) يمكن تمثيله كمجموع عددين وافرين. لذلك يكفي أن نحصر الحساب في المجال \(1 \le n \le L\) حيث \(L=28123\).
الفكرة الرياضية هنا تتكون من مرحلتين واضحتين. أولًا نحسب مجموع القواسم الصحيحة لكل عدد حتى \(L\) لكي نعرف الأعداد الوافرة بدقة. ثم نبني مجموعة كل القيم التي يمكن الوصول إليها كمجموع عددين وافرين داخل الحد نفسه. بعد ذلك تصبح الإجابة مجرد جمع القيم التي لم تُعلَّم.
نعرّف مجموع القواسم الصحيحة بالصيغة
$$s(n)=\sum_{\substack{d \mid n \\ 1 \le d \lt n}} d.$$
وعندئذ يكون \(n\) عددًا ناقصًا إذا كان \(s(n)\lt n\)، وعددًا كاملًا إذا كان \(s(n)=n\)، وعددًا وافرًا إذا كان \(s(n)\gt n\). أصغر عدد وافر هو \(12\)، لأن
$$s(12)=1+2+3+4+6=16 \gt 12.$$
ومن هذه الملاحظة ينتج فورًا أن أي عدد أصغر من \(24\) لا يمكن أن يكون مجموع عددين وافرين، لأن أصغر مجموع ممكن هو \(12+12\).
لتكن
$$A=\{a\in\{1,2,\dots,L\}: s(a)\gt a\}$$
هي مجموعة الأعداد الوافرة حتى الحد \(L\). وما نحتاج إلى معرفته فعلًا هو ما إذا كانت قيمة \(n\le L\) تنتمي إلى
$$E=(A+A)\cap\{1,2,\dots,L\}=\{a_i+a_j:\ a_i,a_j\in A,\ a_i+a_j\le L\}.$$
إذًا تصبح الكمية المطلوبة
$$\sum_{\substack{1 \le n \le L \\ n\notin E}} n.$$
وبهذه الصياغة ينكشف جوهر المسألة بالكامل: نبني المجموعة \(A\)، ثم نعلّم كل عنصر في \(E\)، ثم نجمع الأعداد التي بقيت خارج \(E\).
التنفيذ لا يحلل كل عدد على حدة. بدلًا من ذلك يستخدم غربالًا للقواسم. لكل قاسم صحيح محتمل \(d\)، نضيف \(d\) إلى كل مضاعف من الشكل \(2d,3d,4d,\dots\le L\). وبعد انتهاء العملية تكون الخانة الخاصة بالعدد \(n\) قد استقبلت مساهمة كل قواسمه الصحيحة، وبالتالي تصبح مساوية تمامًا لـ \(s(n)\).
زمن هذه المرحلة تحكمه السلسلة التوافقية:
$$\sum_{d=1}^{\lfloor L/2 \rfloor}\left\lfloor \frac{L}{d}\right\rfloor = O(L\log L).$$
وعند \(L=28123\) يكون هذا التمهيد صغيرًا بما يكفي ليُنفَّذ بمصفوفة بسيطة جدًا.
بعد الغربال تُجمع الأعداد الوافرة بترتيب تصاعدي. إذا ثبّتنا عددًا وافرًا \(a_i\) وجرّبنا شركاء \(a_j\) مع \(j\ge i\)، فإن المجاميع \(a_i+a_j\) تكبر كلما كبر \(j\). لذلك بمجرد أن يتحقق \(a_i+a_j\gt L\)، فإن أي شريك لاحق سيعطي مجموعًا أكبر أيضًا، وبذلك يمكن إيقاف الحلقة الداخلية فورًا.
هذه الرتابة هي الثابت الأساسي في المرحلة الثانية. فهي تمنع الخوارزمية من متابعة أزواج لم تعد مفيدة لأنها خرجت أصلًا عن حد البحث.
حتى \(25\)، تكون الأعداد الوافرة هي \(12,18,20,24\). أول مجموع ممكن هو
$$12+12=24.$$
ثم نحصل مباشرة على
$$12+18=30 \gt 25,$$
ولذلك لا حاجة بعد ذلك إلى تجربة \(12+20\) أو \(12+24\) عندما يكون الحد هو \(25\). وهكذا تُعلَّم \(24\) على أنها قيمة قابلة للتمثيل، بينما تبقى \(25\) غير معلَّمة وتدخل في المجموع النهائي.
تنشئ تطبيقات C++ وPython وJava مصفوفة صحيحة بطول \(L+1\)، ثم تملؤها بغربال القواسم السابق. وبعد ذلك تُجرى عملية مسح واحدة من اليسار إلى اليمين لاستخراج جميع الأعداد الوافرة بين \(12\) و\(L\). وبما أن المسح تصاعدي، فإن قائمة الأعداد الوافرة تكون مرتبة تلقائيًا.
يُستخدم جدول منطقي مفهرس من \(0\) حتى \(L\) لتسجيل القيم التي يمكن كتابتها كمجموع عددين وافرين. ويبدأ الفهرس الثاني من الفهرس الأول، لذلك يُعالَج كل زوج غير مرتب مرة واحدة فقط. إذا بقي المجموع داخل الحد، تُعلَّم الخانة المناسبة؛ وإذا تجاوزه، تُكسَر الحلقة الداخلية فورًا.
في النهاية تُجمع كل القيم \(n\) التي تحقق \(1 \le n \le L\) وما زالت خانتها المنطقية false. كما تتحقق التطبيقات من حالتي فحص صغيرتين قبل استعمال الحد الافتراضي، فتؤكد أن النتيجتين الجزئيتين عند \(L=50\) و\(L=100\) هما \(891\) و\(2766\).
غربال القواسم يكلف \(O(L\log L)\). وإذا رمزنا بعدد الأعداد الوافرة حتى \(L\) بالرمز \(k=|A|\)، فإن مرحلة التعليم تكلف \(O(k^2)\) في أسوأ الحالات، مع توفير عملي مهم بسبب الإيقاف المبكر في القائمة المرتبة. أما المسح الأخير للجمع فتكلفته \(O(L)\).
استهلاك الذاكرة هو \(O(L)\): مصفوفة صحيحة لمجاميع القواسم الصحيحة، ومصفوفة منطقية لقابلية التمثيل، وقائمة الأعداد الوافرة. وعند \(L=28123\) تبقى هذه البنى صغيرة جدًا في اللغات الثلاث.