Problem 206: Concealed Square

Mathematical Development

Theorem (Divisibility by 10). If $n^2$ has the form $1\_2\_3\_4\_5\_6\_7\_8\_9\_0$, then $10 \mid n$.

Proof. The last digit of $n^2$ is 0, so $n$ must be divisible by both 2 and 5. Hence $10 \mid n$. $\square$

Theorem (Residue Constraint mod 100). Write $n = 10m$. Then $n^2$ has the prescribed form only if $m \equiv 3 \pmod{10}$ or $m \equiv 7 \pmod{10}$, that is, $n \equiv 30 \pmod{100}$ or $n \equiv 70 \pmod{100}$.

Proof. Since $n^2 = 100m^2$, the pattern forces the hundreds digit of $n^2$ to be 9, so the units digit of $m^2$ must be 9. A square ends in 9 exactly when its root ends in 3 or 7. $\square$

Lemma (Search Bounds). The value of $n$ satisfies

Proof. The 19-digit square $n^2$ lies in the interval $[1020304050607080900,\; 1929394959697989990]$. Taking square roots gives

Since $n$ must be divisible by 10, the upper endpoint rounds to $1389199190$. $\square$

Theorem (Uniqueness). There exists exactly one $n$ in the search range satisfying the pattern constraint.

Proof. The search is exhaustive over the candidates with final digits 30 or 70 inside the square-root interval. Computational verification finds exactly one solution:

which matches the pattern $1\_2\_3\_4\_5\_6\_7\_8\_9\_0$. $\square$

Editorial

The digit pattern forces strong modular restrictions before any search begins. Because the square ends in 0, the number itself must be divisible by 10. After dividing by 10, the next fixed digit forces the remaining factor to end in 3 or 7, so the full number must end in 30 or 70.

That leaves a narrow arithmetic progression inside the square-root bounds of the pattern interval. We scan those candidates and test the square digit by digit against 1_2_3_4_5_6_7_8_9_0. The search is still exhaustive, but the modular pruning makes it small enough to finish quickly.

Pseudocode

lower = ceil(sqrt(1020304050607080900))
upper = floor(sqrt(1929394959697989990))

Move lower upward to the first number in [lower, upper]
whose last two digits are 30 or 70.

candidate = lower
While candidate <= upper:
    square = candidate * candidate
    If the digits of square in positions
       1, 3, 5, ..., 19 are 1, 2, 3, ..., 9, 0 respectively:
        return candidate

    If candidate ends in 30:
        candidate += 40
    Otherwise:
        candidate += 60

Complexity Analysis

• Time: $O((n_{\max} - n_{\min}) / 50)$ candidate checks, each with constant-time digit testing.
• Space: $O(1)$.

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    // We need n such that n^2 has the form 1_2_3_4_5_6_7_8_9_0
    // n must end in 30 or 70 (since n divisible by 10, and (n/10)^2 ends in 9)
    // n^2 has 19 digits, so n is roughly 1.01e9 to 1.39e9

    // Use __int128 or just unsigned long long (19 digits fits in ull)
    // max n^2 ~ 1.93e18 which fits in unsigned long long (max ~1.84e19)

    auto check = [](long long n) -> bool {
        long long sq = n * n;
        // Check pattern: digits at positions (from right):
        // pos 0 -> 0, pos 2 -> 9, pos 4 -> 8, ..., pos 18 -> 1
        // i.e., (sq / 10^(2k)) % 10 == (10 - k) for k=0..9, with digit 10-0=10->0 special
        // Actually: the pattern from left is 1_2_3_4_5_6_7_8_9_0
        // From right (position 0 = units): pos 0 = 0, pos 2 = 9, pos 4 = 8, ...
        // pos 2*i should be (10 - i) % 10 for i = 0..9

        for (int i = 0; i <= 9; i++) {
            int digit = sq % 10;
            int expected = (10 - i) % 10;
            if (digit != expected) return false;
            sq /= 100; // skip one digit (the underscore)
        }
        return true;
    };

    // Search range
    long long lo = (long long)ceil(sqrt(1020304050607080900.0));
    long long hi = (long long)floor(sqrt(1929394959697989990.0));

    // Adjust lo to end in 30 or 70
    for (long long n = lo; n <= hi; n++) {
        int r = n % 100;
        if (r == 30 || r == 70) {
            lo = n;
            break;
        }
    }

    for (long long n = lo; n <= hi; n += 10) {
        // n ends in X0, we want X=3 or X=7
        int tens = (n / 10) % 10;
        if (tens != 3 && tens != 7) continue;

        if (check(n)) {
            cout << n << endl;
            return 0;
        }
    }

    return 0;
}

"""
Problem 206: Concealed Square
Find the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0.
"""

import math

def check(n):
    """Check if n^2 matches the pattern 1_2_3_4_5_6_7_8_9_0."""
    sq = n * n
    s = str(sq)
    if len(s) != 19:
        return False
    pattern = "1_2_3_4_5_6_7_8_9_0"
    for i, c in enumerate(pattern):
        if c != '_' and s[i] != c:
            return False
    return True

def solve():
    lo = math.isqrt(1020304050607080900)
    hi = math.isqrt(1929394959697989990)

    # n must end in 30 or 70
    # Start from hi and work down (answer is near upper bound)
    # Or iterate up from lo
    for n in range(lo, hi + 1):
        r = n % 100
        if r != 30 and r != 70:
            continue
        if check(n):
            return n

    return None

# More efficient: step by 40/60 alternating from a starting point ending in 30
def solve_fast():
    lo = math.isqrt(1020304050607080900)
    hi = math.isqrt(1929394959697989990)

    # Align lo to end in 30
    r = lo % 100
    if r <= 30:
        start = lo - r + 30
    elif r <= 70:
        start = lo - r + 70
    else:
        start = lo - r + 130

    n = start
    while n <= hi:
        if check(n):
            return n
        # Alternate between 30 and 70 endings
        if n % 100 == 30:
            n += 40  # jump to next XX70
        else:
            n += 60  # jump to next XX30 (next hundred)

    return None

answer = solve_fast()
print(answer)