Detailed mathematical approach

Problem Summary

Let \(P(x)\) denote the next lexicographically larger permutation of the decimal digits of \(x\). If the digits of \(x\) are already in nonincreasing order, then no larger permutation exists and we define \(P(x)=0\). Problem 925 asks for

$S(k)=\sum_{n=1}^{10^k-1} P(n^2)\pmod{10^9+7}.$

For \(k=16\), a direct loop over all \(10^{16}-1\) roots is impossible. The solutions therefore do not enumerate roots one by one. Instead they group roots by decimal suffixes and exploit the fact that the low digits of a square depend only on the low digits of the root.

Mathematical Approach

The core idea is to reveal the square from right to left. As soon as the decisive ascent for the next-permutation operation is known, an entire block of roots can be collapsed into a single contribution.

Separating the easy square-sum term from the permutation correction

Introduce the digit-permutation correction

$\Delta(x)=\begin{cases} P(x)-x,&\text{if a larger digit permutation exists},\\ -x,&\text{otherwise}. \end{cases}$

Then \(x+\Delta(x)=P(x)\), with the second line exactly encoding the convention \(P(x)=0\). Hence

$S(k)\equiv \sum_{n=1}^{10^k-1} n^2+\sum_{n=1}^{10^k-1}\Delta(n^2)\pmod{10^9+7}.$

The first sum is closed form. Writing \(N=10^k\),

$\sum_{n=1}^{10^k-1} n^2=\sum_{n=0}^{N-1} n^2=\frac{N(N-1)(2N-1)}{6}.$

So the real problem is to evaluate the correction sum efficiently.

Encoding a root by trailing zeros and a revealed suffix

Every positive root \(n<10^k\) can be written uniquely as

$n=(q\,10^\ell+r)\,10^t,$

where \(t\ge 0\) is the number of trailing zeros, \(r\) is an \(\ell\)-digit suffix block whose rightmost digit is nonzero, and \(q\) is the still-unknown higher prefix. In the state description, leading zeros inside the width-\(\ell\) block are allowed; that is why blocks such as \(01\) genuinely occur in the recursion.

The implementations start from a one-digit nonzero block \(r=d\in\{1,\dots,9\}\), choose \(t\in\{0,\dots,k-1\}\), and then prepend new digits on the left. Once \(\ell+t\ge k\), every root digit has been fixed and the recursion stops.

The square-suffix invariant

For a fixed state \((r,\ell,t)\), all completions share the same low square digits because

$n^2=(q\,10^\ell+r)^2\,10^{2t}\equiv r^2\,10^{2t}\pmod{10^{\ell+2t}}.$

Thus the lowest \(\ell+2t\) digits of \(n^2\) are already determined by the revealed root suffix and by the trailing-zero count. If we prepend a new digit \(d\in\{0,\dots,9\}\) and set

$r'=d\,10^\ell+r,$

then one more square digit becomes visible:

