Detailed mathematical approach

Problem Summary

Fix the prime base

$p=10^9+7.$

For each \(d\in\{1,2,\dots,100000\}\), the implementation studies the digit

$a=p-d,$

so it is really searching among the \(100000\) largest nonzero base-\(p\) digits. Define

$M_p(a)=\min\{m\ge 1:\text{the base-}p\text{ expansion of }m^2\text{ contains the digit }a\}.$

The computed quantity is therefore

$\sum_{d=1}^{100000} M_p(p-d).$

A direct search is hopeless because the first valid square can be on the scale of \(p\), so the solution turns the digit condition into modular and interval conditions.

Mathematical Approach

The key observation is that a fixed digit in a fixed base corresponds to a family of arithmetic intervals, and for the specific digits \(a=p-d\) those intervals collapse to only two relevant cases.

Step 1: Translate a Digit Occurrence into an Interval

A digit \(a\) appears in the base-\(p\) expansion of an integer \(N\) at position \(k\ge 0\) exactly when there exists an integer \(t\ge 0\) such that

$a\,p^k+t\,p^{k+1}\le N\le a\,p^k+t\,p^{k+1}+p^k-1.$

Applying this to \(N=m^2\), every possible occurrence of \(a\) inside a square is equivalent to asking whether some interval of that form contains a perfect square.

For fixed \(k\) and \(t\), the smallest candidate square root is always

$m=\left\lceil\sqrt{a\,p^k+t\,p^{k+1}}\right\rceil.$

So the whole problem is reduced to finding the first interval whose lower endpoint rounds up to a square still inside the same interval.

Step 2: Why Only the Unit Digit or the Next Digit Can Matter

Here the target digit is \(a=p-d\) with \(1\le d\le 100000\), so \(a\) is very close to \(p\) and in particular

$a>\frac{p}{2}.$

If \(a\) appears in the unit position (\(k=0\)), then we only need a congruence modulo \(p\).

If instead \(a\) appears at any higher position (\(k\ge 1\)), then

$m^2\ge a\,p>\frac{p^2}{2},$

hence

$m>\frac{p}{\sqrt{2}}>\frac{p}{2}.$

This matters because any square root found modulo \(p\) can be represented by a positive integer at most \(p/2\). Therefore:

If the unit-digit case is possible, it automatically gives the global minimum.

If the unit-digit case is impossible, then the smallest remaining possibility is the \(p\)-digit (\(k=1\)); positions \(k\ge 2\) are much larger still.

Step 3: Quadratic-Residue Branch

To place the digit \(a\) in the unit position, we need

$m^2\equiv a \pmod p.$

Euler's criterion decides whether this congruence has a solution:

$a^{(p-1)/2}\equiv 1 \pmod p \iff a\text{ is a quadratic residue mod }p.$

Because

$p\equiv 3\pmod 4,$

a square root is given directly by

$r\equiv a^{(p+1)/4}\pmod p.$

The two residue-class solutions are \(r\) and \(p-r\), so the smallest positive integer producing the digit \(a\) in the final base-\(p\) digit is

$M_p(a)=\min(r,p-r).$

No larger-position occurrence can beat this, because every larger-position occurrence already needs \(m>p/\sqrt2\).

Step 4: Non-Residue Branch Becomes an Interval Search

If \(a\) is not a quadratic residue modulo \(p\), then the unit-digit case is impossible. The first possible place is therefore the coefficient of \(p\), so we look for squares in intervals

$I_t=[a\,p+t\,p^2,\ a\,p+t\,p^2+p-1]\qquad (t\ge 0).$

Since \(a=p-d\), the lower endpoint becomes

$L_t=a\,p+t\,p^2=p^2-dp+t\,p^2.$

For a fixed \(t\), the smallest square that could possibly land in the interval is

$m_t=\left\lceil\sqrt{L_t}\right\rceil.$

The interval contains a square exactly when

$m_t^2\le L_t+p-1.$

The first \(t\) satisfying this condition yields the global minimum, because the intervals are strictly increasing with \(t\).

Step 5: Worked Examples

A small residue example is base \(11\) with target digit \(9\). Since

$9\equiv 3^2\pmod{11},$

the smallest positive representative is \(3\), and indeed

$3^2=9,$

so \(M_{11}(9)=3\).

A small non-residue example is base \(11\) with target digit \(10\). Here \(10\) is not a square modulo \(11\), so the unit-digit case is impossible. We must search the \(11\)-digit intervals:

$[110,120],\qquad [231,241],\qquad [352,362],\dots$

The corresponding ceiling square roots are

$11,\qquad 16,\qquad 19.$

The first two squares miss their intervals, because

$11^2=121>120,\qquad 16^2=256>241.$

The third one works:

$19^2=361\in[352,362].$

In base \(11\), this is

$361=2\cdot 11^2+10\cdot 11+9,$

so the digit \(10\) appears and

$M_{11}(10)=19.$

This is exactly the logic used by the interval branch.

How the Code Works

The C++, Python, and Java implementations precompute the two exponents

$\frac{p-1}{2}\qquad\text{and}\qquad\frac{p+1}{4},$

together with \(p^2\). Then they loop through \(d=1,\dots,100000\), form the target digit \(a=p-d\), and use fast modular exponentiation to evaluate Euler's criterion.

If \(a\) is a quadratic residue, the implementation computes the modular square root by the closed form valid for primes \(p\equiv 3\pmod 4\), then takes the smaller of the two symmetric representatives.

If \(a\) is a non-residue, the implementation starts from the first interval lower bound \(p^2-dp\), repeatedly computes the ceiling integer square root of the current lower bound, and checks whether that square stays within the interval of width \(p\). If not, it shifts the interval upward by another \(p^2\) and repeats.

Each answer is added to a running total. Wide integer arithmetic is used where necessary so that values around \(p^2\) are handled safely.

Complexity Analysis

Let \(D=100000\) be the number of queried digits. Each digit requires one modular exponentiation to test quadratic residuosity, and residue cases require one more modular exponentiation to recover a square root. Both operations cost \(O(\log p)\) modular multiplications.

In the non-residue case there is an additional interval loop. If \(T_d\) denotes the number of interval lifts needed for the digit \(p-d\), the total running time is

$O\!\left(D\log p+\sum_{d=1}^{D} T_d\right).$

The memory usage is \(O(1)\) beyond the storage needed for a few wide integers. For the fixed prime in the problem, this behaves essentially linearly in the number of digits being summed.

Footnotes and References

1. Problem page: Project Euler 817
2. Euler's criterion: Wikipedia - Euler's criterion
3. Legendre symbol: Wikipedia - Legendre symbol
4. Quadratic residue: Wikipedia - Quadratic residue
5. Integer square root: Wikipedia - Integer square root