Problem 206: Concealed Square

Mathematical Foundation

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. Since $n^2 \equiv 0 \pmod{10}$, we must have $10 \mid n$ (for if $\gcd(n, 5) = 1$ and $\gcd(n, 2) = 1$, then $n^2 \equiv 1$ or other nonzero residues mod 10). More precisely, $n^2 \equiv 0 \pmod{10}$ requires $5 \mid n$ and $2 \mid n$, 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}$, i.e., $n \equiv 30 \pmod{100}$ or $n \equiv 70 \pmod{100}$.

Proof. With $n = 10m$, we have $n^2 = 100m^2$. The pattern requires the digit at position 16 (0-indexed from the left in the 19-digit number) to be 9, which means the tens digit of $n^2$ must fit $\_9\_0$. Equivalently, the units digit of $m^2$ must be 9. Since $k^2 \equiv 9 \pmod{10}$ iff $k \equiv 3$ or $k \equiv 7 \pmod{10}$, we get $m \equiv 3$ or $7 \pmod{10}$. $\square$

Lemma (Search Bounds). The value of $n$ satisfies $1010101010 \leq n \leq 1389199190$.

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

Since $n$ must be divisible by 10, the upper bound 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 approximately $7.58 \times 10^6$ candidates (values of $n$ in $[1010101010, 1389199190]$ with $n \equiv 30$ or $70 \pmod{100}$). Computational verification confirms exactly one solution: $n = 1389019170$, with $n^2 = 1929374254627488900$, which matches the pattern $1\_2\_3\_4\_5\_6\_7\_8\_9\_0$. $\square$

Editorial

We lo = 1010101030 (first multiple of 10 in range with m ending in 3). Candidates are generated from the derived formulas, filtered by the required conditions, and processed in order until the desired value is obtained.

Pseudocode

Input: pattern 1_2_3_4_5_6_7_8_9_0
Output: the unique n such that n^2 matches the pattern
lo = 1010101030  (first multiple of 10 in range with m ending in 3)
For n = lo to hi, stepping by 100:

Complexity Analysis

• Time: $O((n_{\max} - n_{\min})/50) \approx O(7.58 \times 10^6)$ candidate evaluations. Each evaluation involves one multiplication and at most 10 digit extractions, all $O(1)$.
• 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)