$n^2\equiv (r')^2\,10^{2t}\pmod{10^{\ell+1+2t}}.$

The recursion therefore grows a known square suffix one decimal place at a time.

Detecting the exact moment when the next-permutation pivot is fixed

Let the width-\(\ell\) decimal block representing \(r^2\bmod 10^\ell\) be padded with leading zeros if necessary. A crucial invariant is that this block is nonincreasing from left to right in every recursive state that continues deeper. The base case \(\ell=1\) is trivial, and the recursion preserves the invariant precisely by deciding whether to continue or to collapse the branch.

Write

$a=\left\lfloor\frac{r^2\bmod 10^\ell}{10^{\ell-1}}\right\rfloor,\qquad b=\left\lfloor\frac{(r')^2\bmod 10^{\ell+1}}{10^\ell}\right\rfloor.$

Here \(a\) is the leftmost digit of the current known square suffix, and \(b\) is the new digit inserted immediately to its left.

If \(b\ge a\), then the enlarged \((\ell+1)\)-digit suffix is still nonincreasing, so the rightmost ascent needed by the next-permutation algorithm has not appeared yet. The branch must be extended further.

If \(b<a\), then the digits to the right were already nonincreasing, and the first ascent from the right is now exactly the boundary \(b\mid a\). That means the pivot of the next-permutation operation has been located completely inside the revealed suffix. Digits farther to the left will remain untouched by the permutation step, so the correction \(\Delta(n^2)\) no longer depends on the unrevealed higher prefix.

Collapsing an entire block of higher prefixes

After prepending \(d\), there remain

$m=k-\ell-t-1$

root digits that have not been chosen yet. There are therefore \(10^m\) completions of the current root state. All corresponding squares share the same revealed suffix

$u=\big((r')^2\bmod 10^{\ell+1}\big)\,10^{2t}.$

Once \(b<a\), every completion whose square has a genuine nonzero prefix to the left of that suffix has the same correction as the representative number \(10^{\ell+1+2t}+u\). This representative need not itself be a square; it is only a convenient number with the same decisive suffix and with a real digit to the left of it.

The only subtle case is the completion with empty higher root prefix. If \((r')^2<10^{\ell+1}\), then that completion produces the actual square \(u\), where the apparent leading zero in the width-\((\ell+1)\) block was only padding. In that one case we must use \(\Delta(u)\) rather than the positive-prefix representative.

So the whole block contributes

$C(r',\ell+1,t)= \begin{cases} \Delta(u)+(10^m-1)\,\Delta\!\left(10^{\ell+1+2t}+u\right),&(r')^2<10^{\ell+1},\\ 10^m\,\Delta\!\left(10^{\ell+1+2t}+u\right),&(r')^2\ge 10^{\ell+1}. \end{cases}$

The recursion and the final assembly

Let \(F(r,\ell,t)\) be the sum of \(\Delta(n^2)\) over all roots consistent with the state \((r,\ell,t)\). For each prepended digit \(d\), with \(r'=d\,10^\ell+r\), the recursion is

$F(r,\ell,t)=\sum_{d=0}^{9} \begin{cases} C(r',\ell+1,t),&b<a,\\ F(r',\ell+1,t),&b\ge a, \end{cases}$

and the base case is

$F(r,\ell,t)=\Delta\!\left((r\,10^t)^2\right)\qquad\text{when }\ell+t\ge k.$

Finally, every positive root belongs to exactly one initial state determined by its last nonzero digit and its trailing-zero count, so

$\sum_{n=1}^{10^k-1}\Delta(n^2)=\sum_{d=1}^{9}\sum_{t=0}^{k-1}F(d,1,t).$

Worked examples

Start with the branch \(r=3\), \(\ell=1\), \(t=0\). The known square suffix is \(3^2=9\), so \(a=9\). Prepend the digit \(1\): then \(r'=13\) and

$13^2=169,\qquad 169\bmod 100=69,$

so \(b=6\). Since \(6<9\), the pivot is fixed at the boundary \(6\mid 9\). Therefore all squares coming from roots ending in \(13\) share the same correction:

$169\to 196,\qquad 113^2=12769\to 12796,\qquad 213^2=45369\to 45396.$

In each case the change is \(27\), so the branch can be aggregated immediately.

The padding-zero exception is equally important. The width-two block \(01\) represents a real recursive state. For \(1^2=1\), that left zero is not an actual digit, so there is no larger permutation and \(\Delta(1)=-1\). But \(101^2=10201\) has the same visible suffix \(01\) together with a genuine higher prefix, and its next permutation is \(10210\), giving correction \(9\). This is exactly the split handled by the two cases in \(C(r',\ell+1,t)\).

How the Code Works

Precomputation and the closed-form contribution

The C++, Python, and Java implementations precompute powers of ten both as ordinary integers and modulo \(10^9+7\). They begin the answer with the closed-form square sum \(\frac{N(N-1)(2N-1)}{6}\) for \(N=10^k\), and then add the correction sum produced by the recursion.

Recursive exploration of suffix states

From each initial choice of the last nonzero digit \(d\) and the trailing-zero count \(t\), the implementation prepends digits on the left. At each state it computes the old leftmost known square digit \(a\), tests every extension digit through the new digit \(b\), and applies exactly the mathematical rule above: recurse when \(b\ge a\), collapse the whole branch when \(b<a\).

The aggregation count \(10^m\), the suffix value \(u\), and the padding-zero split are all handled directly from the state parameters. No root in the collapsed block is enumerated individually.

Evaluating the permutation correction itself

Whenever a leaf or an aggregated representative must be evaluated, the implementation converts the relevant number into a digit array, performs the standard next lexicographic permutation on those digits, and reads the result back modulo \(10^9+7\). If no next permutation exists, the contribution is \(-x\) modulo \(10^9+7\), matching the definition of \(\Delta(x)\).

The three languages differ only in how they store large integers. The recursive structure, the suffix tests, and the block-aggregation formulas are the same in all three versions.

Complexity Analysis

Let \(T(k)\) be the number of suffix states that are actually visited before they either recurse further or collapse into a block contribution. The running time is \(O(T(k)\,k)\): each state tries ten prepended digits, and every representative next-permutation evaluation touches at most \(2k\) decimal digits because the square of a \(k\)-digit root has at most \(2k\) digits.

A trivial upper bound is \(T(k)\le 10^k-1\), since without early collapses the search tree would degenerate into root-by-root enumeration. The speedup comes from the many branches where the inequality \(b<a\) appears early, allowing a whole family of \(10^m\) roots to be replaced by one or two representative evaluations. Memory usage is \(O(k)\) for the power tables and recursion depth, plus temporary digit arrays of length at most \(2k\).

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=925
2. Lexicographic next permutation: Wikipedia - Permutation, generation in lexicographic order
3. Lexicographic order: Wikipedia - Lexicographic order
4. Square pyramidal number: Wikipedia - Square pyramidal number
5. Positional notation: Wikipedia - Positional notation
6. Modular arithmetic: Wikipedia - Modular arithmetic