Detailed mathematical approach

Problem Summary

The problem asks for the unique positive integer \(n\) whose square has the decimal form 1_2_3_4_5_6_7_8_9_0, where each underscore stands for an arbitrary digit. In other words, the units digit of \(n^2\) must be \(0\), the hundreds digit must be \(9\), the ten-thousands digit must be \(8\), and so on up to the leading digit \(1\).

A brute-force scan over all nearby integers would still be far larger than necessary. The implementations therefore combine three precise ideas: a tight square-root interval, a modular restriction on the last two digits of the root, and a purely arithmetic verifier that peels the square two digits at a time.

Mathematical Approach

The decimal mask already tells us almost everything. Once we translate the pattern into inequalities and congruences, the search becomes a small filtered sweep rather than an open-ended trial.

Bounding the square and the root

If the hidden digits are all minimized to \(0\), the square is at least

$L=1020304050607080900.$

If the hidden digits are all maximized to \(9\), the square is at most

$U=1929394959697989990.$

Therefore every valid root must satisfy

$\left\lceil \sqrt{L} \right\rceil \le n \le \left\lfloor \sqrt{U} \right\rfloor,$

that is,

$1010101011 \le n \le 1389026623.$

This already collapses the problem to a finite interval of plausible roots.

Why the root must end in 30 or 70

The pattern ends in \(0\), so \(n^2\) is divisible by \(10\). A square can end in \(0\) only when the root itself is divisible by \(10\), so we may write

$n=10m.$

Then

$m^2=\frac{n^2}{100}$

must end in \(9\), because removing the final two zeros from a valid square exposes the fixed digit \(9\). Hence

$m^2 \equiv 9 \pmod{10}.$

The only residues whose squares are \(9\) modulo \(10\) are \(3\) and \(7\), so

$m \equiv 3 \text{ or } 7 \pmod{10},$

which is equivalent to

$n \equiv 30 \text{ or } 70 \pmod{100}.$

This is exactly the filter used by the implementations: among multiples of \(10\), only those ending in \(30\) or \(70\) can possibly work.

Worked example: the trailing-digit filter

It is useful to see the last-digit argument concretely. Among numbers ending in \(10,30,50,70,90\), the corresponding squares satisfy

$10^2 \equiv 100,\quad 30^2 \equiv 900,\quad 50^2 \equiv 500,\quad 70^2 \equiv 900,\quad 90^2 \equiv 100 \pmod{1000}.$

A valid square must end in \(900\), because its last three digits are forced to be 9_0 with the middle digit hidden. The congruence table shows that only the endings \(30\) and \(70\) survive.

Turning the decimal mask into an arithmetic invariant

After the residue filter, the remaining question is whether a candidate square matches every forced digit. The code does not build strings or use pattern matching. Instead, it checks the required digits numerically.

For a candidate square \(s=n^2\), validity is equivalent to the system

$s \equiv 0 \pmod{10},$

and, for \(k=1,2,\dots,9\),

$\left\lfloor \frac{s}{10^{2k}} \right\rfloor \bmod 10 = 10-k.$

These equations say exactly that the digits in positions \(10^0,10^2,10^4,\dots,10^{18}\) are \(0,9,8,\dots,1\). The implementations realize this by first checking the units digit, then repeatedly dividing by \(100\). Each division discards one hidden digit together with one already verified fixed digit, so the next fixed digit becomes the new units digit.

If we define

$s_0=s,\qquad s_{r+1}=\left\lfloor \frac{s_r}{100} \right\rfloor,$

then a valid square must satisfy

$s_0 \bmod 10 = 0,\qquad s_r \bmod 10 = 10-r \quad (r=1,\dots,9).$

This invariant is the heart of the checker.

Why the search is small enough

The interval from \(1010101011\) to \(1389026623\) contains about \(3.79\times 10^8\) integers, but the first divisibility condition lets us step by \(10\), and the residue condition keeps only two endings out of every hundred. That leaves only about \(7.6\times 10^6\) serious candidates, and each candidate needs only a constant number of arithmetic tests. For this problem size, that is entirely practical.

How the Code Works

Establishing the search interval

The C++, Python, and Java implementations begin by computing the integer square-root bounds implied by the smallest and largest masked squares. The lower bound is then advanced to a multiple of \(10\), because no valid root can avoid that divisibility condition.

Enumerating only admissible endings

The main loop advances through the interval in steps of \(10\). For each candidate root, the implementation inspects its last two digits and immediately discards anything that is not congruent to \(30\) or \(70\) modulo \(100\). This removes the overwhelming majority of candidates before any square-pattern work is done.

Checking the masked square numerically

For the surviving candidates, the implementation squares the root and performs the digit test described above. It first verifies the final \(0\), then repeatedly divides the square by \(100\) and checks that the newly exposed units digit is \(9,8,7,\dots,1\) in order. Because the pattern is fixed, the verifier uses only integer arithmetic and a short loop over those nine required digits.

The search stops as soon as a candidate passes the full test. One implementation also includes small checkpoint cases for the digit verifier, confirming that the mask checker accepts the canonical lower template and rejects a nearby incorrect value.

Complexity Analysis

Let

$I=\left\lfloor \sqrt{U} \right\rfloor-\left\lceil \sqrt{L} \right\rceil+1.$

A naive scan over all integers in that interval would cost \(O(I)\) candidate generations. The implementations still have linear worst-case behavior in the width of the interval, but with a much smaller constant: they inspect only multiples of \(10\), and among those they fully test only the roots congruent to \(30\) or \(70\) modulo \(100\). So the number of full pattern checks is roughly \(I/50\).

Each pattern check performs a square and then a fixed number of digit inspections, so its cost is \(O(1)\). The overall running time is therefore \(O(I)\) with strong constant-factor pruning, and the memory usage is \(O(1)\) because the algorithm stores only a handful of integers.

Footnotes and References

1. Project Euler problem page: Project Euler 206 - Concealed Square
2. Modular arithmetic: Wikipedia - Modular arithmetic
3. Integer square root: Wikipedia - Integer square root
4. Square number: Wikipedia - Square number
5. Decimal positional notation: Wikipedia - Decimal