For every positive integer \(n\), let \(\operatorname{dr}(n)\) be its digital root, obtained by repeatedly summing decimal digits until only one digit remains. If
$$n=f_1f_2\cdots f_k,\qquad f_i \ge 2,$$
define the digital-root sum of that multiplicative factorisation by
$$\operatorname{drs}(f_1,\dots,f_k)=\sum_{i=1}^{k}\operatorname{dr}(f_i).$$
The quantity of interest is
$$\operatorname{mdrs}(n)=\max \operatorname{drs}(f_1,\dots,f_k),$$
where the maximum runs over all multiplicative factorizations of \(n\) into integers at least 2, including the trivial one-part factorisation \(n\) itself. The problem asks for
$$\sum_{n=2}^{10^6-1}\operatorname{mdrs}(n).$$
A brute-force search over all factorizations of every integer below one million would repeat the same subproblems many times. The implementations avoid that by turning \(\operatorname{mdrs}\) into a dynamic program on factor pairs.
The whole solution rests on one observation: once the best value is known for smaller integers, the best value for a larger composite can be assembled from a split \(n=ab\).
For \(n \ge 1\), the digital root is given directly by
$$\operatorname{dr}(n)=1+((n-1)\bmod 9).$$
So \(\operatorname{dr}(n)\) is always one of \(1,2,\dots,9\), and multiples of 9 have digital root 9. If we choose not to factor \(n\) at all, then its score is simply \(\operatorname{dr}(n)\). That provides the baseline value for \(\operatorname{mdrs}(n)\).
Take any nontrivial factorisation of \(n\):
$$n=f_1f_2\cdots f_k,\qquad k\ge 2.$$
Group the factors as \(a=f_1\) and \(b=f_2\cdots f_k\). Then \(n=ab\) with \(a,b\ge 2\), and the score of the original factorisation is at most \(\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\). Conversely, for every split \(n=ab\), concatenating an optimal factorisation of \(a\) with an optimal factorisation of \(b\) produces a factorisation of \(n\) whose score is exactly that sum. Therefore
$$\operatorname{mdrs}(n)=\max\!\left(\operatorname{dr}(n),\max_{\substack{ab=n\\a,b\ge 2}}\bigl(\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\bigr)\right).$$
This is the central mathematical object used by all three implementations. Prime numbers never enter the inner maximum, so for primes the value stays equal to \(\operatorname{dr}(n)\). Composite numbers are improved by whichever proper factor pair gives the largest sum.
The table is initialized with
$$\operatorname{mdrs}(n)=\operatorname{dr}(n)\qquad (1\le n<10^6).$$
After that, every product \(p=ab\) with \(a,b\ge 2\) is used to relax the table entry for \(p\):
$$\operatorname{mdrs}(p)\leftarrow \max\!\bigl(\operatorname{mdrs}(p),\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\bigr).$$
The only subtle point is correctness of the loop order. When the outer sweep reaches a value \(a\), all proper factorizations of \(a\) have already been processed, because every factor pair of \(a\) uses a smaller left factor. So \(\operatorname{mdrs}(a)\) is final at that moment. If the companion factor \(b\) is larger and later receives a better value, the same product \(p=ab\) reappears again when the outer sweep eventually reaches \(b\). Hence every unordered factor pair is considered at least once after both component values are final, and a single pass over multiples is enough.
The direct digital root is \(\operatorname{dr}(24)=6\), so the baseline starts at 6. The proper factor pairs are
$$24=2\cdot 12=3\cdot 8=4\cdot 6.$$
Using already-computed smaller values gives
$$\operatorname{mdrs}(2)+\operatorname{mdrs}(12)=2+8=10,$$
$$\operatorname{mdrs}(3)+\operatorname{mdrs}(8)=3+8=11,$$
$$\operatorname{mdrs}(4)+\operatorname{mdrs}(6)=4+6=10.$$
So
$$\operatorname{mdrs}(24)=11,$$
attained by the factorisation \(24=3\cdot 8\). This example is important because it shows why the problem is not solved by the digital root alone: the best multiplicative split can exceed \(\operatorname{dr}(n)\) by a large margin.
The C++, Python, and Java implementations allocate an array indexed by the integers below \(10^6\). Each entry is first filled with the closed-form digital root, so every number begins with the score of its trivial one-factor decomposition.
The main sweep chooses an outer factor \(a\) from 2 upward and then visits the multiples \(2a,3a,4a,\dots\). For each multiple \(p\), the companion factor is \(b=p/a\), so the implementation tries the candidate \(\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\). If that candidate is better than the current entry for \(p\), the table is updated. One implementation also checks the known value \(\operatorname{mdrs}(24)=11\) before doing the full run.
Once the table has been relaxed over all products, the remaining work is linear: add \(\operatorname{mdrs}(n)\) for every \(n\) from 2 through \(10^6-1\). The three language versions differ only in surface syntax; the mathematical workflow is the same in all of them.
Initializing the table costs \(O(N)\) with \(N=10^6\). The dominant phase is the sweep over multiples:
$$\sum_{a=2}^{N-1}\left\lfloor\frac{N-1}{a}\right\rfloor = O(N\log N).$$
The final accumulation is another \(O(N)\) pass, so the total running time is \(O(N\log N)\). The memory usage is \(O(N)\) for the array of \(\operatorname{mdrs}\) values.
Für jede positive ganze Zahl \(n\) bezeichne \(\operatorname{dr}(n)\) ihre digitale Wurzel, also das Ergebnis der wiederholten Quersummenbildung bis nur noch eine Ziffer übrig bleibt. Gilt
$$n=f_1f_2\cdots f_k,\qquad f_i \ge 2,$$
dann ist die digitale-Wurzel-Summe dieser multiplikativen Zerlegung definiert als
$$\operatorname{drs}(f_1,\dots,f_k)=\sum_{i=1}^{k}\operatorname{dr}(f_i).$$
Gesucht ist
$$\operatorname{mdrs}(n)=\max \operatorname{drs}(f_1,\dots,f_k),$$
wobei das Maximum über alle Zerlegungen von \(n\) in Faktoren \(\ge 2\) läuft, einschließlich der trivialen Ein-Faktor-Zerlegung \(n\) selbst. Die Aufgabe verlangt dann
$$\sum_{n=2}^{10^6-1}\operatorname{mdrs}(n).$$
Ein naiver Durchlauf über alle Faktorisierungen aller Zahlen unter einer Million würde dieselben Teilprobleme immer wieder neu lösen. Die Implementierungen vermeiden das mit einer dynamischen Programmierung über Faktorpaare.
Der entscheidende Punkt ist: Sobald die besten Werte kleinerer Zahlen bekannt sind, kann der beste Wert einer größeren zusammengesetzten Zahl aus einer Zerlegung \(n=ab\) aufgebaut werden.
Für \(n \ge 1\) gilt direkt
$$\operatorname{dr}(n)=1+((n-1)\bmod 9).$$
Damit liegt \(\operatorname{dr}(n)\) immer in \(\{1,2,\dots,9\}\), und Vielfache von 9 haben digitale Wurzel 9. Wenn man \(n\) überhaupt nicht weiter zerlegt, ist der zugehörige Wert einfach \(\operatorname{dr}(n)\). Das ist also der Ausgangswert von \(\operatorname{mdrs}(n)\).
Betrachte eine nichttriviale Faktorisierung
$$n=f_1f_2\cdots f_k,\qquad k\ge 2.$$
Fasse die Faktoren zu \(a=f_1\) und \(b=f_2\cdots f_k\) zusammen. Dann ist \(n=ab\) mit \(a,b\ge 2\), und der Wert der ursprünglichen Faktorisierung ist höchstens \(\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\). Umgekehrt liefert jede Zerlegung \(n=ab\) zusammen mit optimalen Faktorisierungen von \(a\) und \(b\) eine Faktorisierung von \(n\) mit genau dieser Summe. Also gilt
$$\operatorname{mdrs}(n)=\max\!\left(\operatorname{dr}(n),\max_{\substack{ab=n\\a,b\ge 2}}\bigl(\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\bigr)\right).$$
Das ist die zentrale Formel aller drei Implementierungen. Primzahlen tauchen im inneren Maximum nicht auf; für sie bleibt der Wert also \(\operatorname{dr}(n)\). Zusammengesetzte Zahlen werden durch das beste echte Faktorpaarsplit verbessert.
Die Tabelle wird zunächst mit
$$\operatorname{mdrs}(n)=\operatorname{dr}(n)\qquad (1\le n<10^6)$$
gefüllt. Danach wird jedes Produkt \(p=ab\) mit \(a,b\ge 2\) zur Relaxation benutzt:
$$\operatorname{mdrs}(p)\leftarrow \max\!\bigl(\operatorname{mdrs}(p),\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\bigr).$$
Die eigentliche Korrektheitsfrage steckt in der Reihenfolge der Schleifen. Wenn der äußere Durchlauf bei einem Wert \(a\) angekommen ist, dann sind bereits alle echten Faktorisierungen von \(a\) verarbeitet worden, weil jedes Faktorpaar von \(a\) einen kleineren linken Faktor besitzt. Also ist \(\operatorname{mdrs}(a)\) in diesem Moment schon final. Falls der Partner \(b\) größer ist und später noch verbessert wird, erscheint dasselbe Produkt \(p=ab\) erneut, sobald der äußere Durchlauf \(b\) erreicht. Deshalb wird jedes ungeordnete Faktorpaar mindestens einmal in einem Zustand betrachtet, in dem beide Teilwerte final sind, und ein einziger Sweep über alle Vielfachen reicht aus.
Direkt gilt \(\operatorname{dr}(24)=6\), also startet der Basiswert bei 6. Die echten Faktorpaare sind
$$24=2\cdot 12=3\cdot 8=4\cdot 6.$$
Mit den schon berechneten kleineren Werten erhält man
$$\operatorname{mdrs}(2)+\operatorname{mdrs}(12)=2+8=10,$$
$$\operatorname{mdrs}(3)+\operatorname{mdrs}(8)=3+8=11,$$
$$\operatorname{mdrs}(4)+\operatorname{mdrs}(6)=4+6=10.$$
Damit folgt
$$\operatorname{mdrs}(24)=11,$$
erreicht durch die Zerlegung \(24=3\cdot 8\). Das Beispiel zeigt unmittelbar, warum die bloße digitale Wurzel nicht genügt: die beste multiplikative Zerlegung kann deutlich größer sein als \(\operatorname{dr}(n)\).
Die C++-, Python- und Java-Implementierungen legen ein Array für alle Zahlen unter \(10^6\) an. Jeder Eintrag wird zuerst mit der geschlossenen Formel für die digitale Wurzel gefüllt, sodass jede Zahl mit dem Wert ihrer trivialen Ein-Faktor-Zerlegung startet.
Der Hauptdurchlauf wählt einen äußeren Faktor \(a\) ab 2 aufwärts und besucht dann die Vielfachen \(2a,3a,4a,\dots\). Für jedes Vielfache \(p\) ist der Partner \(b=p/a\), also wird der Kandidat \(\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\) getestet. Wenn dieser Kandidat besser als der bisherige Eintrag von \(p\) ist, wird die Tabelle aktualisiert. Eine der Implementierungen überprüft vor dem großen Lauf zusätzlich den bekannten Kontrollwert \(\operatorname{mdrs}(24)=11\).
Nach Abschluss aller Relaxationen bleibt nur noch ein linearer Summendurchlauf: addiert werden die Werte \(\operatorname{mdrs}(n)\) für \(n=2,3,\dots,10^6-1\). Die drei Sprachversionen unterscheiden sich nur in der Oberflächen-Syntax; mathematisch führen sie denselben Ablauf aus.
Das Initialisieren der Tabelle kostet \(O(N)\) mit \(N=10^6\). Dominant ist der Sweep über alle Vielfachen:
$$\sum_{a=2}^{N-1}\left\lfloor\frac{N-1}{a}\right\rfloor = O(N\log N).$$
Die abschließende Summation ist nochmals \(O(N)\), also beträgt die Gesamtlaufzeit \(O(N\log N)\). Der Speicherbedarf liegt bei \(O(N)\) für das Array der \(\operatorname{mdrs}\)-Werte.
Her pozitif tam sayı \(n\) için \(\operatorname{dr}(n)\), rakamları tekrar tekrar toplayarak tek basamağa inince elde edilen dijital kök olsun. Eğer
$$n=f_1f_2\cdots f_k,\qquad f_i \ge 2,$$
ise bu çarpımsal ayrışımın dijital-kök toplamını
$$\operatorname{drs}(f_1,\dots,f_k)=\sum_{i=1}^{k}\operatorname{dr}(f_i)$$
diye tanımlayalım. İlgilendiğimiz büyüklük
$$\operatorname{mdrs}(n)=\max \operatorname{drs}(f_1,\dots,f_k)$$
olup burada maksimum, \(n\)'in tüm \(\ge 2\) çarpanlı ayrışımları üzerinde alınır; \(n\)'in tek başına bırakıldığı trivial ayrışım da buna dahildir. Problem,
$$\sum_{n=2}^{10^6-1}\operatorname{mdrs}(n)$$
toplamını istemektedir. Bir milyondan küçük her sayı için bütün çarpımsal ayrışımları tek tek denemek çok büyük tekrar üretir. Çözüm bunun yerine \(\operatorname{mdrs}\) fonksiyonunu factor-pair tabanlı bir dinamik programa dönüştürür.
Temel fikir şudur: daha küçük sayıların en iyi değerleri biliniyorsa, daha büyük bir bileşik sayının en iyi değeri \(n=ab\) biçimindeki bir bölmeden üretilebilir.
\(n \ge 1\) için dijital kök doğrudan
$$\operatorname{dr}(n)=1+((n-1)\bmod 9)$$
formülüyle verilir. Dolayısıyla \(\operatorname{dr}(n)\) her zaman \(1,2,\dots,9\) kümesindedir ve 9'un katlarının dijital kökü 9 olur. Eğer \(n\)'i hiç parçalamazsak skor yalnızca \(\operatorname{dr}(n)\)'dir. Bu da \(\operatorname{mdrs}(n)\) için başlangıç değerini verir.
Şu trivial olmayan ayrışımı alın:
$$n=f_1f_2\cdots f_k,\qquad k\ge 2.$$
İlk faktörü \(a=f_1\), kalanların çarpımını da \(b=f_2\cdots f_k\) olarak gruplayalım. O zaman \(n=ab\) ve \(a,b\ge 2\). Orijinal ayrışımın skoru en fazla \(\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\) olabilir. Tersine, \(n=ab\) olan her bölme için \(a\) ile \(b\)'nin en iyi ayrışımlarını birleştirmek, tam olarak bu toplamı veren bir \(n\) ayrışımı üretir. Bu yüzden
$$\operatorname{mdrs}(n)=\max\!\left(\operatorname{dr}(n),\max_{\substack{ab=n\\a,b\ge 2}}\bigl(\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\bigr)\right).$$
Üç uygulamanın da dayandığı ana formül budur. Asal sayılar iç maksimuma girmez; dolayısıyla onlar için değer \(\operatorname{dr}(n)\) olarak kalır. Bileşik sayılar ise kendilerine en çok katkı yapan uygun çarpan çiftiyle iyileşir.
Tablo başlangıçta
$$\operatorname{mdrs}(n)=\operatorname{dr}(n)\qquad (1\le n<10^6)$$
olarak doldurulur. Sonra her \(p=ab\) çarpımı için
$$\operatorname{mdrs}(p)\leftarrow \max\!\bigl(\operatorname{mdrs}(p),\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\bigr)$$
gevşetmesi uygulanır. Buradaki kritik nokta döngü sırasının doğruluğudur. Dış döngü bir \(a\) değerine ulaştığında, \(a\)'nın bütün gerçek ayrışımları daha önce işlenmiştir; çünkü \(a\)'yı oluşturan her çarpan çifti daha küçük bir sol çarpan kullanır. Bu nedenle o anda \(\operatorname{mdrs}(a)\) artık kesindir. Eğer eşlik eden \(b\) daha büyükse ve sonra daha iyi bir değere ulaşırsa, aynı ürün \(p=ab\) dış döngü \(b\)'ye geldiğinde yeniden görülecektir. Böylece her sırasız çarpan çifti, iki bileşen değeri de kesinleştikten sonra en az bir kez değerlendirilmiş olur; bütün çoklular üzerinde tek geçiş yeterlidir.
Doğrudan dijital kök \(\operatorname{dr}(24)=6\) olduğu için başlangıç değeri 6'dır. Gerçek çarpan çiftleri
$$24=2\cdot 12=3\cdot 8=4\cdot 6$$
şeklindedir. Daha önce hesaplanmış küçük değerleri kullanırsak
$$\operatorname{mdrs}(2)+\operatorname{mdrs}(12)=2+8=10,$$
$$\operatorname{mdrs}(3)+\operatorname{mdrs}(8)=3+8=11,$$
$$\operatorname{mdrs}(4)+\operatorname{mdrs}(6)=4+6=10$$
elde edilir. O halde
$$\operatorname{mdrs}(24)=11,$$
ve bu değer \(24=3\cdot 8\) ayrışımından gelir. Bu örnek önemlidir; çünkü problemin yalnızca dijital kökü hesaplamaktan ibaret olmadığını, en iyi çarpımsal ayrışımın \(\operatorname{dr}(n)\)'yi açıkça aşabildiğini gösterir.
C++, Python ve Java uygulamaları \(10^6\)'dan küçük sayılar için bir dizi ayırır. Her hücre önce kapalı form dijital kök formülüyle doldurulur; böylece her sayı, tek parçalı trivial ayrışımının skoru ile başlar.
Ana tarama, dış çarpan \(a\)'yı 2'den başlayarak artırır ve sonra \(2a,3a,4a,\dots\) çoklularını gezer. Her \(p\) çoklusu için eşlik eden çarpan \(b=p/a\) olur; dolayısıyla aday değer \(\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\) denenir. Bu aday mevcut değerden iyiyse tablo güncellenir. Uygulamalardan biri ayrıca tam çalışmadan önce bilinen \(\operatorname{mdrs}(24)=11\) kontrolünü yapar.
Tüm gevşetmeler bitince geriye doğrusal bir toplama kalır: \(n=2,3,\dots,10^6-1\) için \(\operatorname{mdrs}(n)\) değerleri toplanır. Üç dildeki sürümler sözdizimi bakımından farklı görünse de yürüttükleri matematiksel süreç aynıdır.
Tabloyu başlatmak \(N=10^6\) için \(O(N)\) zaman alır. Baskın maliyet çoklular taramasıdır:
$$\sum_{a=2}^{N-1}\left\lfloor\frac{N-1}{a}\right\rfloor = O(N\log N).$$
Son toplama bir kez daha \(O(N)\) sürer; dolayısıyla toplam zaman karmaşıklığı \(O(N\log N)\) olur. Bellek kullanımı ise \(\operatorname{mdrs}\) dizisi için \(O(N)\)'dir.
Para cada entero positivo \(n\), sea \(\operatorname{dr}(n)\) su raíz digital, obtenida sumando repetidamente sus cifras decimales hasta quedar con una sola cifra. Si
$$n=f_1f_2\cdots f_k,\qquad f_i \ge 2,$$
definimos la suma de raíces digitales de esa factorización multiplicativa como
$$\operatorname{drs}(f_1,\dots,f_k)=\sum_{i=1}^{k}\operatorname{dr}(f_i).$$
La cantidad central es
$$\operatorname{mdrs}(n)=\max \operatorname{drs}(f_1,\dots,f_k),$$
donde el máximo recorre todas las factorizaciones de \(n\) en enteros mayores o iguales que 2, incluyendo la factorización trivial de una sola pieza. El problema pide calcular
$$\sum_{n=2}^{10^6-1}\operatorname{mdrs}(n).$$
Buscar de manera exhaustiva todas las factorizaciones de cada número menor que un millón repetiría una gran cantidad de subproblemas. Por eso las implementaciones reformulan \(\operatorname{mdrs}\) como una programación dinámica sobre pares de factores.
La observación clave es que, una vez conocidos los mejores valores para los enteros más pequeños, el mejor valor de un compuesto mayor puede construirse a partir de una descomposición \(n=ab\).
Para \(n \ge 1\), la raíz digital viene dada por la fórmula cerrada
$$\operatorname{dr}(n)=1+((n-1)\bmod 9).$$
Así, \(\operatorname{dr}(n)\) siempre pertenece a \(\{1,2,\dots,9\}\), y los múltiplos de 9 tienen raíz digital 9. Si no factorizamos \(n\) en absoluto, su puntuación es simplemente \(\operatorname{dr}(n)\). Ese es el valor base de \(\operatorname{mdrs}(n)\).
Tomemos una factorización no trivial
$$n=f_1f_2\cdots f_k,\qquad k\ge 2.$$
Agrupemos los factores como \(a=f_1\) y \(b=f_2\cdots f_k\). Entonces \(n=ab\) con \(a,b\ge 2\), y la puntuación de la factorización original es a lo sumo \(\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\). A la inversa, para cualquier partición \(n=ab\), concatenar una factorización óptima de \(a\) con una factorización óptima de \(b\) produce una factorización de \(n\) con exactamente esa suma. Por tanto,
$$\operatorname{mdrs}(n)=\max\!\left(\operatorname{dr}(n),\max_{\substack{ab=n\\a,b\ge 2}}\bigl(\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\bigr)\right).$$
Esta es la fórmula central utilizada por las tres implementaciones. Los números primos no aparecen en el máximo interior, así que para ellos el valor permanece igual a \(\operatorname{dr}(n)\). Los compuestos mejoran mediante el par de factores propio que dé la suma más grande.
La tabla se inicializa con
$$\operatorname{mdrs}(n)=\operatorname{dr}(n)\qquad (1\le n<10^6).$$
Después, cada producto \(p=ab\) con \(a,b\ge 2\) sirve para relajar la entrada correspondiente:
$$\operatorname{mdrs}(p)\leftarrow \max\!\bigl(\operatorname{mdrs}(p),\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\bigr).$$
La parte delicada es justificar el orden de los bucles. Cuando el barrido exterior alcanza un valor \(a\), todas las factorizaciones propias de \(a\) ya fueron procesadas, porque cualquier par de factores de \(a\) tiene un factor izquierdo más pequeño. Así, \(\operatorname{mdrs}(a)\) ya es definitivo en ese momento. Si el factor compañero \(b\) es más grande y mejora más tarde, el mismo producto \(p=ab\) vuelve a aparecer cuando el barrido exterior llegue a \(b\). En consecuencia, cada par de factores no ordenado se considera al menos una vez después de que ambos valores parciales sean definitivos, y un solo recorrido por los múltiplos es suficiente.
La raíz digital directa es \(\operatorname{dr}(24)=6\), así que el valor base comienza en 6. Los pares de factores propios son
$$24=2\cdot 12=3\cdot 8=4\cdot 6.$$
Usando valores más pequeños ya calculados se obtiene
$$\operatorname{mdrs}(2)+\operatorname{mdrs}(12)=2+8=10,$$
$$\operatorname{mdrs}(3)+\operatorname{mdrs}(8)=3+8=11,$$
$$\operatorname{mdrs}(4)+\operatorname{mdrs}(6)=4+6=10.$$
Luego
$$\operatorname{mdrs}(24)=11,$$
alcanzado por la factorización \(24=3\cdot 8\). El ejemplo muestra por qué el problema no se reduce a calcular una sola raíz digital: la mejor descomposición multiplicativa puede superar claramente a \(\operatorname{dr}(n)\).
Las implementaciones en C++, Python y Java reservan un arreglo indexado por los enteros menores que \(10^6\). Cada posición se rellena primero con la fórmula cerrada de la raíz digital, de modo que cada número arranca con la puntuación de su descomposición trivial de un solo factor.
El barrido principal escoge un factor exterior \(a\) desde 2 en adelante y luego recorre los múltiplos \(2a,3a,4a,\dots\). Para cada múltiplo \(p\), el factor compañero es \(b=p/a\), así que se prueba el candidato \(\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\). Si ese candidato mejora el valor actual de \(p\), la tabla se actualiza. Una de las implementaciones también verifica antes de la ejecución completa el valor conocido \(\operatorname{mdrs}(24)=11\).
Una vez terminadas todas las relajaciones, solo queda una suma lineal: añadir \(\operatorname{mdrs}(n)\) para todos los \(n\) entre 2 y \(10^6-1\). Las tres versiones difieren solo en la sintaxis del lenguaje; la estructura matemática es idéntica.
Inicializar la tabla cuesta \(O(N)\) con \(N=10^6\). La fase dominante es el barrido sobre múltiplos:
$$\sum_{a=2}^{N-1}\left\lfloor\frac{N-1}{a}\right\rfloor = O(N\log N).$$
La acumulación final añade otro paso \(O(N)\), así que el tiempo total es \(O(N\log N)\). El uso de memoria es \(O(N)\) para el arreglo de valores \(\operatorname{mdrs}\).
对每个正整数 \(n\)，记 \(\operatorname{dr}(n)\) 为它的数字根，也就是不断把十进制各位数字相加，直到结果只剩下一位数。若
$$n=f_1f_2\cdots f_k,\qquad f_i \ge 2,$$
则把这组乘法分解的数字根总和定义为
$$\operatorname{drs}(f_1,\dots,f_k)=\sum_{i=1}^{k}\operatorname{dr}(f_i).$$
题目关心的是
$$\operatorname{mdrs}(n)=\max \operatorname{drs}(f_1,\dots,f_k),$$
其中最大值是在所有由不小于 2 的因子组成的乘法分解上取得的，平凡分解 \(n\) 本身也允许。最终要求计算
$$\sum_{n=2}^{10^6-1}\operatorname{mdrs}(n).$$
如果对每个小于一百万的整数都暴力枚举所有乘法分解，会产生大量重复子问题。三份实现的核心做法，是把 \(\operatorname{mdrs}\) 改写成一个按因子对推进的动态规划。
这道题真正需要抓住的对象，不是某个单独的分解，而是“一个整数在所有乘法分解中能达到的最大数字根和”。一旦把它写成关于因子对的递推式，整个问题就变成了自底向上的表格更新。
对 \(n \ge 1\)，数字根可以直接写成
$$\operatorname{dr}(n)=1+((n-1)\bmod 9).$$
因此 \(\operatorname{dr}(n)\) 总在 \(1,2,\dots,9\) 之间，9 的倍数的数字根等于 9。若完全不拆分 \(n\)，那么这一个因子的得分就是 \(\operatorname{dr}(n)\)。这给出了 \(\operatorname{mdrs}(n)\) 的最初下界，也是动态规划数组的初始值。
设 \(n\) 有一个非平凡乘法分解
$$n=f_1f_2\cdots f_k,\qquad k\ge 2.$$
把它重新分组为 \(a=f_1\) 与 \(b=f_2\cdots f_k\)，就有 \(n=ab\) 且 \(a,b\ge 2\)。原分解的数字根和不会超过 \(\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\)，因为 \(a\) 部分和 \(b\) 部分各自最多只能达到自己的最优值。反过来，只要给定任意一个分拆 \(n=ab\)，再把 \(a\) 与 \(b\) 各自的最优分解拼接起来，就能得到一个数字根和恰好等于 \(\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\) 的 \(n\) 的分解。因此有完全准确的公式
$$\operatorname{mdrs}(n)=\max\!\left(\operatorname{dr}(n),\max_{\substack{ab=n\\a,b\ge 2}}\bigl(\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\bigr)\right).$$
这正是三种语言实现共同使用的数学核心。素数没有真因子对，所以它们的值不会被改进，始终等于 \(\operatorname{dr}(n)\)。合数则会从所有真因子对中选出贡献最大的那一个。
实现先把表初始化为
$$\operatorname{mdrs}(n)=\operatorname{dr}(n)\qquad (1\le n<10^6).$$
随后，对每个 \(a,b\ge 2\) 且 \(p=ab\) 的乘积，尝试做更新
$$\operatorname{mdrs}(p)\leftarrow \max\!\bigl(\operatorname{mdrs}(p),\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\bigr).$$
关键难点在于说明循环顺序为什么正确。外层扫描走到某个 \(a\) 时，\(a\) 的所有真分解其实都已经处理过了，因为任何把 \(a\) 写成乘积的因子对，都有一个更小的左侧因子。也就是说，在 \(a\) 被拿去更新别的数时，\(\operatorname{mdrs}(a)\) 已经是最终值。若配对因子 \(b\) 更大，它可能还会在后面继续变优，但同一个乘积 \(p=ab\) 会在外层扫描走到 \(b\) 时再次出现。于是每个无序因子对至少会在“两边都已最终确定”的时刻被考察一次，整张表只需要一遍按倍数推进的扫描就能收敛。
先看平凡情况，\(\operatorname{dr}(24)=6\)，所以初始值是 6。24 的真因子对为
$$24=2\cdot 12=3\cdot 8=4\cdot 6.$$
这时利用已经求好的较小整数最优值，可得
$$\operatorname{mdrs}(2)+\operatorname{mdrs}(12)=2+8=10,$$
$$\operatorname{mdrs}(3)+\operatorname{mdrs}(8)=3+8=11,$$
$$\operatorname{mdrs}(4)+\operatorname{mdrs}(6)=4+6=10.$$
因此
$$\operatorname{mdrs}(24)=11.$$
最优分解是 \(24=3\cdot 8\)。这个例子正好说明：题目并不是单纯计算数字根，因为最优乘法分解产生的总和可以明显大于 \(\operatorname{dr}(n)\)。
C++、Python 和 Java 实现都会先分配一个长度接近 \(10^6\) 的数组。数组的每个位置先填入该整数的数字根，也就是把“只保留一个因子”的分解作为默认答案。
主循环按 \(a=2,3,4,\dots\) 向上扫描，并访问 \(2a,3a,4a,\dots\) 这些倍数。对于某个倍数 \(p\)，另一个因子自然是 \(b=p/a\)，于是尝试候选值 \(\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\)。如果它优于当前的 \(\operatorname{mdrs}(p)\)，就更新数组。三份实现的写法略有不同，但做的都是同一件事。另有一份实现会在完整计算前先检查已知结论 \(\operatorname{mdrs}(24)=11\)，作为小型正确性校验。
当所有乘积带来的松弛都处理完成后，剩下的工作只是把 \(2\) 到 \(10^6-1\) 的所有 \(\operatorname{mdrs}(n)\) 加起来。这里不再需要额外的数学技巧，只是对最终表做一次线性累加。
初始化数组需要 \(O(N)\) 时间，其中 \(N=10^6\)。主导开销来自按倍数扫描的阶段：
$$\sum_{a=2}^{N-1}\left\lfloor\frac{N-1}{a}\right\rfloor = O(N\log N).$$
最后的求和再花 \(O(N)\) 时间，因此总时间复杂度为 \(O(N\log N)\)。空间复杂度为 \(O(N)\)，对应保存整张 \(\operatorname{mdrs}\) 表的数组。
Для каждого положительного целого \(n\) обозначим через \(\operatorname{dr}(n)\) его цифровой корень, то есть результат многократного сложения десятичных цифр до получения одной цифры. Если
$$n=f_1f_2\cdots f_k,\qquad f_i \ge 2,$$
то сумму цифровых корней этого мультипликативного разложения определим как
$$\operatorname{drs}(f_1,\dots,f_k)=\sum_{i=1}^{k}\operatorname{dr}(f_i).$$
Основная величина задачи равна
$$\operatorname{mdrs}(n)=\max \operatorname{drs}(f_1,\dots,f_k),$$
где максимум берется по всем разложениям числа \(n\) на множители не меньше 2, включая тривиальное одноэлементное разложение \(n\) само по себе. Нужно вычислить
$$\sum_{n=2}^{10^6-1}\operatorname{mdrs}(n).$$
Полный перебор всех разложений для каждого числа меньше миллиона породил бы огромное количество повторяющихся подзадач. Поэтому решения переписывают \(\operatorname{mdrs}\) как динамику по парам множителей.
Главная идея состоит в том, что оптимальное значение для составного числа можно собрать из оптимальных значений его меньших множителей.
Для \(n \ge 1\) цифровой корень задается формулой
$$\operatorname{dr}(n)=1+((n-1)\bmod 9).$$
Следовательно, \(\operatorname{dr}(n)\) всегда лежит в множестве \(\{1,2,\dots,9\}\), а для кратных 9 значение равно 9. Если число \(n\) не раскладывать вообще, его вклад равен просто \(\operatorname{dr}(n)\). Именно это значение служит стартовой нижней границей для \(\operatorname{mdrs}(n)\).
Рассмотрим нетривиальное разложение
$$n=f_1f_2\cdots f_k,\qquad k\ge 2.$$
Сгруппируем множители как \(a=f_1\) и \(b=f_2\cdots f_k\). Тогда \(n=ab\) и \(a,b\ge 2\). Сумма цифровых корней исходного разложения не превосходит \(\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\), потому что каждая часть по отдельности не может превзойти свой оптимум. Обратно, для любого разбиения \(n=ab\) можно взять оптимальное разложение \(a\) и оптимальное разложение \(b\), а затем объединить их. Получится разложение \(n\) с точно такой суммой. Значит,
$$\operatorname{mdrs}(n)=\max\!\left(\operatorname{dr}(n),\max_{\substack{ab=n\\a,b\ge 2}}\bigl(\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\bigr)\right).$$
Это и есть центральная формула, лежащая в основе всех трех реализаций. Для простых чисел внутренний максимум пуст, поэтому значение остается равным \(\operatorname{dr}(n)\). Для составных чисел выбирается наилучшая собственная пара множителей.
Сначала таблица заполняется значениями
$$\operatorname{mdrs}(n)=\operatorname{dr}(n)\qquad (1\le n<10^6).$$
Затем для каждого произведения \(p=ab\) с \(a,b\ge 2\) выполняется релаксация
$$\operatorname{mdrs}(p)\leftarrow \max\!\bigl(\operatorname{mdrs}(p),\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\bigr).$$
Тонкий момент состоит в корректности порядка обхода. Когда внешний цикл доходит до числа \(a\), все собственные разложения числа \(a\) уже были обработаны, потому что любая пара множителей числа \(a\) содержит меньший левый множитель. Следовательно, в этот момент \(\operatorname{mdrs}(a)\) уже окончательно известно. Если второй множитель \(b\) больше и улучшится позже, то то же произведение \(p=ab\) встретится еще раз, когда внешний цикл дойдет до \(b\). Значит, каждая неупорядоченная пара множителей хотя бы один раз рассматривается в момент, когда оба частичных значения уже окончательны, и одного прохода по всем кратным достаточно.
Непосредственно \(\operatorname{dr}(24)=6\), поэтому базовое значение равно 6. Собственные пары множителей таковы:
$$24=2\cdot 12=3\cdot 8=4\cdot 6.$$
Используя уже найденные значения для меньших чисел, получаем
$$\operatorname{mdrs}(2)+\operatorname{mdrs}(12)=2+8=10,$$
$$\operatorname{mdrs}(3)+\operatorname{mdrs}(8)=3+8=11,$$
$$\operatorname{mdrs}(4)+\operatorname{mdrs}(6)=4+6=10.$$
Следовательно,
$$\operatorname{mdrs}(24)=11,$$
и максимум достигается на разложении \(24=3\cdot 8\). Этот пример хорошо показывает, что задача не сводится к одной цифровой корневой функции: оптимальная мультипликативная структура может дать существенно больший результат.
Реализации на C++, Python и Java создают массив для всех чисел меньше \(10^6\). Сначала в каждую ячейку записывается цифровой корень соответствующего числа, то есть значение для тривиального разложения из одного множителя.
Основной проход перебирает внешний множитель \(a=2,3,4,\dots\) и затем идет по кратным \(2a,3a,4a,\dots\). Для очередного кратного \(p\) второй множитель равен \(b=p/a\), после чего проверяется кандидат \(\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\). Если этот кандидат лучше текущего значения для \(p\), выполняется обновление массива. В одной из реализаций перед полным запуском дополнительно проверяется известное контрольное значение \(\operatorname{mdrs}(24)=11\).
После завершения всех релаксаций остается линейный проход по массиву: складываются значения \(\operatorname{mdrs}(n)\) для всех \(n\) от 2 до \(10^6-1\). Различия между тремя версиями только синтаксические; математический алгоритм у них один и тот же.
Инициализация массива стоит \(O(N)\) при \(N=10^6\). Доминирует проход по кратным:
$$\sum_{a=2}^{N-1}\left\lfloor\frac{N-1}{a}\right\rfloor = O(N\log N).$$
Финальное суммирование добавляет еще \(O(N)\), так что общая временная сложность равна \(O(N\log N)\). Память имеет порядок \(O(N)\), поскольку хранится массив значений \(\operatorname{mdrs}\).
لكل عدد صحيح موجب \(n\)، نرمز بـ \(\operatorname{dr}(n)\) إلى جذره الرقمي، أي الناتج من جمع الأرقام العشرية مرارًا حتى يبقى رقم واحد فقط. وإذا كان
$$n=f_1f_2\cdots f_k,\qquad f_i \ge 2,$$
فنعرّف مجموع الجذور الرقمية لهذا التحليل الضربي بالصيغة
$$\operatorname{drs}(f_1,\dots,f_k)=\sum_{i=1}^{k}\operatorname{dr}(f_i).$$
والكمية الأساسية في المسألة هي
$$\operatorname{mdrs}(n)=\max \operatorname{drs}(f_1,\dots,f_k),$$
حيث يؤخذ هذا العظم على جميع التحليلات الضربية للعدد \(n\) إلى عوامل لا تقل عن 2، مع السماح بالتحليل التافه ذي العامل الواحد \(n\) نفسه. والمطلوب حساب
$$\sum_{n=2}^{10^6-1}\operatorname{mdrs}(n).$$
الاستقصاء المباشر لكل التحليلات الممكنة لكل عدد أصغر من مليون سيكرر نفس المسائل الفرعية مرات كثيرة. لذلك تحوّل الحلول \(\operatorname{mdrs}\) إلى برمجة ديناميكية مبنية على أزواج العوامل.
الفكرة الحاسمة هي أن أفضل قيمة لعدد مركب كبير يمكن بناؤها من أفضل قيم لعوامل أصغر منه، ما دام لدينا تفكيك من الشكل \(n=ab\).
عندما \(n \ge 1\) فإن الجذر الرقمي يعطى مباشرةً بـ
$$\operatorname{dr}(n)=1+((n-1)\bmod 9).$$
إذًا تكون \(\operatorname{dr}(n)\) دائمًا واحدة من القيم \(1,2,\dots,9\)، وتكون مساويةً لـ 9 عند مضاعفات 9. وإذا لم نُحلّل \(n\) أصلًا، فالقيمة المقابلة له هي \(\operatorname{dr}(n)\) فقط. هذه هي قيمة البداية في جدول \(\operatorname{mdrs}(n)\).
خذ تحليلًا غير تافه للعدد
$$n=f_1f_2\cdots f_k,\qquad k\ge 2.$$
اجمع العوامل في مجموعتين: \(a=f_1\) و \(b=f_2\cdots f_k\). عندئذٍ \(n=ab\) مع \(a,b\ge 2\)، ولا يمكن أن تتجاوز قيمة التحليل الأصلي \(\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\)، لأن كل جزء منهما لا يستطيع تجاوز أفضل قيمة له وحده. وبالعكس، لكل تفكيك \(n=ab\) يمكن ضم أفضل تحليل لـ \(a\) مع أفضل تحليل لـ \(b\)، فنحصل على تحليل لـ \(n\) يحقق هذا المجموع تمامًا. لذلك نحصل على الصيغة
$$\operatorname{mdrs}(n)=\max\!\left(\operatorname{dr}(n),\max_{\substack{ab=n\\a,b\ge 2}}\bigl(\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\bigr)\right).$$
هذه هي الصيغة المركزية التي تعتمد عليها تطبيقات C++ وPython وJava. الأعداد الأولية لا تمتلك أزواج عوامل حقيقية، ولهذا تبقى قيمتها مساويةً لـ \(\operatorname{dr}(n)\). أما الأعداد المركبة فتأخذ أفضل تحسين ناتج من أفضل زوج عوامل مناسب.
يبدأ الجدول بالقيم
$$\operatorname{mdrs}(n)=\operatorname{dr}(n)\qquad (1\le n<10^6).$$
ثم يُستخدم كل حاصل ضرب \(p=ab\) مع \(a,b\ge 2\) لإجراء التحديث
$$\operatorname{mdrs}(p)\leftarrow \max\!\bigl(\operatorname{mdrs}(p),\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\bigr).$$
النقطة الدقيقة هنا هي صحة ترتيب الحلقات. عندما تصل الحلقة الخارجية إلى قيمة \(a\)، تكون جميع التحليلات الحقيقية للعدد \(a\) قد عولجت سابقًا، لأن كل زوج عوامل للعدد \(a\) يستعمل عاملًا أيسر أصغر منه. لذلك تكون \(\operatorname{mdrs}(a)\) قد استقرت نهائيًا عند تلك اللحظة. وإذا كان العامل المرافق \(b\) أكبر وما زال قابلاً للتحسن لاحقًا، فإن نفس الناتج \(p=ab\) سيظهر مرة أخرى عندما تصل الحلقة الخارجية إلى \(b\). وبذلك يُفحَص كل زوج عوامل غير مرتب مرة واحدة على الأقل بعد أن تكون القيمتان الجزئيتان قد استقرتا، ولهذا تكفي جولة واحدة على المضاعفات كلها.
أولًا لدينا \(\operatorname{dr}(24)=6\)، إذن قيمة البداية هي 6. وأزواج العوامل الحقيقية هي
$$24=2\cdot 12=3\cdot 8=4\cdot 6.$$
وباستخدام القيم الأصغر المحسوبة مسبقًا نحصل على
$$\operatorname{mdrs}(2)+\operatorname{mdrs}(12)=2+8=10,$$
$$\operatorname{mdrs}(3)+\operatorname{mdrs}(8)=3+8=11,$$
$$\operatorname{mdrs}(4)+\operatorname{mdrs}(6)=4+6=10.$$
إذن
$$\operatorname{mdrs}(24)=11,$$
ويتحقق هذا عند التحليل \(24=3\cdot 8\). هذا المثال يوضح مباشرةً أن المسألة ليست مجرد حساب جذر رقمي واحد، لأن أفضل تحليل ضربي قد يعطي مجموعًا أكبر بكثير من \(\operatorname{dr}(n)\).
تقوم تطبيقات C++ وPython وJava بإنشاء مصفوفة مفهرسة بالأعداد الأصغر من \(10^6\). ثم تُملأ كل خانة أولًا بالجذر الرقمي الموافق، بحيث يبدأ كل عدد بقيمة تحليله التافه ذي العامل الواحد.
تختار الحلقة الرئيسية عاملًا خارجيًا \(a\) ابتداءً من 2، ثم تمر على المضاعفات \(2a,3a,4a,\dots\). ولكل مضاعف \(p\) يكون العامل الآخر \(b=p/a\)، فتُجرَّب القيمة المرشحة \(\operatorname{mdrs}(a)+\operatorname{mdrs}(b)\). إذا كانت هذه القيمة أفضل من القيمة الحالية لـ \(p\)، تُحدَّث المصفوفة. وتحتوي إحدى النسخ أيضًا على فحص صغير قبل التنفيذ الكامل للتأكد من أن القيمة المعروفة \(\operatorname{mdrs}(24)=11\) صحيحة.
بعد اكتمال جميع التحديثات، لا يبقى إلا المرور خطيًا على الجدول وجمع \(\operatorname{mdrs}(n)\) لكل \(n\) من 2 حتى \(10^6-1\). الفروق بين اللغات الثلاث شكلية فقط؛ أما الخوارزمية الرياضية نفسها فواحدة.
تهيئة المصفوفة تكلف \(O(N)\) حيث \(N=10^6\). أما الكلفة المسيطرة فتأتي من المرور على المضاعفات:
$$\sum_{a=2}^{N-1}\left\lfloor\frac{N-1}{a}\right\rfloor = O(N\log N).$$
ثم تأتي عملية الجمع النهائية بكلفة \(O(N)\) إضافية، لذا يكون الزمن الكلي \(O(N\log N)\). أما الذاكرة فهي \(O(N)\) لتخزين مصفوفة قيم \(\operatorname{mdrs}\).