Detailed mathematical approach

Problem Summary

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\).

Mathematical Approach

1. Turn matching digits into one exact balance equation

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.

2. Locate the only possible highest nonnegative position

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.$$

3. Dispose of the exceptional and impossible bases

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.

4. Prove that the lower weights can make every integer up to their capacity

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.

5. Maximize the leading digit

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\).

6. A descending digit greedy rule is exact and maximizes the number

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:

• If \(d_i<a-1\), division with remainder gives \(0\le R_{\mathrm{new}}<w_i\le C_i+1\), hence \(R_{\mathrm{new}}\le C_i\).
• If \(d_i=a-1\), the invariant \(R_{\mathrm{old}}\le C_i+(a-1)w_i\) gives \(0\le R_{\mathrm{new}}\le C_i\).

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.

7. Worked example: bases 3 and 4

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\).

Correctness Argument

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.

How the Code Works

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.

Complexity Analysis

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.

Footnotes and References

1. Project Euler 1009 — A Change of Base. The official statement defines the common digit string, the maximum \(F(a,b)\), and the sum \(G(a)\). Its published examples provide independent checkpoints for the implementation and the worked example; they are distinct from the requested final sum.
2. Wolfram MathWorld — Base and positional notation. The positional expansion \(\sum_i d_i a^i\) turns the shared digit string into the balance equation. The article then derives why the most significant differing digit determines numerical order, which is the reason digit-by-digit maximization gives the greatest valid integer.
3. Wolfram MathWorld — Geometric Series. Finite geometric sums simplify the lower-position capacity and yield \(1+C_i-w_i=(b-a)(b^i-1)/(b-1)\). The interval-completeness proof and the greedy optimality proof are derived in this article for these particular weights; the reference supplies the geometric-sum identity.
4. Wolfram MathWorld — Horner's Method. Reading the digits from most to least significant evaluates their positional polynomial by the recurrence \(n\leftarrow an+d_i\). This reconstructs the chosen number with one multiplication and one addition per digit, without separately computing a power for every term.
5. Python documentation — Numeric types. Python integers have unlimited precision, so powers, capacities, and remainders can be computed exactly as ordinary int values. Integer division // implements the required floor for the nonnegative quantities in the greedy step, preserving the feasibility inequalities without rounding error.
6. Java documentation — BigInteger. Java 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.
7. GCC documentation — 128-bit integers. GCC documents 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.