For integer bases \(b>a>1\), let \(F(a,b)\) be the greatest integer \(n\) whose base-\(a\) digits are identical to the base-\(b\) digits of \(2n\), or zero when no positive solution exists. Define \(G(a)=\sum_{b>a}F(a,b)\). We need \(\sum_{a=2}^{20}G(a)\).
The supplied checkpoints are \(F(3,4)=53\), \(F(9,10)=8152650\), and \(G(3)=72\). The first example is \(53=(1222)_3\) and \(106=(1222)_4\).
Write the common digit string as \(d_m\cdots d_1d_0\), where \(d_m>0\) and \(0\le d_i\le a-1\). These digits are automatically valid in base \(b\), since \(b>a\). The required property is exactly
$$n=\sum_{i=0}^{m}d_i a^i,\qquad 2n=\sum_{i=0}^{m}d_i b^i,$$
or, after subtraction,
$$\sum_{i=0}^{m}d_i(b^i-2a^i)=0.$$
At small indices, a nonzero digit contributes negatively to this last sum; at sufficiently large indices it contributes positively. The solution balances the two contributions.
Let
$$k=\min\{i\ge 0:b^i\ge2a^i\} =\left\lceil\frac{\log2}{\log(b/a)}\right\rceil.$$
Because \(b/a>1\), this index exists; because \(b^0=a^0=1\), it satisfies \(k\ge1\). The implementation finds it by multiplying exact integer powers, avoiding floating-point errors at the boundary.
For \(0\le i<k\), define the positive weights
$$w_i=2a^i-b^i>0, \qquad C=(a-1)\sum_{i=0}^{k-1}w_i.$$
The quantity \(C\) is the largest negative contribution that all lower positions can supply. Since each \(w_i<2a^i\),
$$C<2(a-1)\sum_{i=0}^{k-1}a^i=2(a^k-1)<2a^k.$$
Now let \(q_i=b^i-2a^i\). At the first position above \(k\),
$$q_{k+1}=bq_k+2(b-a)a^k\ge2a^k>C.$$
The recurrence \(q_{i+1}=bq_i+2(b-a)a^i\) also shows that these positive contributions increase for \(i\ge k\). Therefore even one nonzero digit above position \(k\) would outweigh all available negative contributions. Other nonnegative terms could only increase the imbalance. Consequently every solution has degree at most \(k\).
When \(q_k>0\), every positive solution must have a nonzero digit at position \(k\): a nonempty string confined to positions below \(k\) would make the balance strictly negative. Thus the original search over unbounded integers reduces to
$$d_kq_k=\sum_{i=0}^{k-1}d_iw_i, \qquad 0\le d_i\le a-1.$$
If \(b=2a\), then \(k=1\) and \(q_1=0\). The balance equation forces \(d_0=0\), while the cutoff already forbids every position above 1. The greatest allowed leading digit is \(a-1\), giving
$$\boxed{F(a,2a)=a(a-1)}.$$
This is the only case where \(q_k=0\). Indeed, if \((b/a)^k=2\), reduce \(b/a=u/v\) to lowest terms. From \(u^k=2v^k\), coprimality forces \(v=1\); then \(u^k=2\) forces \(u=2\) and \(k=1\). Handling this case separately also prevents division by zero.
If \(b\ge3a\), then \(k=1\), \(w_0=1\), and \(q_1=b-2a\ge a\). The lower capacity is only \(C=a-1\), so even \(d_1=1\) cannot be balanced. Hence
$$\boxed{F(a,b)=0\quad\text{for }b\ge3a}.$$
This proves the infinite sum is finite and permits the exact bound
$$G(a)=\sum_{b=a+1}^{3a-1}F(a,b).$$
Some bases inside this interval also have no positive solution; the algorithm returns zero for them automatically.
A capacity bound alone would not normally guarantee an exact representation: arbitrary bounded coin systems have gaps. These particular weights have a stronger property.
Let \(C_i=(a-1)\sum_{j=0}^{i-1}w_j\), so \(C_0=0\) and \(C_k=C\). A geometric-sum calculation gives
$$\begin{aligned} 1+C_i-w_i &=1+(a-1)\sum_{j=0}^{i-1}(2a^j-b^j)-(2a^i-b^i)\\ &=\frac{(b-a)(b^i-1)}{b-1}\ge0. \end{aligned}$$
Thus \(w_0=1\), and every subsequent positive weight satisfies
$$\boxed{w_i\le C_i+1}.$$
Inductively suppose positions below \(i\) can represent every integer in \([0,C_i]\). For a fixed choice \(d_i=t\), adding position \(i\) gives the integer interval \([tw_i,tw_i+C_i]\), with \(t=0,\ldots,a-1\). Consecutive intervals overlap or are adjacent because \(w_i\le C_i+1\). Their union is therefore every integer from 0 to \(C_i+(a-1)w_i=C_{i+1}\). Starting with the empty representation of zero proves that positions below \(k\) represent every integer in \([0,C]\).
The weights need not be increasing. The proof uses their digit-position order and the capacity of earlier positions, so no sorting assumption is needed.
Assume \(b\ne2a\), so \(q_k>0\). Feasibility requires \(d_kq_k\le C\) and \(d_k\le a-1\). Completeness of the lower weights proves these necessary conditions are sufficient. The largest feasible leading digit is therefore
$$\boxed{d_k=\min\left(a-1,\left\lfloor\frac{C}{q_k}\right\rfloor\right)}.$$
If this value is zero, there is no positive solution. Otherwise initialize the balance still to be supplied as \(R=d_kq_k\).
Process \(i=k-1,k-2,\ldots,0\), choosing
$$\boxed{d_i=\min\left(a-1,\left\lfloor\frac{R}{w_i}\right\rfloor\right), \qquad R\leftarrow R-d_iw_i.}$$
This is the largest digit at position \(i\) that does not overshoot the required balance. It always leaves a feasible remainder:
The lower positions can represent every integer in \([0,C_i]\), so either case preserves the invariant. At the end, \(C_0=0\), and the remainder is exactly zero.
For a fixed base and a bounded digit length, numerical order is the lexicographic order of the digits from most to least significant: increasing digit \(i\) by one adds \(a^i\), whereas all smaller positions combined can change the number by at most \(a^i-1\). We first maximize \(d_k\), then choose the greatest feasible value of each successive digit. Therefore the completed string represents the greatest valid \(n\), namely \(F(a,b)\).
The program reconstructs this number by Horner's rule, starting at \(d_k\) and applying \(n\leftarrow an+d_i\) at each lower position.
The first index with \(4^k\ge2\cdot3^k\) is \(k=3\). The weights, leading cost, and capacity are
$$(w_0,w_1,w_2)=(1,2,2),\qquad q_3=64-54=10, \qquad C=2(1+2+2)=10.$$
Consequently \(d_3=\min(2,10/10)=1\). The remaining balance is 10. Descending greedy chooses \(d_2=2\), leaving 6; \(d_1=2\), leaving 2; and \(d_0=2\), leaving zero. Therefore
$$n=(1222)_3=27+18+6+2=53, \qquad (1222)_4=64+32+8+2=106=2n.$$
The only nonzero terms for \(a=3\) are \(F(3,4)=53\), \(F(3,6)=6\), \(F(3,7)=8\), and \(F(3,8)=5\), giving \(G(3)=72\).
Lemma 1 (digit equation). Matching representations are equivalent to \(\sum_i d_i(b^i-2a^i)=0\) with \(0\le d_i<a\).
Lemma 2 (finite cutoff). Every nonzero digit above the first index \(k\) with \(b^k\ge2a^k\) contributes more than the combined negative capacity. Thus all valid strings have degree at most \(k\). The equality case is precisely \(b=2a\); and \(b\ge3a\) admits no positive solution.
Lemma 3 (complete lower weights). The identity \(1+C_i-w_i=(b-a)(b^i-1)/(b-1)\ge0\) and the interval induction show that the lower digits realize every integer between zero and their capacity.
Lemma 4 (maximum string). Lemma 3 makes the chosen leading digit feasible and proves that each subsequent greedy digit leaves a feasible remainder. Every chosen digit is the largest possible after the fixed prefix; therefore the resulting base-\(a\) value is the maximum valid value.
By Lemmas 1–4, largest_value(a,b) returns exactly \(F(a,b)\), including zero and the special case. Summing all \(a+1\le b<3a\) includes every possible nonzero term of \(G(a)\). The outer sum for \(2\le a\le20\) is consequently the requested answer.
largest_value handles \(b\ge3a\) and \(b=2a\), constructs the weights and capacity using integer powers, computes the best leading digit, and reconstructs the optimum with the descending greedy loop. sum_for_base evaluates the finite sum for one base; main adds the results for bases 2 through 20.
The C++ implementation uses unsigned 128-bit integers. Although the final answer fits in signed 64 bits, intermediate powers can exceed 64 bits: for \((a,b)=(20,21)\), \(b^{15}=68122318582951682301\). Python integers and Java BigInteger provide exact arithmetic for these same operations. No floating-point logarithms are needed in the implementation.
same_digits independently compares successive base remainders of \(n\) and \(2n\). The optional --self-test checks the published values, exhaustively compares against direct enumeration for \(2\le a\le7\) and \(a<b\le3a+2\), and checks the matching-digit property for every pair used by the final calculation. The proven degree bound supplies the brute-force upper limit \(n<a^{k+1}\). These checks test the implementation; the completeness and greedy arguments establish maximality for the full range.
For a single pair \((a,b)\), the construction and greedy pass use \(O(k)\) exact-integer arithmetic operations and \(O(k)\) stored weights, where \(k=\lceil\log2/\log(b/a)\rceil\). There are exactly 399 pairs in the main finite sum, and \(k\le15\) throughout \(2\le a\le20\). Memory is reused for each pair.
For a variable maximum base \(A\), the straightforward bound is \(O(A^2K)\) arithmetic operations and \(O(K)\) auxiliary integers, with \(K=\lceil\log2/\log((A+1)/A)\rceil=O(A)\). A sharper sum over base gaps gives \(O(A^2\log A)\) arithmetic operations: writing \(b=a+h\), \(k=O(1+a/h)\), and summing over \(1\le h<2a\) costs \(O(a\log a)\) for each \(a\). These are arithmetic-operation counts; arbitrary-precision operation costs also depend on operand length when \(A\) grows.
int values. Integer division // implements the required floor for the nonnegative quantities in the greedy step, preserving the feasibility inequalities without rounding error.BigInteger provides arbitrary-precision integer arithmetic and exact comparisons. Its addition, multiplication, subtraction, and integer-division operations support the same construction; because the operands divided here are nonnegative, divide gives the floor required by the formulas.unsigned __int128 as an extension on targets that support a suitable integer mode. This implementation needs more than 64 bits for some intermediate powers: \(21^{15}\) requires 66 bits, so those multiplications must already take place in the wider type.Für ganzzahlige Basen \(b>a>1\) sei \(F(a,b)\) die größte ganze Zahl \(n\), deren Ziffern zur Basis \(a\) mit den Ziffern von \(2n\) zur Basis \(b\) übereinstimmen; gibt es keine positive Lösung, ist der Wert null. Definiere \(G(a)=\sum_{b>a}F(a,b)\). Gesucht ist \(\sum_{a=2}^{20}G(a)\).
Die vorgegebenen Kontrollwerte sind \(F(3,4)=53\), \(F(9,10)=8152650\) und \(G(3)=72\). Das erste Beispiel lautet \(53=(1222)_3\) und \(106=(1222)_4\).
Schreibe die gemeinsame Ziffernfolge als \(d_m\cdots d_1d_0\), wobei \(d_m>0\) und \(0\le d_i\le a-1\). Wegen \(b>a\) sind diese Ziffern automatisch auch zur Basis \(b\) zulässig. Die verlangte Eigenschaft entspricht genau
$$n=\sum_{i=0}^{m}d_i a^i,\qquad 2n=\sum_{i=0}^{m}d_i b^i,$$
beziehungsweise nach Subtraktion
$$\sum_{i=0}^{m}d_i(b^i-2a^i)=0.$$
Bei kleinen Indizes trägt eine Ziffer ungleich null negativ zu dieser letzten Summe bei, bei hinreichend großen Indizes positiv. Eine Lösung gleicht diese beiden Beiträge aus.
Sei
$$k=\min\{i\ge 0:b^i\ge2a^i\} =\left\lceil\frac{\log2}{\log(b/a)}\right\rceil.$$
Wegen \(b/a>1\) existiert dieser Index; wegen \(b^0=a^0=1\) gilt \(k\ge1\). Die Implementierung ermittelt ihn durch Multiplikation exakter ganzzahliger Potenzen und vermeidet damit Gleitkommafehler an der Grenze.
Für \(0\le i<k\) definieren wir die positiven Gewichte
$$w_i=2a^i-b^i>0, \qquad C=(a-1)\sum_{i=0}^{k-1}w_i.$$
Die Größe \(C\) ist der größte Betrag des negativen Beitrags, den sämtliche niedrigeren Stellen zusammen liefern können. Da für jedes Gewicht \(w_i<2a^i\) gilt, folgt
$$C<2(a-1)\sum_{i=0}^{k-1}a^i=2(a^k-1)<2a^k.$$
Setze nun \(q_i=b^i-2a^i\). An der ersten Stelle oberhalb von \(k\) gilt
$$q_{k+1}=bq_k+2(b-a)a^k\ge2a^k>C.$$
Die Rekursion \(q_{i+1}=bq_i+2(b-a)a^i\) zeigt außerdem, dass diese positiven Beiträge für \(i\ge k\) wachsen. Bereits eine einzige Ziffer ungleich null oberhalb der Stelle \(k\) würde daher sämtliche verfügbaren negativen Beiträge übertreffen. Weitere nichtnegative Terme könnten das Ungleichgewicht nur vergrößern. Folglich hat jede Lösung höchstens Grad \(k\).
Für \(q_k>0\) muss jede positive Lösung an der Stelle \(k\) eine Ziffer ungleich null besitzen: Eine nichtleere Folge, die nur Stellen unterhalb von \(k\) verwendet, hätte eine streng negative Bilanz. Die ursprüngliche Suche über unbeschränkt große ganze Zahlen reduziert sich damit auf
$$d_kq_k=\sum_{i=0}^{k-1}d_iw_i, \qquad 0\le d_i\le a-1.$$
Ist \(b=2a\), so gelten \(k=1\) und \(q_1=0\). Die Bilanzgleichung erzwingt \(d_0=0\), während die bewiesene Schranke bereits alle Stellen oberhalb von 1 ausschließt. Die größte zulässige führende Ziffer ist \(a-1\), also
$$\boxed{F(a,2a)=a(a-1)}.$$
Dies ist der einzige Fall mit \(q_k=0\). Gilt nämlich \((b/a)^k=2\), so schreibe \(b/a=u/v\) als vollständig gekürzten Bruch. Aus \(u^k=2v^k\) und der Teilerfremdheit folgt \(v=1\); anschließend erzwingt \(u^k=2\) die Werte \(u=2\) und \(k=1\). Die gesonderte Behandlung verhindert zugleich eine Division durch null.
Ist \(b\ge3a\), so gelten \(k=1\), \(w_0=1\) und \(q_1=b-2a\ge a\). Die Kapazität der niedrigeren Stellen beträgt nur \(C=a-1\); selbst \(d_1=1\) kann deshalb nicht ausgeglichen werden. Somit
$$\boxed{F(a,b)=0\quad\text{for }b\ge3a}.$$
Damit ist die Endlichkeit der unendlichen Summe bewiesen, und es gilt die exakte Begrenzung
$$G(a)=\sum_{b=a+1}^{3a-1}F(a,b).$$
Auch für manche Basen innerhalb dieses Intervalls gibt es keine positive Lösung; für sie liefert der Algorithmus automatisch null.
Eine Kapazitätsschranke allein garantiert normalerweise keine exakte Darstellung: Beliebige Münzsysteme mit begrenzten Stückzahlen können Lücken haben. Die hier auftretenden Gewichte besitzen jedoch eine stärkere Eigenschaft.
Sei \(C_i=(a-1)\sum_{j=0}^{i-1}w_j\), also \(C_0=0\) und \(C_k=C\). Durch Auswertung der geometrischen Summen erhält man
$$\begin{aligned} 1+C_i-w_i &=1+(a-1)\sum_{j=0}^{i-1}(2a^j-b^j)-(2a^i-b^i)\\ &=\frac{(b-a)(b^i-1)}{b-1}\ge0. \end{aligned}$$
Damit ist \(w_0=1\), und jedes folgende positive Gewicht erfüllt
$$\boxed{w_i\le C_i+1}.$$
Nehmen wir induktiv an, dass die Stellen unterhalb von \(i\) jede ganze Zahl in \([0,C_i]\) darstellen können. Bei festem \(d_i=t\) liefert das Hinzufügen der Stelle \(i\) das ganzzahlige Intervall \([tw_i,tw_i+C_i]\), wobei \(t=0,\ldots,a-1\). Aufeinanderfolgende Intervalle überlappen sich oder grenzen unmittelbar aneinander, denn \(w_i\le C_i+1\). Ihre Vereinigung umfasst somit jede ganze Zahl von 0 bis \(C_i+(a-1)w_i=C_{i+1}\). Ausgehend von der leeren Darstellung der null beweist dies, dass die Stellen unterhalb von \(k\) jede ganze Zahl in \([0,C]\) darstellen.
Die Gewichte müssen nicht aufsteigend sein. Der Beweis verwendet ihre Reihenfolge nach Ziffernposition und die Kapazität der niedrigeren Stellen; eine Sortierungsannahme ist nicht erforderlich.
Es sei \(b\ne2a\), also \(q_k>0\). Für eine Lösung müssen \(d_kq_k\le C\) und \(d_k\le a-1\) gelten. Die lückenlose Darstellbarkeit durch die niedrigeren Gewichte beweist, dass diese notwendigen Bedingungen auch hinreichend sind. Die größte mögliche führende Ziffer ist daher
$$\boxed{d_k=\min\left(a-1,\left\lfloor\frac{C}{q_k}\right\rfloor\right)}.$$
Ist dieser Wert null, existiert keine positive Lösung. Andernfalls wird der noch auszugleichende Betrag mit \(R=d_kq_k\) initialisiert.
Durchlaufe \(i=k-1,k-2,\ldots,0\) und wähle jeweils
$$\boxed{d_i=\min\left(a-1,\left\lfloor\frac{R}{w_i}\right\rfloor\right), \qquad R\leftarrow R-d_iw_i.}$$
Dies ist die größte Ziffer an Stelle \(i\), die den erforderlichen Ausgleichsbetrag nicht überschreitet. Der verbleibende Rest ist stets darstellbar:
Die niedrigeren Stellen stellen jede ganze Zahl in \([0,C_i]\) dar; in beiden Fällen bleibt die Invariante daher erhalten. Am Ende gilt \(C_0=0\), und der Rest ist exakt null.
Bei fester Basis und beschränkter Ziffernzahl entspricht die numerische Reihenfolge der lexikografischen Reihenfolge der Ziffern von der höchsten zur niedrigsten Stelle: Wird Ziffer \(i\) um eins erhöht, wächst die Zahl um \(a^i\), während alle niedrigeren Stellen zusammen sie um höchstens \(a^i-1\) verändern können. Wir maximieren zunächst \(d_k\) und wählen anschließend für jede folgende Ziffer den größten möglichen Wert. Die vollständige Ziffernfolge stellt deshalb das größte zulässige \(n\), also \(F(a,b)\), dar.
Das Programm rekonstruiert diese Zahl mit dem Horner-Schema: Es beginnt bei \(d_k\) und wendet für jede niedrigere Stelle \(n\leftarrow an+d_i\) an.
Der erste Index mit \(4^k\ge2\cdot3^k\) ist \(k=3\). Gewichte, Kosten der führenden Ziffer und Kapazität sind
$$(w_0,w_1,w_2)=(1,2,2),\qquad q_3=64-54=10, \qquad C=2(1+2+2)=10.$$
Folglich ist \(d_3=\min(2,10/10)=1\). Der verbleibende Ausgleichsbetrag beträgt 10. Die absteigende Greedy-Auswahl setzt \(d_2=2\), sodass 6 verbleibt; danach \(d_1=2\), sodass 2 verbleibt; schließlich \(d_0=2\), sodass der Rest null ist. Daher
$$n=(1222)_3=27+18+6+2=53, \qquad (1222)_4=64+32+8+2=106=2n.$$
Die einzigen von null verschiedenen Terme für \(a=3\) sind \(F(3,4)=53\), \(F(3,6)=6\), \(F(3,7)=8\) und \(F(3,8)=5\); zusammen ergeben sie \(G(3)=72\).
Lemma 1 (Zifferngleichung). Übereinstimmende Darstellungen sind äquivalent zu \(\sum_i d_i(b^i-2a^i)=0\) mit \(0\le d_i<a\).
Lemma 2 (endliche Gradschranke). Jede Ziffer ungleich null oberhalb des ersten Index \(k\) mit \(b^k\ge2a^k\) trägt mehr bei als die gesamte negative Kapazität. Alle zulässigen Ziffernfolgen haben daher höchstens Grad \(k\). Gleichheit tritt genau für \(b=2a\) auf; für \(b\ge3a\) gibt es keine positive Lösung.
Lemma 3 (lückenlose niedrigere Gewichte). Die Identität \(1+C_i-w_i=(b-a)(b^i-1)/(b-1)\ge0\) und die Intervallinduktion zeigen, dass die niedrigeren Ziffern jede ganze Zahl zwischen null und ihrer Kapazität darstellen.
Lemma 4 (maximale Ziffernfolge). Lemma 3 stellt die Zulässigkeit der gewählten führenden Ziffer sicher und beweist, dass jede folgende Greedy-Ziffer einen darstellbaren Rest hinterlässt. Jede gewählte Ziffer ist nach dem bereits festgelegten Präfix die größtmögliche; somit ist der entstehende Wert zur Basis \(a\) der größte zulässige Wert.
Nach den Lemmata 1–4 liefert largest_value(a,b) genau \(F(a,b)\), einschließlich null und des Sonderfalls. Die Summe über alle \(a+1\le b<3a\) enthält jeden möglicherweise von null verschiedenen Term von \(G(a)\). Die äußere Summe für \(2\le a\le20\) ist folglich die gesuchte Antwort.
largest_value behandelt \(b\ge3a\) und \(b=2a\), bildet Gewichte und Kapazität aus ganzzahligen Potenzen, berechnet die optimale führende Ziffer und rekonstruiert das Optimum in der absteigenden Greedy-Schleife. sum_for_base wertet die endliche Summe für eine Basis aus; main addiert die Ergebnisse für die Basen 2 bis 20.
Die C++-Implementierung verwendet vorzeichenlose 128-Bit-Ganzzahlen. Obwohl das Endergebnis in eine vorzeichenbehaftete 64-Bit-Ganzzahl passt, können Zwischenpotenzen 64 Bit überschreiten: Für \((a,b)=(20,21)\) gilt \(b^{15}=68122318582951682301\). Die Ganzzahlen von Python und Javas BigInteger ermöglichen dieselben Operationen mit exakter Arithmetik. Die Implementierung benötigt keine Gleitkommalogarithmen.
same_digits vergleicht unabhängig die aufeinanderfolgenden Divisionsreste von \(n\) und \(2n\) in den jeweiligen Basen. Der optionale Aufruf mit --self-test prüft die veröffentlichten Werte, vergleicht für \(2\le a\le7\) und \(a<b\le3a+2\) vollständig mit direkter Enumeration und kontrolliert die Ziffernübereinstimmung für jedes Basenpaar der endgültigen Berechnung. Die bewiesene Gradschranke liefert die obere Grenze \(n<a^{k+1}\) für die vollständige Suche. Diese Prüfungen kontrollieren die Implementierung; die Darstellbarkeits- und Greedy-Beweise sichern die Maximalität im gesamten Bereich.
Für ein einzelnes Paar \((a,b)\) benötigen Aufbau und Greedy-Durchlauf \(O(k)\) exakte ganzzahlige Rechenoperationen und \(O(k)\) gespeicherte Gewichte, wobei \(k=\lceil\log2/\log(b/a)\rceil\). Die endliche Hauptsumme enthält genau 399 Paare, und im gesamten Bereich \(2\le a\le20\) gilt \(k\le15\). Der Speicher wird für jedes Paar wiederverwendet.
Bei einer variablen maximalen Basis \(A\) ergibt sich unmittelbar die Schranke \(O(A^2K)\) für die Zahl der Rechenoperationen und \(O(K)\) für die zusätzlich gespeicherten Ganzzahlen, mit \(K=\lceil\log2/\log((A+1)/A)\rceil=O(A)\). Eine genauere Summation über die Basisabstände liefert \(O(A^2\log A)\) Rechenoperationen: Mit \(b=a+h\) gilt \(k=O(1+a/h)\), und die Summe über \(1\le h<2a\) kostet für jedes \(a\) insgesamt \(O(a\log a)\). Dies sind Anzahlen arithmetischer Operationen; bei wachsendem \(A\) hängen die Kosten der Arithmetik mit beliebiger Genauigkeit zusätzlich von der Operandenlänge ab.
int-Werten berechnen. Die Ganzzahldivision // liefert für die nichtnegativen Größen des Greedy-Schritts die benötigte Abrundung und erhält die Machbarkeitsungleichungen ohne Rundungsfehler.BigInteger bietet Ganzzahlarithmetik beliebiger Genauigkeit und exakte Vergleiche. Addition, Multiplikation, Subtraktion und Ganzzahldivision setzen dieselbe Konstruktion um; da hier nur nichtnegative Operanden dividiert werden, liefert divide die in den Formeln benötigte Abrundung.unsigned __int128 als Erweiterung für Zielplattformen mit einem geeigneten Ganzzahlmodus. Einige Zwischenpotenzen dieser Implementierung benötigen mehr als 64 Bit: \(21^{15}\) benötigt 66 Bit, weshalb bereits die entsprechenden Multiplikationen im breiteren Typ erfolgen müssen.\(b>a>1\) tam sayı tabanları için \(F(a,b)\), \(a\) tabanındaki rakamları \(2n\) sayısının \(b\) tabanındaki rakamlarıyla aynı olan en büyük \(n\) tam sayısı olsun; pozitif çözüm yoksa değeri sıfır olsun. \(G(a)=\sum_{b>a}F(a,b)\) olarak tanımlanıyor. İstenen değer \(\sum_{a=2}^{20}G(a)\).
Verilen kontrol değerleri \(F(3,4)=53\), \(F(9,10)=8152650\) ve \(G(3)=72\). İlk örnekte \(53=(1222)_3\) ve \(106=(1222)_4\) eşitlikleri sağlanıyor.
Ortak rakam dizisini \(d_m\cdots d_1d_0\) biçiminde yazalım; burada \(d_m>0\) ve \(0\le d_i\le a-1\). \(b>a\) olduğundan bu rakamlar \(b\) tabanında da geçerlidir. İstenen özellik tam olarak şu eşitliklere karşılık gelir:
$$n=\sum_{i=0}^{m}d_i a^i,\qquad 2n=\sum_{i=0}^{m}d_i b^i,$$
Çıkarma işlemiyle eşdeğer olarak
$$\sum_{i=0}^{m}d_i(b^i-2a^i)=0.$$
Küçük indislerde sıfırdan farklı bir rakam bu son toplama negatif katkı yaparken yeterince büyük indislerde pozitif katkı yapar. Bir çözüm, bu iki katkıyı dengeler.
Şu indisi tanımlayalım:
$$k=\min\{i\ge 0:b^i\ge2a^i\} =\left\lceil\frac{\log2}{\log(b/a)}\right\rceil.$$
\(b/a>1\) olduğundan bu indis vardır; \(b^0=a^0=1\) olduğundan da \(k\ge1\) sağlanır. Uygulama, tam sayı kuvvetlerini çarparak bu indisi bulur ve böylece eşik yakınındaki kayan nokta hatalarını önler.
\(0\le i<k\) için pozitif ağırlıkları ve toplam kapasiteyi tanımlayalım:
$$w_i=2a^i-b^i>0, \qquad C=(a-1)\sum_{i=0}^{k-1}w_i.$$
\(C\), bütün alt basamakların birlikte sağlayabileceği negatif katkının en büyük mutlak değeridir. Her \(w_i<2a^i\) olduğundan
$$C<2(a-1)\sum_{i=0}^{k-1}a^i=2(a^k-1)<2a^k.$$
Şimdi \(q_i=b^i-2a^i\) olsun. \(k\)'nin hemen üstündeki basamakta
$$q_{k+1}=bq_k+2(b-a)a^k\ge2a^k>C.$$
\(q_{i+1}=bq_i+2(b-a)a^i\) bağıntısı, bu pozitif katkıların \(i\ge k\) için arttığını da gösterir. Dolayısıyla \(k\) basamağının üstündeki tek bir sıfırdan farklı rakam bile mevcut negatif katkıların tümünü aşar. Diğer negatif olmayan terimler bu dengesizliği ancak büyütebilir. Bu nedenle her çözümün derecesi en fazla \(k\)'dir.
\(q_k>0\) olduğunda her pozitif çözümün \(k\) basamağında sıfırdan farklı bir rakamı bulunmalıdır: Yalnızca \(k\)'nin altındaki basamaklardan oluşan sıfırdan farklı bir gösterim dengeyi kesin olarak negatif yapar. Böylece büyüklüğü sınırsız tam sayılar üzerindeki başlangıç araması şu denkleme indirgenir:
$$d_kq_k=\sum_{i=0}^{k-1}d_iw_i, \qquad 0\le d_i\le a-1.$$
\(b=2a\) ise \(k=1\) ve \(q_1=0\) olur. Denge denklemi \(d_0=0\) olmasını zorunlu kılar; kanıtlanan derece sınırı ise 1'in üstündeki bütün basamakları zaten dışlar. İzin verilen en büyük baştaki rakam \(a-1\) olduğundan
$$\boxed{F(a,2a)=a(a-1)}.$$
\(q_k=0\) olan tek durum budur. Gerçekten de \((b/a)^k=2\) ise \(b/a=u/v\) kesrini en sade biçimde yazalım. \(u^k=2v^k\) eşitliğinde aralarında asallık \(v=1\) olmasını zorunlu kılar; ardından \(u^k=2\) eşitliği \(u=2\) ve \(k=1\) sonuçlarını verir. Bu durumu ayrı ele almak, sıfıra bölmeyi de önler.
\(b\ge3a\) ise \(k=1\), \(w_0=1\) ve \(q_1=b-2a\ge a\) olur. Alt basamakların kapasitesi yalnızca \(C=a-1\) olduğundan \(d_1=1\) bile dengelenemez. Dolayısıyla
$$\boxed{F(a,b)=0\quad\text{for }b\ge3a}.$$
Bu, sonsuz toplamın sonlu olduğunu kanıtlar ve toplamı tam olarak şu aralıkla sınırlar:
$$G(a)=\sum_{b=a+1}^{3a-1}F(a,b).$$
Bu aralıktaki bazı tabanlarda da pozitif çözüm yoktur; algoritma onlar için kendiliğinden sıfır döndürür.
Tek başına bir kapasite sınırı, genellikle tam bir gösterimi garanti etmez: Her değerden sınırlı sayıda kullanılabilen gelişigüzel para sistemlerinde boşluklar bulunabilir. Buradaki ağırlıklar ise daha güçlü bir özelliğe sahiptir.
\(C_i=(a-1)\sum_{j=0}^{i-1}w_j\) olsun; böylece \(C_0=0\) ve \(C_k=C\). Geometrik toplamlar hesaplandığında
$$\begin{aligned} 1+C_i-w_i &=1+(a-1)\sum_{j=0}^{i-1}(2a^j-b^j)-(2a^i-b^i)\\ &=\frac{(b-a)(b^i-1)}{b-1}\ge0. \end{aligned}$$
Dolayısıyla \(w_0=1\) olur ve sonraki her pozitif ağırlık şu eşitsizliği sağlar:
$$\boxed{w_i\le C_i+1}.$$
Tümevarım varsayımı olarak \(i\)'nin altındaki basamakların \([0,C_i]\) aralığındaki her tam sayıyı gösterebildiğini kabul edelim. Sabit bir \(d_i=t\) seçimi için \(i\) basamağını eklemek, \(t=0,\ldots,a-1\) olmak üzere \([tw_i,tw_i+C_i]\) tam sayı aralığını verir. \(w_i\le C_i+1\) olduğundan ardışık aralıklar kesişir veya aralarında tam sayı boşluğu kalmadan bitişir. Bu nedenle birleşimleri, 0'dan \(C_i+(a-1)w_i=C_{i+1}\)'e kadar her tam sayıyı içerir. Sıfırın boş gösteriminden başlayan bu tümevarım, \(k\)'nin altındaki basamakların \([0,C]\) aralığındaki her tam sayıyı gösterebildiğini kanıtlar.
Ağırlıkların artan sırada olması gerekmez. Kanıt, basamak indislerine göre sırayı ve daha alt basamakların kapasitesini kullanır; ağırlıkların sıralı olduğu varsayımına ihtiyaç yoktur.
\(b\ne2a\), dolayısıyla \(q_k>0\) olduğunu varsayalım. Bir çözüm için \(d_kq_k\le C\) ve \(d_k\le a-1\) gereklidir. Alt ağırlıkların aralıktaki bütün tam sayıları gösterebilmesi, bu gerekli koşulların yeterli de olduğunu kanıtlar. Bu nedenle mümkün olan en büyük baştaki rakam
$$\boxed{d_k=\min\left(a-1,\left\lfloor\frac{C}{q_k}\right\rfloor\right)}.$$
Bu değer sıfırsa pozitif çözüm yoktur. Aksi hâlde, henüz karşılanması gereken denge miktarını \(R=d_kq_k\) olarak başlatırız.
\(i=k-1,k-2,\ldots,0\) sırasıyla ilerleyerek şu seçimleri yaparız:
$$\boxed{d_i=\min\left(a-1,\left\lfloor\frac{R}{w_i}\right\rfloor\right), \qquad R\leftarrow R-d_iw_i.}$$
Bu, \(i\) basamağında gereken denge miktarını aşmayan en büyük rakamdır. Her zaman alt basamaklarla gösterilebilen bir kalan bırakır:
Alt basamaklar \([0,C_i]\) aralığındaki her tam sayıyı gösterebildiğinden iki durumda da değişmez korunur. Sonunda \(C_0=0\) olur ve kalan tam olarak sıfıra iner.
Sabit bir tabanda, basamak sayısı sınırlı gösterimlerin sayısal sırası, rakamların en yüksek basamaktan en düşüğe doğru sözlük sırasıyla aynıdır: \(i\) rakamını bir artırmak sayıya \(a^i\) eklerken daha alt basamakların tamamı sayıyı en fazla \(a^i-1\) değiştirebilir. Önce \(d_k\)'yi en büyük yapar, sonra gelen her rakam için mümkün olan en büyük değeri seçeriz. Dolayısıyla tamamlanan rakam dizisi en büyük geçerli \(n\)'yi, yani \(F(a,b)\)'yi gösterir.
Program bu sayıyı Horner yöntemiyle yeniden oluşturur: \(d_k\)'den başlar ve her alt basamakta \(n\leftarrow an+d_i\) güncellemesini uygular.
\(4^k\ge2\cdot3^k\) koşulunu sağlayan ilk indis \(k=3\)'tür. Ağırlıklar, baştaki rakamın birim katkısı ve kapasite şöyledir:
$$(w_0,w_1,w_2)=(1,2,2),\qquad q_3=64-54=10, \qquad C=2(1+2+2)=10.$$
Böylece \(d_3=\min(2,10/10)=1\) olur. Karşılanması gereken kalan denge 10'dur. Yüksek basamaktan başlayan açgözlü seçim \(d_2=2\) ile 6 bırakır; \(d_1=2\) ile 2 bırakır; \(d_0=2\) ile kalanı sıfırlar. Dolayısıyla
$$n=(1222)_3=27+18+6+2=53, \qquad (1222)_4=64+32+8+2=106=2n.$$
\(a=3\) için sıfırdan farklı tek terimler \(F(3,4)=53\), \(F(3,6)=6\), \(F(3,7)=8\) ve \(F(3,8)=5\) olduğundan \(G(3)=72\) elde edilir.
Lemma 1 (rakam denklemi). Gösterimlerin aynı olması, \(0\le d_i<a\) koşuluyla birlikte \(\sum_i d_i(b^i-2a^i)=0\) denklemine eşdeğerdir.
Lemma 2 (sonlu derece sınırı). \(b^k\ge2a^k\) koşulunu sağlayan ilk \(k\) indisinin üstündeki her sıfırdan farklı rakam, toplam negatif kapasiteden daha büyük katkı yapar. Bu nedenle tüm geçerli rakam dizilerinin derecesi en fazla \(k\)'dir. Eşitlik durumu tam olarak \(b=2a\)'dır; \(b\ge3a\) için pozitif çözüm yoktur.
Lemma 3 (alt ağırlıklarla eksiksiz gösterim). \(1+C_i-w_i=(b-a)(b^i-1)/(b-1)\ge0\) özdeşliği ve aralıklar üzerinden tümevarım, alt rakamların sıfır ile kapasiteleri arasındaki her tam sayıyı oluşturabildiğini gösterir.
Lemma 4 (en büyük rakam dizisi). Lemma 3, seçilen baştaki rakamın uygulanabilir olmasını sağlar ve sonraki her açgözlü seçimin gösterilebilir bir kalan bıraktığını kanıtlar. Seçilen her rakam, sabitlenmiş önceki rakamlardan sonra mümkün olan en büyük rakamdır; dolayısıyla elde edilen \(a\) tabanındaki değer en büyük geçerli değerdir.
Lemma 1–4 uyarınca largest_value(a,b), sıfır ve özel durum dâhil tam olarak \(F(a,b)\)'yi döndürür. Tüm \(a+1\le b<3a\) değerlerini toplamak, \(G(a)\)'nın sıfırdan farklı olabilecek bütün terimlerini kapsar. Dolayısıyla \(2\le a\le20\) için dış toplam, istenen cevaptır.
largest_value, \(b\ge3a\) ve \(b=2a\) durumlarını ele alır; tam sayı kuvvetleriyle ağırlıkları ve kapasiteyi oluşturur; en iyi baştaki rakamı hesaplar ve yüksek basamaktan başlayan açgözlü döngüyle en büyük çözümü kurar. sum_for_base, tek bir taban için sonlu toplamı hesaplar; main ise 2'den 20'ye kadar tabanların sonuçlarını toplar.
C++ uygulaması işaretsiz 128 bit tam sayılar kullanır. Son cevap işaretli 64 bite sığsa da ara kuvvetler 64 biti aşabilir: \((a,b)=(20,21)\) için \(b^{15}=68122318582951682301\). Python tam sayıları ve Java BigInteger sınıfı aynı işlemler için tam aritmetik sağlar. Uygulamada kayan noktalı logaritmalara ihtiyaç yoktur.
same_digits, \(n\) ve \(2n\)'nin ilgili tabanlara göre ardışık bölme kalanlarını bağımsız olarak karşılaştırır. İsteğe bağlı --self-test, yayımlanmış değerleri kontrol eder; \(2\le a\le7\) ve \(a<b\le3a+2\) için doğrudan taramayla eksiksiz karşılaştırma yapar ve son hesaplamada kullanılan her taban çifti için rakamların aynı olma özelliğini denetler. Kanıtlanan derece sınırı, kaba kuvvet taramasına \(n<a^{k+1}\) üst sınırını verir. Bu kontroller uygulamayı sınar; eksiksiz gösterim ve açgözlü seçim kanıtları ise tüm aralıkta en büyük çözümün bulunduğunu gösterir.
Tek bir \((a,b)\) çifti için ağırlıkların kurulması ve açgözlü geçiş, \(k=\lceil\log2/\log(b/a)\rceil\) olmak üzere \(O(k)\) tam sayı aritmetik işlemi ve saklanan \(O(k)\) ağırlık gerektirir. Ana sonlu toplamda tam olarak 399 çift vardır ve \(2\le a\le20\) aralığının tamamında \(k\le15\) sağlanır. Her çift için aynı bellek yeniden kullanılır.
En büyük taban değişken bir \(A\) olduğunda doğrudan sınır, \(K=\lceil\log2/\log((A+1)/A)\rceil=O(A)\) olmak üzere \(O(A^2K)\) aritmetik işlem ve \(O(K)\) yardımcı tam sayıdır. Taban farkları üzerinden daha sıkı bir toplama \(O(A^2\log A)\) aritmetik işlem verir: \(b=a+h\) yazıldığında \(k=O(1+a/h)\) olur ve \(1\le h<2a\) üzerinden toplam, her \(a\) için \(O(a\log a)\) maliyetlidir. Bunlar aritmetik işlem sayılarıdır; \(A\) büyüdüğünde keyfi duyarlıklı işlemlerin maliyeti, işlenen sayıların uzunluğuna da bağlıdır.
int değerleriyle tam olarak hesaplanabilir. // tam sayı bölmesi, açgözlü adımdaki negatif olmayan nicelikler için gereken aşağı yuvarlamayı yapar ve yapılabilirlik eşitsizliklerini yuvarlama hatası olmadan korur.BigInteger, keyfî duyarlıkta tam sayı aritmetiği ve kesin karşılaştırmalar sağlar. Toplama, çarpma, çıkarma ve tam sayı bölmesi aynı matematiksel yapıyı uygular; burada bölünen nicelikler negatif olmadığı için divide, formüllerde gereken aşağı yuvarlanmış bölümü verir.unsigned __int128 türünü uygun tam sayı kipini destekleyen hedeflerde kullanılabilen bir uzantı olarak belgeler. Bu uygulamadaki bazı ara kuvvetler 64 biti aşar: \(21^{15}\) için 66 bit gerekir; dolayısıyla ilgili çarpmalar da en başından geniş türde yapılmalıdır.Para bases enteras \(b>a>1\), sea \(F(a,b)\) el mayor entero \(n\) cuyos dígitos en base \(a\) coinciden con los dígitos de \(2n\) en base \(b\), o cero si no existe ninguna solución positiva. Definimos \(G(a)=\sum_{b>a}F(a,b)\). Debemos calcular \(\sum_{a=2}^{20}G(a)\).
Los valores de comprobación proporcionados son \(F(3,4)=53\), \(F(9,10)=8152650\) y \(G(3)=72\). El primer ejemplo es \(53=(1222)_3\) y \(106=(1222)_4\).
Escribimos la secuencia común de dígitos como \(d_m\cdots d_1d_0\), donde \(d_m>0\) y \(0\le d_i\le a-1\). Estos dígitos también son válidos en base \(b\), puesto que \(b>a\). La propiedad requerida equivale exactamente a
$$n=\sum_{i=0}^{m}d_i a^i,\qquad 2n=\sum_{i=0}^{m}d_i b^i,$$
o, tras restar,
$$\sum_{i=0}^{m}d_i(b^i-2a^i)=0.$$
En los índices pequeños, un dígito distinto de cero aporta una contribución negativa a esta última suma; en los índices suficientemente grandes, su contribución es positiva. La solución equilibra ambas contribuciones.
Sea
$$k=\min\{i\ge 0:b^i\ge2a^i\} =\left\lceil\frac{\log2}{\log(b/a)}\right\rceil.$$
Como \(b/a>1\), este índice existe; como \(b^0=a^0=1\), satisface \(k\ge1\). La implementación lo encuentra multiplicando potencias enteras exactas, lo que evita errores de coma flotante en el punto de corte.
Para \(0\le i<k\), definimos los pesos positivos
$$w_i=2a^i-b^i>0, \qquad C=(a-1)\sum_{i=0}^{k-1}w_i.$$
La cantidad \(C\) es la máxima contribución negativa que pueden aportar conjuntamente todas las posiciones inferiores. Como cada \(w_i<2a^i\),
$$C<2(a-1)\sum_{i=0}^{k-1}a^i=2(a^k-1)<2a^k.$$
Ahora sea \(q_i=b^i-2a^i\). En la primera posición por encima de \(k\),
$$q_{k+1}=bq_k+2(b-a)a^k\ge2a^k>C.$$
La recurrencia \(q_{i+1}=bq_i+2(b-a)a^i\) también muestra que estas contribuciones positivas aumentan para \(i\ge k\). Por tanto, un solo dígito distinto de cero por encima de la posición \(k\) ya superaría toda la contribución negativa disponible. Los demás términos no negativos solo podrían aumentar el desequilibrio. En consecuencia, toda solución tiene grado a lo sumo \(k\).
Cuando \(q_k>0\), toda solución positiva debe tener un dígito distinto de cero en la posición \(k\): una secuencia no nula limitada a las posiciones inferiores a \(k\) haría que el balance fuera estrictamente negativo. Así, la búsqueda original entre enteros sin cota se reduce a
$$d_kq_k=\sum_{i=0}^{k-1}d_iw_i, \qquad 0\le d_i\le a-1.$$
Si \(b=2a\), entonces \(k=1\) y \(q_1=0\). La ecuación de equilibrio obliga a que \(d_0=0\), mientras que la cota ya excluye todas las posiciones por encima de 1. El mayor dígito inicial permitido es \(a-1\), de modo que
$$\boxed{F(a,2a)=a(a-1)}.$$
Este es el único caso en que \(q_k=0\). En efecto, si \((b/a)^k=2\), reducimos \(b/a=u/v\) a una fracción irreducible. De \(u^k=2v^k\), la coprimalidad obliga a que \(v=1\); entonces \(u^k=2\) obliga a que \(u=2\) y \(k=1\). Tratar este caso por separado también evita dividir entre cero.
Si \(b\ge3a\), entonces \(k=1\), \(w_0=1\) y \(q_1=b-2a\ge a\). La capacidad de las posiciones inferiores es solo \(C=a-1\), por lo que ni siquiera \(d_1=1\) puede equilibrarse. Por tanto,
$$\boxed{F(a,b)=0\quad\text{for }b\ge3a}.$$
Esto demuestra que la suma infinita es finita y permite establecer la cota exacta
$$G(a)=\sum_{b=a+1}^{3a-1}F(a,b).$$
Algunas bases dentro de este intervalo tampoco tienen solución positiva; el algoritmo devuelve cero automáticamente en esos casos.
En general, una cota de capacidad no basta para garantizar una representación exacta: los sistemas arbitrarios de monedas con cantidades limitadas pueden dejar huecos. Estos pesos concretos poseen una propiedad más fuerte.
Sea \(C_i=(a-1)\sum_{j=0}^{i-1}w_j\), de modo que \(C_0=0\) y \(C_k=C\). Mediante la fórmula de la suma geométrica obtenemos
$$\begin{aligned} 1+C_i-w_i &=1+(a-1)\sum_{j=0}^{i-1}(2a^j-b^j)-(2a^i-b^i)\\ &=\frac{(b-a)(b^i-1)}{b-1}\ge0. \end{aligned}$$
Por tanto, \(w_0=1\), y cada peso positivo posterior satisface
$$\boxed{w_i\le C_i+1}.$$
Supongamos por inducción que las posiciones inferiores a \(i\) pueden representar todos los enteros de \([0,C_i]\). Para una elección fija \(d_i=t\), añadir la posición \(i\) produce el intervalo de enteros \([tw_i,tw_i+C_i]\), con \(t=0,\ldots,a-1\). Los intervalos consecutivos se solapan o son adyacentes, porque \(w_i\le C_i+1\). Por consiguiente, su unión contiene todos los enteros desde 0 hasta \(C_i+(a-1)w_i=C_{i+1}\). Partiendo de la representación vacía de cero, queda demostrado que las posiciones inferiores a \(k\) representan todos los enteros de \([0,C]\).
Los pesos no tienen por qué ser crecientes. La demostración utiliza su orden por posición del dígito y la capacidad de las posiciones anteriores, por lo que no necesita ninguna hipótesis de ordenación por magnitud.
Supongamos que \(b\ne2a\), de modo que \(q_k>0\). La factibilidad exige \(d_kq_k\le C\) y \(d_k\le a-1\). La cobertura completa de los pesos inferiores demuestra que estas condiciones necesarias también son suficientes. Por tanto, el mayor dígito inicial factible es
$$\boxed{d_k=\min\left(a-1,\left\lfloor\frac{C}{q_k}\right\rfloor\right)}.$$
Si este valor es cero, no existe ninguna solución positiva. En caso contrario, inicializamos la contribución que aún debe aportarse como \(R=d_kq_k\).
Procesamos \(i=k-1,k-2,\ldots,0\), eligiendo
$$\boxed{d_i=\min\left(a-1,\left\lfloor\frac{R}{w_i}\right\rfloor\right), \qquad R\leftarrow R-d_iw_i.}$$
Este es el mayor dígito en la posición \(i\) que no supera la contribución requerida. Siempre deja un resto factible:
Las posiciones inferiores pueden representar todos los enteros de \([0,C_i]\), por lo que ambos casos preservan el invariante. Al terminar, \(C_0=0\), y el resto es exactamente cero.
Para una base fija y una longitud de dígitos acotada, el orden numérico coincide con el orden lexicográfico de los dígitos desde el más significativo hasta el menos significativo: aumentar en uno el dígito \(i\) añade \(a^i\), mientras que todas las posiciones inferiores juntas pueden modificar el número en, como máximo, \(a^i-1\). Primero maximizamos \(d_k\) y luego elegimos el mayor valor factible de cada dígito sucesivo. Por tanto, la secuencia obtenida representa el mayor \(n\) válido, es decir, \(F(a,b)\).
El programa reconstruye este número mediante el esquema de Horner, comenzando por \(d_k\) y aplicando \(n\leftarrow an+d_i\) en cada posición inferior.
El primer índice con \(4^k\ge2\cdot3^k\) es \(k=3\). Los pesos, el coste del dígito inicial y la capacidad son
$$(w_0,w_1,w_2)=(1,2,2),\qquad q_3=64-54=10, \qquad C=2(1+2+2)=10.$$
En consecuencia, \(d_3=\min(2,10/10)=1\). Queda por equilibrar una contribución de 10. El algoritmo voraz descendente elige \(d_2=2\), dejando 6; \(d_1=2\), dejando 2; y \(d_0=2\), dejando cero. Por tanto,
$$n=(1222)_3=27+18+6+2=53, \qquad (1222)_4=64+32+8+2=106=2n.$$
Los únicos términos no nulos para \(a=3\) son \(F(3,4)=53\), \(F(3,6)=6\), \(F(3,7)=8\) y \(F(3,8)=5\), cuya suma da \(G(3)=72\).
Lema 1 (ecuación de los dígitos). La coincidencia de representaciones equivale a \(\sum_i d_i(b^i-2a^i)=0\) con \(0\le d_i<a\).
Lema 2 (cota finita). Todo dígito no nulo por encima del primer índice \(k\) con \(b^k\ge2a^k\) aporta más que la capacidad negativa total. Así, todas las secuencias válidas tienen grado a lo sumo \(k\). La igualdad se da precisamente cuando \(b=2a\); y \(b\ge3a\) no admite solución positiva.
Lema 3 (cobertura completa de los pesos inferiores). La identidad \(1+C_i-w_i=(b-a)(b^i-1)/(b-1)\ge0\) y la inducción sobre intervalos demuestran que los dígitos inferiores representan todos los enteros entre cero y su capacidad.
Lema 4 (secuencia máxima). El lema 3 garantiza que el dígito inicial elegido es factible y demuestra que cada dígito voraz posterior deja un resto factible. Cada dígito elegido es el mayor posible tras el prefijo ya fijado; por tanto, el valor resultante en base \(a\) es el máximo valor válido.
Por los lemas 1–4, largest_value(a,b) devuelve exactamente \(F(a,b)\), incluidos cero y el caso especial. Sumar todos los \(a+1\le b<3a\) incluye todos los términos que pueden ser no nulos en \(G(a)\). Por consiguiente, la suma exterior para \(2\le a\le20\) es la respuesta solicitada.
largest_value trata \(b\ge3a\) y \(b=2a\), construye los pesos y la capacidad mediante potencias enteras, calcula el mejor dígito inicial y reconstruye el óptimo con el bucle voraz descendente. sum_for_base evalúa la suma finita para una base; main suma los resultados de las bases 2 a 20.
La implementación en C++ utiliza enteros de 128 bits sin signo. Aunque la respuesta final cabe en 64 bits con signo, las potencias intermedias pueden superar los 64 bits: para \((a,b)=(20,21)\), \(b^{15}=68122318582951682301\). Los enteros de Python y BigInteger de Java proporcionan aritmética exacta para estas mismas operaciones. La implementación no necesita logaritmos de coma flotante.
same_digits compara de forma independiente los restos sucesivos de \(n\) y \(2n\) al dividirlos entre sus respectivas bases. La opción --self-test comprueba los valores publicados, compara exhaustivamente con la enumeración directa para \(2\le a\le7\) y \(a<b\le3a+2\), y verifica la coincidencia de dígitos para cada pareja utilizada en el cálculo final. La cota de grado demostrada proporciona el límite superior de fuerza bruta \(n<a^{k+1}\). Estas comprobaciones verifican la implementación; los argumentos de cobertura completa y de optimalidad voraz establecen la maximalidad en todo el intervalo.
Para una sola pareja \((a,b)\), la construcción y el recorrido voraz utilizan \(O(k)\) operaciones aritméticas con enteros exactos y almacenan \(O(k)\) pesos, donde \(k=\lceil\log2/\log(b/a)\rceil\). La suma finita principal contiene exactamente 399 parejas, y \(k\le15\) en todo el intervalo \(2\le a\le20\). La memoria se reutiliza para cada pareja.
Para una base máxima variable \(A\), la cota directa es \(O(A^2K)\) operaciones aritméticas y \(O(K)\) enteros auxiliares, con \(K=\lceil\log2/\log((A+1)/A)\rceil=O(A)\). Una suma más precisa sobre las diferencias entre bases da \(O(A^2\log A)\) operaciones aritméticas: escribiendo \(b=a+h\), tenemos \(k=O(1+a/h)\), y sumar sobre \(1\le h<2a\) cuesta \(O(a\log a)\) para cada \(a\). Estas cotas cuentan operaciones aritméticas; cuando \(A\) crece, el coste de las operaciones de precisión arbitraria también depende de la longitud de los operandos.
int ordinarios. La división entera // da el redondeo hacia abajo requerido para las cantidades no negativas del paso voraz y conserva las desigualdades de factibilidad sin errores de redondeo.BigInteger ofrece aritmética entera de precisión arbitraria y comparaciones exactas. Sus operaciones de suma, multiplicación, resta y división entera permiten aplicar la misma construcción; como aquí los operandos divididos son no negativos, divide produce el cociente redondeado hacia abajo que requieren las fórmulas.unsigned __int128 como una extensión disponible en plataformas con un modo entero adecuado. Algunas potencias intermedias de esta implementación requieren más de 64 bits: \(21^{15}\) necesita 66 bits, por lo que esas multiplicaciones deben realizarse desde el principio en el tipo más ancho.对于整数进制 \(b>a>1\)，令 \(F(a,b)\) 表示满足以下条件的最大整数 \(n\)：其 \(a\) 进制数字串与 \(2n\) 的 \(b\) 进制数字串完全相同；若不存在正整数解，则取零。定义 \(G(a)=\sum_{b>a}F(a,b)\)。我们需要求出 \(\sum_{a=2}^{20}G(a)\)。
题目给出的校验值为 \(F(3,4)=53\)、\(F(9,10)=8152650\) 和 \(G(3)=72\)。第一个例子是 \(53=(1222)_3\) 且 \(106=(1222)_4\)。
将共同的数字串记为 \(d_m\cdots d_1d_0\)，其中 \(d_m>0\) 且 \(0\le d_i\le a-1\)。由于 \(b>a\)，这些数字在 \(b\) 进制中也必然合法。所要求的性质恰好等价于
$$n=\sum_{i=0}^{m}d_i a^i,\qquad 2n=\sum_{i=0}^{m}d_i b^i,$$
将两式相减，可得
$$\sum_{i=0}^{m}d_i(b^i-2a^i)=0.$$
在较低的数位上，非零数字对最后这个和产生负贡献；在足够高的数位上，它产生正贡献。解必须使这两类贡献恰好抵消。
令
$$k=\min\{i\ge 0:b^i\ge2a^i\} =\left\lceil\frac{\log2}{\log(b/a)}\right\rceil.$$
因为 \(b/a>1\)，这个下标一定存在；又因为 \(b^0=a^0=1\)，它满足 \(k\ge1\)。程序通过逐次相乘计算精确的整数幂来确定该下标，避免临界位置的浮点误差。
对于 \(0\le i<k\)，定义正权重
$$w_i=2a^i-b^i>0, \qquad C=(a-1)\sum_{i=0}^{k-1}w_i.$$
\(C\) 是所有较低数位所能提供的负贡献绝对值的最大值。由于每个权重都满足 \(w_i<2a^i\)，因此
$$C<2(a-1)\sum_{i=0}^{k-1}a^i=2(a^k-1)<2a^k.$$
现在令 \(q_i=b^i-2a^i\)。对于紧接在 \(k\) 之上的第一个数位，有
$$q_{k+1}=bq_k+2(b-a)a^k\ge2a^k>C.$$
递推式 \(q_{i+1}=bq_i+2(b-a)a^i\) 还表明，在 \(i\ge k\) 时，这些正贡献随下标增大而增加。因此，即使在第 \(k\) 位以上只放置一个非零数字，其贡献也会超过全部可用的负贡献。其他非负项只会进一步加大失衡。由此可知，每个解的最高次幂至多为 \(k\)。
当 \(q_k>0\) 时，每个正整数解在第 \(k\) 位上都必须有一个非零数字：若一个非空数字串仅使用低于 \(k\) 的数位，平衡式的值就会严格小于零。因此，原本针对无界整数的搜索可化为
$$d_kq_k=\sum_{i=0}^{k-1}d_iw_i, \qquad 0\le d_i\le a-1.$$
若 \(b=2a\)，则 \(k=1\) 且 \(q_1=0\)。平衡方程迫使 \(d_0=0\)，而上述截断结论已经排除了第 1 位以上的所有数位。允许的最大首位数字为 \(a-1\)，因此
$$\boxed{F(a,2a)=a(a-1)}.$$
这是 \(q_k=0\) 成立的唯一情形。事实上，若 \((b/a)^k=2\)，将 \(b/a=u/v\) 约成最简分数。由 \(u^k=2v^k\) 及互素性可知，必须有 \(v=1\)；随后 \(u^k=2\) 又迫使 \(u=2\) 且 \(k=1\)。单独处理这一情形也能避免除以零。
若 \(b\ge3a\)，则 \(k=1\)、\(w_0=1\) 且 \(q_1=b-2a\ge a\)。低位的容量仅为 \(C=a-1\)，因此连 \(d_1=1\) 都无法得到平衡。所以
$$\boxed{F(a,b)=0\quad\text{for }b\ge3a}.$$
这证明了无穷和实际上只有有限个非零项，并给出了精确的求和范围
$$G(a)=\sum_{b=a+1}^{3a-1}F(a,b).$$
这个区间内的某些进制同样没有正整数解；算法会自动对它们返回零。
通常，仅有容量上界并不能保证精确表示：对于任意一种每种面额数量受限的硬币系统，可表示的金额可能存在空缺。不过，这里的权重具有更强的性质。
令 \(C_i=(a-1)\sum_{j=0}^{i-1}w_j\)，于是 \(C_0=0\) 且 \(C_k=C\)。利用等比数列求和可得
$$\begin{aligned} 1+C_i-w_i &=1+(a-1)\sum_{j=0}^{i-1}(2a^j-b^j)-(2a^i-b^i)\\ &=\frac{(b-a)(b^i-1)}{b-1}\ge0. \end{aligned}$$
因此 \(w_0=1\)，且后续每一个正权重都满足
$$\boxed{w_i\le C_i+1}.$$
作归纳假设：低于第 \(i\) 位的数位可以表示 \([0,C_i]\) 内的每一个整数。固定 \(d_i=t\) 后，加入第 \(i\) 位即可得到整数区间 \([tw_i,tw_i+C_i]\)，其中 \(t=0,\ldots,a-1\)。由于 \(w_i\le C_i+1\)，相邻区间彼此重叠或首尾相接。因此，它们的并集包含从 0 到 \(C_i+(a-1)w_i=C_{i+1}\) 的每一个整数。从零的空表示出发进行归纳，即可证明低于第 \(k\) 位的数位能够表示 \([0,C]\) 内的每一个整数。
权重不必递增。证明使用的是权重对应的数位顺序，以及先前较低数位的容量，因此无需任何关于权重已排序的假设。
假设 \(b\ne2a\)，于是 \(q_k>0\)。可行性要求 \(d_kq_k\le C\) 且 \(d_k\le a-1\)。低位权重的完备性证明了这些必要条件也充分。因此，最大的可行首位数字为
$$\boxed{d_k=\min\left(a-1,\left\lfloor\frac{C}{q_k}\right\rfloor\right)}.$$
若这个值为零，则不存在正整数解。否则，将尚需补足的平衡量初始化为 \(R=d_kq_k\)。
依次处理 \(i=k-1,k-2,\ldots,0\)，选择
$$\boxed{d_i=\min\left(a-1,\left\lfloor\frac{R}{w_i}\right\rfloor\right), \qquad R\leftarrow R-d_iw_i.}$$
这是第 \(i\) 位上不超过所需平衡量的最大数字。它总能留下一个可表示的余量：
较低数位能够表示 \([0,C_i]\) 内的每个整数，所以两种情况都会保持不变式。最后，\(C_0=0\)，余量恰好为零。
在进制固定且位数有界时，数值大小顺序就是从最高位到最低位的数字字典序：将第 \(i\) 位的数字增加一，会使数值增加 \(a^i\)，而全部更低数位合计至多只能改变 \(a^i-1\)。我们先最大化 \(d_k\)，再为随后每一位选择最大的可行数字。因此，最终得到的数字串表示最大的合法 \(n\)，即 \(F(a,b)\)。
程序使用霍纳法则重建这个数：从 \(d_k\) 开始，每处理一个较低数位就执行 \(n\leftarrow an+d_i\)。
第一个满足 \(4^k\ge2\cdot3^k\) 的下标是 \(k=3\)。权重、首位的正贡献系数及容量分别为
$$(w_0,w_1,w_2)=(1,2,2),\qquad q_3=64-54=10, \qquad C=2(1+2+2)=10.$$
因此 \(d_3=\min(2,10/10)=1\)。剩余平衡量为 10。从高位到低位的贪心过程选择 \(d_2=2\)，余量变为 6；再选择 \(d_1=2\)，余量变为 2；最后选择 \(d_0=2\)，余量变为零。因此
$$n=(1222)_3=27+18+6+2=53, \qquad (1222)_4=64+32+8+2=106=2n.$$
对于 \(a=3\)，仅有的非零项为 \(F(3,4)=53\)、\(F(3,6)=6\)、\(F(3,7)=8\) 和 \(F(3,8)=5\)，从而得到 \(G(3)=72\)。
引理 1（数位方程）。 两种进制表示的数字串相同，等价于 \(\sum_i d_i(b^i-2a^i)=0\)，其中 \(0\le d_i<a\)。
引理 2（有限截断）。 设 \(k\) 是第一个满足 \(b^k\ge2a^k\) 的下标，则高于该位置的任何非零数字所产生的贡献，都超过所有负贡献的总容量。因此，所有合法数字串的最高次幂至多为 \(k\)。等号成立的情形恰好是 \(b=2a\)；而 \(b\ge3a\) 时不存在正整数解。
引理 3（低位权重的完备性）。 恒等式 \(1+C_i-w_i=(b-a)(b^i-1)/(b-1)\ge0\) 与区间归纳证明表明，较低数位能够表示从零到其容量之间的每一个整数。
引理 4（最大的数字串）。 引理 3 保证所选首位数字可行，并证明随后每一步贪心选择都会留下可行余量。在已经固定的前缀之后，每个所选数字都是可能的最大值；因此，得到的 \(a\) 进制数值就是最大的合法数值。
根据引理 1–4，largest_value(a,b) 返回的恰好是 \(F(a,b)\)，包括结果为零以及特殊进制的情形。对所有 \(a+1\le b<3a\) 求和，即包含了 \(G(a)\) 中一切可能的非零项。因此，再对 \(2\le a\le20\) 进行外层求和就得到题目要求的答案。
largest_value 首先处理 \(b\ge3a\) 和 \(b=2a\)，然后用整数幂构造权重及容量，计算最优首位数字，再通过从高位到低位的贪心循环重建最优值。sum_for_base 计算单个进制对应的有限和；main 将进制 2 到 20 的结果相加。
C++ 实现使用无符号 128 位整数。虽然最终答案可以用有符号 64 位整数表示，但中间幂值可能超过 64 位：例如，当 \((a,b)=(20,21)\) 时，\(b^{15}=68122318582951682301\)。Python 整数和 Java 的 BigInteger 为这些相同的运算提供精确算术支持。实现中不需要计算浮点对数。
same_digits 通过逐次比较 \(n\) 与 \(2n\) 在各自进制下的除法余数，独立检查数字串是否相同。可选的 --self-test 会核对题目给出的数值，在 \(2\le a\le7\) 且 \(a<b\le3a+2\) 的范围内与直接枚举结果进行穷尽比较，并检查最终计算所涉及的每一对进制是否满足数字串相同的性质。已经证明的次数上界给出了暴力枚举的上限 \(n<a^{k+1}\)。这些检查用于验证实现；完备性证明和贪心论证则确立了完整范围内的最大性。
对于单个进制对 \((a,b)\)，构造过程与贪心遍历需要 \(O(k)\) 次精确整数算术运算，并存储 \(O(k)\) 个权重，其中 \(k=\lceil\log2/\log(b/a)\rceil\)。主有限和中恰好有 399 对进制，且在整个 \(2\le a\le20\) 范围内都有 \(k\le15\)。每处理一对进制都会复用内存。
若将最大进制视为变量 \(A\)，直接得到的上界为 \(O(A^2K)\) 次算术运算及 \(O(K)\) 个辅助整数，其中 \(K=\lceil\log2/\log((A+1)/A)\rceil=O(A)\)。对进制差求和可得到更紧的上界 \(O(A^2\log A)\) 次算术运算：写成 \(b=a+h\) 时，有 \(k=O(1+a/h)\)，对 \(1\le h<2a\) 求和后，每个 \(a\) 的代价为 \(O(a\log a)\)。这些复杂度统计的是算术运算次数；当 \(A\) 增大时，任意精度运算的实际代价还取决于操作数的长度。
int 精确计算。整数除法 // 对贪心步骤中的非负数给出所需的向下取整结果，使可行性不等式不受舍入误差影响。BigInteger 提供任意精度整数运算和精确比较。其加法、乘法、减法与整数除法可直接实现同一构造；由于这里参与除法的数均非负，divide 给出的结果正是公式所需的向下取整商。unsigned __int128 记载为适用于支持相应整数模式的目标平台的扩展类型。此实现的某些中间幂需要超过 64 位：\(21^{15}\) 需要 66 位，因此相关乘法本身就必须在较宽的类型中进行。Для целых оснований \(b>a>1\) обозначим через \(F(a,b)\) наибольшее целое число \(n\), цифры которого в системе счисления с основанием \(a\) совпадают с цифрами числа \(2n\) в системе с основанием \(b\); если положительного решения нет, значение равно нулю. Определим \(G(a)=\sum_{b>a}F(a,b)\). Требуется найти \(\sum_{a=2}^{20}G(a)\).
В условии приведены контрольные значения \(F(3,4)=53\), \(F(9,10)=8152650\) и \(G(3)=72\). Первый пример: \(53=(1222)_3\) и \(106=(1222)_4\).
Запишем общую последовательность цифр как \(d_m\cdots d_1d_0\), где \(d_m>0\) и \(0\le d_i\le a-1\). Эти цифры автоматически допустимы и в системе с основанием \(b\), поскольку \(b>a\). Требуемое свойство в точности означает
$$n=\sum_{i=0}^{m}d_i a^i,\qquad 2n=\sum_{i=0}^{m}d_i b^i,$$
или, после вычитания,
$$\sum_{i=0}^{m}d_i(b^i-2a^i)=0.$$
При малых индексах ненулевая цифра вносит отрицательный вклад в последнюю сумму; при достаточно больших индексах её вклад положителен. В решении эти два вклада уравновешиваются.
Пусть
$$k=\min\{i\ge 0:b^i\ge2a^i\} =\left\lceil\frac{\log2}{\log(b/a)}\right\rceil.$$
Поскольку \(b/a>1\), такой индекс существует; поскольку \(b^0=a^0=1\), выполняется \(k\ge1\). В реализации он находится последовательным умножением точных целых степеней, что исключает ошибки вычислений с плавающей точкой на границе.
Для \(0\le i<k\) определим положительные веса
$$w_i=2a^i-b^i>0, \qquad C=(a-1)\sum_{i=0}^{k-1}w_i.$$
Величина \(C\) — наибольший по модулю отрицательный вклад, который могут дать все младшие разряды вместе. Поскольку каждый \(w_i<2a^i\),
$$C<2(a-1)\sum_{i=0}^{k-1}a^i=2(a^k-1)<2a^k.$$
Теперь положим \(q_i=b^i-2a^i\). В первом разряде выше \(k\) имеем
$$q_{k+1}=bq_k+2(b-a)a^k\ge2a^k>C.$$
Рекуррентное соотношение \(q_{i+1}=bq_i+2(b-a)a^i\) также показывает, что эти положительные вклады возрастают при \(i\ge k\). Поэтому даже одна ненулевая цифра выше разряда \(k\) перевесила бы весь доступный отрицательный вклад. Остальные неотрицательные слагаемые могли бы лишь увеличить дисбаланс. Следовательно, степень любого решения не превосходит \(k\).
Если \(q_k>0\), каждое положительное решение обязано иметь ненулевую цифру в разряде \(k\): ненулевая запись, ограниченная разрядами ниже \(k\), дала бы строго отрицательный баланс. Таким образом, исходный поиск среди неограниченных целых чисел сводится к уравнению
$$d_kq_k=\sum_{i=0}^{k-1}d_iw_i, \qquad 0\le d_i\le a-1.$$
Если \(b=2a\), то \(k=1\) и \(q_1=0\). Уравнение баланса требует \(d_0=0\), а полученная граница уже запрещает все разряды выше 1. Наибольшая допустимая старшая цифра равна \(a-1\), откуда
$$\boxed{F(a,2a)=a(a-1)}.$$
Это единственный случай, когда \(q_k=0\). Действительно, если \((b/a)^k=2\), сократим дробь \(b/a=u/v\). Из \(u^k=2v^k\) и взаимной простоты следует \(v=1\); тогда \(u^k=2\) требует \(u=2\) и \(k=1\). Отдельная обработка этого случая также предотвращает деление на ноль.
Если \(b\ge3a\), то \(k=1\), \(w_0=1\) и \(q_1=b-2a\ge a\). Возможности младших разрядов ограничены величиной \(C=a-1\), поэтому уравновесить даже \(d_1=1\) невозможно. Следовательно,
$$\boxed{F(a,b)=0\quad\text{for }b\ge3a}.$$
Это доказывает, что бесконечная сумма фактически конечна, и даёт точные пределы
$$G(a)=\sum_{b=a+1}^{3a-1}F(a,b).$$
Для некоторых оснований внутри этого интервала положительных решений также нет; алгоритм автоматически возвращает для них ноль.
Само по себе ограничение на максимальную сумму обычно не гарантирует точного представления: произвольные системы монет с ограниченным количеством могут иметь пропуски. У данных весов есть более сильное свойство.
Пусть \(C_i=(a-1)\sum_{j=0}^{i-1}w_j\), так что \(C_0=0\) и \(C_k=C\). Вычисление геометрических сумм даёт
$$\begin{aligned} 1+C_i-w_i &=1+(a-1)\sum_{j=0}^{i-1}(2a^j-b^j)-(2a^i-b^i)\\ &=\frac{(b-a)(b^i-1)}{b-1}\ge0. \end{aligned}$$
Таким образом, \(w_0=1\), а каждый следующий положительный вес удовлетворяет условию
$$\boxed{w_i\le C_i+1}.$$
Предположим по индукции, что разряды ниже \(i\) представляют все целые числа из \([0,C_i]\). При фиксированном выборе \(d_i=t\) добавление разряда \(i\) даёт целочисленный интервал \([tw_i,tw_i+C_i]\), где \(t=0,\ldots,a-1\). Соседние интервалы пересекаются или примыкают друг к другу, поскольку \(w_i\le C_i+1\). Поэтому их объединение содержит все целые числа от 0 до \(C_i+(a-1)w_i=C_{i+1}\). Начиная с пустого представления нуля, получаем, что разряды ниже \(k\) представляют каждое целое число из \([0,C]\).
Веса не обязаны возрастать. Доказательство использует порядок разрядов и максимальную сумму предыдущих разрядов, поэтому предположение об упорядоченности весов по величине не требуется.
Предположим, что \(b\ne2a\), поэтому \(q_k>0\). Для допустимости необходимы \(d_kq_k\le C\) и \(d_k\le a-1\). Полнота представлений младшими весами доказывает, что эти необходимые условия также достаточны. Следовательно, наибольшая допустимая старшая цифра равна
$$\boxed{d_k=\min\left(a-1,\left\lfloor\frac{C}{q_k}\right\rfloor\right)}.$$
Если это значение равно нулю, положительного решения нет. Иначе задаём оставшийся вклад, который нужно набрать, как \(R=d_kq_k\).
Обрабатываем \(i=k-1,k-2,\ldots,0\), выбирая
$$\boxed{d_i=\min\left(a-1,\left\lfloor\frac{R}{w_i}\right\rfloor\right), \qquad R\leftarrow R-d_iw_i.}$$
Это наибольшая цифра в разряде \(i\), которая не превышает требуемый вклад. После её выбора всегда остаётся представимый остаток:
Младшие разряды представляют каждое целое число из \([0,C_i]\), поэтому в обоих случаях инвариант сохраняется. В конце \(C_0=0\), и остаток в точности равен нулю.
При фиксированном основании и ограниченной длине записи числовой порядок совпадает с лексикографическим порядком цифр от старших к младшим: увеличение цифры \(i\) на единицу добавляет \(a^i\), тогда как все младшие разряды вместе могут изменить число не более чем на \(a^i-1\). Сначала мы максимизируем \(d_k\), затем выбираем наибольшее допустимое значение каждой следующей цифры. Поэтому полученная запись представляет наибольшее допустимое \(n\), то есть \(F(a,b)\).
Программа восстанавливает это число по схеме Горнера: начинает с \(d_k\) и применяет \(n\leftarrow an+d_i\) для каждого младшего разряда.
Первый индекс, для которого \(4^k\ge2\cdot3^k\), равен \(k=3\). Веса, стоимость старшей цифры и максимальная сумма младших вкладов равны
$$(w_0,w_1,w_2)=(1,2,2),\qquad q_3=64-54=10, \qquad C=2(1+2+2)=10.$$
Следовательно, \(d_3=\min(2,10/10)=1\). Остаётся набрать вклад 10. Жадный проход от старших разрядов к младшим выбирает \(d_2=2\), оставляя 6; \(d_1=2\), оставляя 2; и \(d_0=2\), оставляя ноль. Поэтому
$$n=(1222)_3=27+18+6+2=53, \qquad (1222)_4=64+32+8+2=106=2n.$$
Единственные ненулевые слагаемые при \(a=3\) — это \(F(3,4)=53\), \(F(3,6)=6\), \(F(3,7)=8\) и \(F(3,8)=5\), что даёт \(G(3)=72\).
Лемма 1 (уравнение цифр). Совпадение записей равносильно \(\sum_i d_i(b^i-2a^i)=0\) при \(0\le d_i<a\).
Лемма 2 (конечная граница). Любая ненулевая цифра выше первого индекса \(k\), для которого \(b^k\ge2a^k\), даёт вклад, превышающий всю доступную отрицательную сумму. Поэтому степень каждой допустимой записи не превосходит \(k\). Равенство возникает в точности при \(b=2a\); при \(b\ge3a\) положительных решений нет.
Лемма 3 (полнота младших весов). Тождество \(1+C_i-w_i=(b-a)(b^i-1)/(b-1)\ge0\) и индукция по интервалам показывают, что младшие цифры представляют все целые числа от нуля до своей максимальной суммы.
Лемма 4 (максимальная запись). Лемма 3 обеспечивает допустимость выбранной старшей цифры и доказывает, что каждый последующий жадный выбор оставляет представимый остаток. Каждая выбранная цифра является наибольшей возможной при уже фиксированном префиксе; следовательно, полученное значение в системе с основанием \(a\) максимально среди допустимых.
По леммам 1–4 функция largest_value(a,b) возвращает в точности \(F(a,b)\), включая нулевой результат и особый случай. Суммирование по всем \(a+1\le b<3a\) включает все потенциально ненулевые слагаемые \(G(a)\). Поэтому внешняя сумма по \(2\le a\le20\) даёт требуемый ответ.
Функция largest_value обрабатывает случаи \(b\ge3a\) и \(b=2a\), строит веса и их максимальную сумму с помощью целых степеней, вычисляет оптимальную старшую цифру и восстанавливает максимум жадным проходом от старших разрядов к младшим. Функция sum_for_base вычисляет конечную сумму для одного основания; main складывает результаты для оснований от 2 до 20.
Реализация на C++ использует беззнаковые 128-битные целые числа. Хотя окончательный ответ помещается в знаковый 64-битный тип, промежуточные степени могут превышать 64 бита: для \((a,b)=(20,21)\) имеем \(b^{15}=68122318582951682301\). Целые числа Python и BigInteger в Java обеспечивают точную арифметику для тех же операций. Логарифмы с плавающей точкой в реализации не нужны.
Функция same_digits независимо сравнивает последовательные остатки от деления \(n\) и \(2n\) на соответствующие основания. Необязательный режим --self-test проверяет опубликованные значения, выполняет исчерпывающее сравнение с прямым перебором для \(2\le a\le7\) и \(a<b\le3a+2\), а также проверяет совпадение цифр для каждой пары, используемой в итоговом вычислении. Доказанная граница степени задаёт верхний предел перебора \(n<a^{k+1}\). Эти проверки тестируют реализацию; доказательства полноты представлений и оптимальности жадного выбора устанавливают максимальность для всего диапазона.
Для одной пары \((a,b)\) построение и жадный проход требуют \(O(k)\) точных целочисленных арифметических операций и хранения \(O(k)\) весов, где \(k=\lceil\log2/\log(b/a)\rceil\). Основная конечная сумма содержит ровно 399 пар, причём \(k\le15\) во всём диапазоне \(2\le a\le20\). Память повторно используется для каждой пары.
Для переменного максимального основания \(A\) непосредственная оценка составляет \(O(A^2K)\) арифметических операций и \(O(K)\) вспомогательных целых чисел, где \(K=\lceil\log2/\log((A+1)/A)\rceil=O(A)\). Более точное суммирование по разностям оснований даёт \(O(A^2\log A)\) арифметических операций: записав \(b=a+h\), получаем \(k=O(1+a/h)\), а суммирование по \(1\le h<2a\) требует \(O(a\log a)\) для каждого \(a\). Это оценки количества арифметических операций; при росте \(A\) стоимость операций с произвольной точностью также зависит от длины операндов.
int. Целочисленное деление // даёт нужное округление вниз для неотрицательных величин жадного шага и сохраняет неравенства допустимости без ошибок округления.BigInteger обеспечивает целочисленную арифметику произвольной точности и точные сравнения. Сложение, умножение, вычитание и целочисленное деление реализуют ту же конструкцию; поскольку операнды деления здесь неотрицательны, divide даёт округлённое вниз частное, требуемое формулами.unsigned __int128 как расширение для целевых платформ с подходящим целочисленным режимом. Некоторые промежуточные степени в этой реализации требуют больше 64 бит: для \(21^{15}\) нужно 66 бит, поэтому сами соответствующие умножения должны выполняться в более широком типе.لأساسين صحيحين \(b>a>1\)، نعرّف \(F(a,b)\) بأنه أكبر عدد صحيح \(n\) تكون أرقامه في الأساس \(a\) مطابقة لأرقام \(2n\) في الأساس \(b\)، أو صفرًا إذا لم يوجد حل موجب. ونعرّف \(G(a)=\sum_{b>a}F(a,b)\). المطلوب هو حساب \(\sum_{a=2}^{20}G(a)\).
القيم المعطاة للتحقق هي \(F(3,4)=53\) و\(F(9,10)=8152650\) و\(G(3)=72\). وفي المثال الأول لدينا \(53=(1222)_3\) و\(106=(1222)_4\).
نكتب سلسلة الأرقام المشتركة على الصورة \(d_m\cdots d_1d_0\)، حيث \(d_m>0\) و\(0\le d_i\le a-1\). وهذه الأرقام صالحة تلقائيًا في الأساس \(b\) لأن \(b>a\). الخاصية المطلوبة تكافئ تمامًا
$$n=\sum_{i=0}^{m}d_i a^i,\qquad 2n=\sum_{i=0}^{m}d_i b^i,$$
أو، بعد الطرح،
$$\sum_{i=0}^{m}d_i(b^i-2a^i)=0.$$
عند الفهارس الصغيرة، يضيف الرقم غير الصفري مساهمة سالبة إلى هذا المجموع الأخير؛ وعند الفهارس الكبيرة بما يكفي، تكون مساهمته موجبة. ويحقق الحل التوازن بين المساهمتين.
لتكن
$$k=\min\{i\ge 0:b^i\ge2a^i\} =\left\lceil\frac{\log2}{\log(b/a)}\right\rceil.$$
بما أن \(b/a>1\)، فإن هذا الفهرس موجود؛ وبما أن \(b^0=a^0=1\)، فإنه يحقق \(k\ge1\). يجد التنفيذ هذا الفهرس بضرب قوى صحيحة دقيقة تباعًا، متجنبًا أخطاء الفاصلة العائمة عند الحد الفاصل.
لكل \(0\le i<k\)، نعرّف الأوزان الموجبة
$$w_i=2a^i-b^i>0, \qquad C=(a-1)\sum_{i=0}^{k-1}w_i.$$
تمثل الكمية \(C\) أكبر مقدار للمساهمة السالبة التي تستطيع جميع المواضع الأدنى توفيرها. وبما أن كل وزن يحقق \(w_i<2a^i\)، فإن
$$C<2(a-1)\sum_{i=0}^{k-1}a^i=2(a^k-1)<2a^k.$$
لنضع الآن \(q_i=b^i-2a^i\). عند أول موضع أعلى من \(k\)، لدينا
$$q_{k+1}=bq_k+2(b-a)a^k\ge2a^k>C.$$
تبيّن علاقة التكرار \(q_{i+1}=bq_i+2(b-a)a^i\) أيضًا أن هذه المساهمات الموجبة تتزايد عندما \(i\ge k\). لذلك فإن رقمًا غير صفري واحدًا فوق الموضع \(k\) سيجعل مساهمته تفوق جميع المساهمات السالبة المتاحة. وأي حدود أخرى غير سالبة لن تزيد إلا مقدار الاختلال. ومن ثم فإن درجة كل حل لا تتجاوز \(k\).
عندما \(q_k>0\)، يجب أن يحتوي كل حل موجب على رقم غير صفري في الموضع \(k\): إذ إن سلسلة غير خالية تقتصر على المواضع الأدنى من \(k\) ستجعل قيمة معادلة الاتزان سالبة تمامًا. وهكذا يختزل البحث الأصلي في أعداد صحيحة غير محدودة إلى
$$d_kq_k=\sum_{i=0}^{k-1}d_iw_i, \qquad 0\le d_i\le a-1.$$
إذا كان \(b=2a\)، فإن \(k=1\) و\(q_1=0\). تفرض معادلة الاتزان \(d_0=0\)، بينما يستبعد حد القطع السابق بالفعل جميع المواضع الأعلى من 1. وأكبر رقم مسموح به في الموضع الأعلى هو \(a-1\)، مما يعطي
$$\boxed{F(a,2a)=a(a-1)}.$$
هذه هي الحالة الوحيدة التي يتحقق فيها \(q_k=0\). بالفعل، إذا كان \((b/a)^k=2\)، نختزل \(b/a=u/v\) إلى أبسط صورة. ومن \(u^k=2v^k\)، يفرض كون البسط والمقام أوليين فيما بينهما أن \(v=1\)؛ ثم تفرض \(u^k=2\) أن \(u=2\) و\(k=1\). كما أن معالجة هذه الحالة على حدة تمنع القسمة على صفر.
إذا كان \(b\ge3a\)، فإن \(k=1\) و\(w_0=1\) و\(q_1=b-2a\ge a\). وسعة المواضع الأدنى لا تزيد على \(C=a-1\)، ولذلك لا يمكن تحقيق الاتزان حتى عند \(d_1=1\). ومن ثم
$$\boxed{F(a,b)=0\quad\text{for }b\ge3a}.$$
يثبت هذا أن المجموع اللانهائي لا يحتوي إلا على عدد منتهٍ من الحدود غير الصفرية، ويتيح نطاق الجمع الدقيق
$$G(a)=\sum_{b=a+1}^{3a-1}F(a,b).$$
بعض الأسس داخل هذا النطاق لا تقبل حلًا موجبًا أيضًا؛ وتعيد الخوارزمية صفرًا لها تلقائيًا.
وجود حد للسعة وحده لا يضمن عادةً إمكان التمثيل الدقيق: فقد تظهر فجوات في أنظمة العملات العامة التي يتاح فيها عدد محدود من كل فئة. لكن هذه الأوزان بعينها تمتلك خاصية أقوى.
لتكن \(C_i=(a-1)\sum_{j=0}^{i-1}w_j\)، بحيث \(C_0=0\) و\(C_k=C\). وبحساب مجموع متسلسلة هندسية نحصل على
$$\begin{aligned} 1+C_i-w_i &=1+(a-1)\sum_{j=0}^{i-1}(2a^j-b^j)-(2a^i-b^i)\\ &=\frac{(b-a)(b^i-1)}{b-1}\ge0. \end{aligned}$$
إذن \(w_0=1\)، وكل وزن موجب تالٍ يحقق
$$\boxed{w_i\le C_i+1}.$$
نفترض استقرائيًا أن المواضع الأدنى من \(i\) تستطيع تمثيل كل عدد صحيح في \([0,C_i]\). عند تثبيت الاختيار \(d_i=t\)، تتيح إضافة الموضع \(i\) فترة الأعداد الصحيحة \([tw_i,tw_i+C_i]\)، حيث \(t=0,\ldots,a-1\). تتداخل الفترات المتتالية أو تتجاور لأن \(w_i\le C_i+1\). لذلك يحتوي اتحادها على كل عدد صحيح من 0 إلى \(C_i+(a-1)w_i=C_{i+1}\). وبالبدء من التمثيل الخالي للصفر، يثبت الاستقراء أن المواضع الأدنى من \(k\) تمثل كل عدد صحيح في \([0,C]\).
لا يلزم أن تكون الأوزان متزايدة. يستخدم البرهان ترتيبها حسب مواضع الأرقام وسعة المواضع السابقة، ولذلك لا يحتاج إلى افتراض أنها مرتبة حسب قيمها.
نفترض \(b\ne2a\)، وبالتالي \(q_k>0\). تتطلب قابلية التمثيل أن \(d_kq_k\le C\) و\(d_k\le a-1\). ويثبت اكتمال أوزان المواضع الأدنى أن هذين الشرطين الضروريين كافيان أيضًا. لذلك فإن أكبر رقم أعلى يمكن اختياره هو
$$\boxed{d_k=\min\left(a-1,\left\lfloor\frac{C}{q_k}\right\rfloor\right)}.$$
إذا كانت هذه القيمة صفرًا، فلا يوجد حل موجب. وإلا فنهيّئ مقدار الاتزان الذي ما زال مطلوبًا توفيره على الصورة \(R=d_kq_k\).
نعالج المواضع \(i=k-1,k-2,\ldots,0\) بالترتيب، ونختار
$$\boxed{d_i=\min\left(a-1,\left\lfloor\frac{R}{w_i}\right\rfloor\right), \qquad R\leftarrow R-d_iw_i.}$$
هذا هو أكبر رقم في الموضع \(i\) لا يتجاوز مقدار الاتزان المطلوب. ويترك دائمًا باقيًا قابلًا للتمثيل:
تستطيع المواضع الأدنى تمثيل كل عدد صحيح في \([0,C_i]\)، ولذلك تحافظ كلتا الحالتين على الخاصية الثابتة. وعند النهاية تكون \(C_0=0\)، ويصبح الباقي صفرًا تمامًا.
عند تثبيت الأساس ووضع حد لطول سلسلة الأرقام، يكون الترتيب العددي هو الترتيب المعجمي للأرقام من الأعلى قيمة موضعية إلى الأدنى: فزيادة الرقم في الموضع \(i\) بمقدار واحد تضيف \(a^i\)، في حين لا تستطيع جميع المواضع الأدنى مجتمعة تغيير العدد بأكثر من \(a^i-1\). نعظّم أولًا \(d_k\)، ثم نختار أكبر قيمة ممكنة لكل رقم تالٍ مع الحفاظ على قابلية التمثيل. لذلك تمثل السلسلة المكتملة أكبر \(n\) صالح، أي \(F(a,b)\).
يعيد البرنامج بناء هذا العدد باستخدام قاعدة هورنر، بدءًا من \(d_k\)، مع تطبيق \(n\leftarrow an+d_i\) عند كل موضع أدنى.
أول فهرس يحقق \(4^k\ge2\cdot3^k\) هو \(k=3\). وتكون الأوزان وكلفة الرقم الأعلى والسعة كما يلي
$$(w_0,w_1,w_2)=(1,2,2),\qquad q_3=64-54=10, \qquad C=2(1+2+2)=10.$$
بالتالي \(d_3=\min(2,10/10)=1\). ومقدار الاتزان المتبقي هو 10. تختار الخوارزمية الجشعة التنازلية \(d_2=2\)، فيتبقى 6؛ ثم \(d_1=2\)، فيتبقى 2؛ ثم \(d_0=2\)، فيصبح الباقي صفرًا. لذلك
$$n=(1222)_3=27+18+6+2=53, \qquad (1222)_4=64+32+8+2=106=2n.$$
الحدود غير الصفرية الوحيدة عند \(a=3\) هي \(F(3,4)=53\) و\(F(3,6)=6\) و\(F(3,7)=8\) و\(F(3,8)=5\)، مما يعطي \(G(3)=72\).
اللمّة 1 (معادلة الأرقام). تطابق التمثيلين يكافئ \(\sum_i d_i(b^i-2a^i)=0\) مع \(0\le d_i<a\).
اللمّة 2 (حد القطع المنتهي). كل رقم غير صفري أعلى من أول فهرس \(k\) يحقق \(b^k\ge2a^k\) يضيف مساهمة تفوق السعة السالبة الكلية. ومن ثم فإن درجة جميع السلاسل الصالحة لا تتجاوز \(k\). وتتحقق حالة المساواة تحديدًا عندما \(b=2a\)؛ أما \(b\ge3a\) فلا يقبل حلًا موجبًا.
اللمّة 3 (اكتمال أوزان المواضع الأدنى). تبيّن الهوية \(1+C_i-w_i=(b-a)(b^i-1)/(b-1)\ge0\) والاستقراء على الفترات أن الأرقام الأدنى تستطيع تمثيل كل عدد صحيح بين الصفر وسعتها.
اللمّة 4 (السلسلة القصوى). تضمن اللمّة 3 إمكان اختيار الرقم الأعلى المحدد، وتثبت أن كل رقم تختاره الخطوة الجشعة التالية يترك باقيًا قابلًا للتمثيل. وكل رقم مختار هو الأكبر الممكن بعد تثبيت البادئة السابقة؛ لذلك تكون القيمة الناتجة في الأساس \(a\) هي أكبر قيمة صالحة.
بفضل اللمّات 1–4، تعيد largest_value(a,b) القيمة \(F(a,b)\) بالضبط، بما في ذلك الصفر والحالة الخاصة. والجمع على جميع \(a+1\le b<3a\) يشمل كل حد يمكن أن يكون غير صفري في \(G(a)\). ومن ثم فإن المجموع الخارجي على \(2\le a\le20\) هو الإجابة المطلوبة.
تعالج largest_value الحالتين \(b\ge3a\) و\(b=2a\)، وتبني الأوزان والسعة باستخدام القوى الصحيحة، وتحسب أفضل رقم أعلى، ثم تعيد بناء القيمة المثلى بحلقة جشعة تنازلية. وتحسب sum_for_base المجموع المنتهي لأساس واحد؛ بينما تجمع main النتائج للأسس من 2 إلى 20.
يستخدم تنفيذ C++ أعدادًا صحيحة غير موقعة من 128 بت. وعلى الرغم من أن الإجابة النهائية تسعها 64 بت موقعة، فإن القوى الوسيطة قد تتجاوز 64 بت: فعند \((a,b)=(20,21)\)، لدينا \(b^{15}=68122318582951682301\). وتوفر أعداد Python الصحيحة والنوع BigInteger في Java حسابًا دقيقًا للعمليات نفسها. ولا يحتاج التنفيذ إلى لوغاريتمات بالفاصلة العائمة.
تتحقق same_digits بصورة مستقلة من خلال مقارنة بواقي القسمة المتتابعة للعددين \(n\) و\(2n\) في أساسيهما. ويفحص الخيار --self-test القيم المنشورة، ويجري مقارنة شاملة مع التعداد المباشر عندما \(2\le a\le7\) و\(a<b\le3a+2\)، ويتحقق من خاصية تطابق الأرقام لكل زوج يُستخدم في الحساب النهائي. ويوفر الحد المثبت للدرجة حد التعداد بالقوة الغاشمة \(n<a^{k+1}\). تختبر هذه الفحوص التنفيذ؛ أما برهانا الاكتمال والاختيار الجشع فيثبتان أن القيمة هي القصوى على النطاق الكامل.
لزوج واحد \((a,b)\)، تستخدم مرحلة البناء والمرور الجشع \(O(k)\) عملية حسابية دقيقة على الأعداد الصحيحة و\(O(k)\) وزنًا مخزنًا، حيث \(k=\lceil\log2/\log(b/a)\rceil\). ويحتوي المجموع المنتهي الرئيسي على 399 زوجًا بالضبط، وتتحقق \(k\le15\) على كامل النطاق \(2\le a\le20\). ويُعاد استخدام الذاكرة لكل زوج.
إذا كان أكبر أساس متغيرًا \(A\)، فإن الحد المباشر هو \(O(A^2K)\) عملية حسابية و\(O(K)\) عددًا صحيحًا مساعدًا، حيث \(K=\lceil\log2/\log((A+1)/A)\rceil=O(A)\). ويعطي الجمع الأدق على فروق الأسس حدًا قدره \(O(A^2\log A)\) عملية حسابية: بكتابة \(b=a+h\) نحصل على \(k=O(1+a/h)\)، وتبلغ كلفة الجمع على \(1\le h<2a\) مقدار \(O(a\log a)\) لكل \(a\). هذه أعداد للعمليات الحسابية؛ أما كلفة العمليات ذات الدقة الاعتباطية فتعتمد أيضًا على طول المعاملات عندما يكبر \(A\).
int العادية. وتحقق القسمة الصحيحة // التقريب المطلوب إلى الأسفل للكميات غير السالبة في الخطوة الجشعة، مع الحفاظ على متباينات الإمكان دون أخطاء تقريب.BigInteger في Java حسابات صحيحة بدقة اعتباطية ومقارنات دقيقة. وتنفذ عمليات الجمع والضرب والطرح والقسمة الصحيحة البناء نفسه؛ ولأن طرفي القسمة هنا غير سالبين، تعطي divide خارج القسمة المقرب إلى الأسفل الذي تتطلبه الصيغ.unsigned __int128 بوصفه امتدادا للمنصات التي تدعم نمطا صحيحا مناسبا. وتحتاج بعض القوى الوسيطة في هذا التنفيذ إلى أكثر من 64 بت: إذ تتطلب \(21^{15}\) مقدار 66 بت، لذا يجب إجراء عمليات الضرب نفسها منذ البداية بالنوع الأوسع.