Problem 206: Concealed Square

Project Euler Problem 206 Solution

EulerSolve provides an optimized solution for Project Euler Problem 206, Concealed Square, with C++, Python, Java, and a step-by-step mathematical explanation.

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....

Detailed mathematical approach

Problem Summary

We must find the positive integer $n$ whose square has the form 1_2_3_4_5_6_7_8_9_0, where each underscore stands for a single digit. So $n^2$ has $19$ digits: the fixed digits $1,2,\dots,9,0$ in this order, with one unknown digit between any two neighbours. The statement says that exactly one such $n$ exists and asks for $n$ itself; it gives no further examples. ^[1]

The whole solution in one sentence: the smallest and the largest number of this form confine $n$ to a range of about $3.8\cdot10^8$ integers, the last digits of the pattern force $n$ to end in $30$ or $70$, and squaring the remaining $7.6$ million candidates in turn and comparing their fixed digits with the pattern finds the root.

Mathematical Approach

We run through the possible roots, not through the $10^9$ fillings of the blanks, and test their squares against the pattern.

1. Reading the pattern

We number the digits from the right, starting with position $0$ for the units digit, so that the digit in position $j$ counts $10^j$ times. ^[2] A number $s$ has the form of the problem when it has exactly $19$ digits, position $0$ holds $0$, and position $2k$ holds $10-k$ for $k=1,2,\dots,9$: position $2$ holds $9$, position $4$ holds $8$, and the leading position $18$ holds $1$. The nine odd positions $1,3,\dots,17$ are the blanks, so exactly $10^9$ numbers have the form.

2. A range for the root

Filling every blank with $0$ gives the smallest number of the form, and filling every blank with $9$ gives the largest:

$$\begin{aligned}L&=1020304050607080900,\\U&=1929394959697989990.\end{aligned}$$

Squaring preserves the order of positive numbers, so $L\le n^2\le U$ holds exactly when $\sqrt L\le n\le\sqrt U$. With $\sqrt L\approx1010101010.10$ and $\sqrt U\approx1389026623.11$ this gives

$$1010101011\le n\le1389026623.$$

The two ends are the ceiling of $\sqrt L$ and the floor of $\sqrt U$; in exact integer arithmetic they are $\operatorname{isqrt}(L-1)+1$ and $\operatorname{isqrt}(U)$, where the integer square root $\operatorname{isqrt}(x)=\lfloor\sqrt x\rfloor$ is the largest integer whose square is at most $x$. ^[3] The range contains $378\,925\,613$ integers. All numbers from $L$ to $U$ have $19$ digits and begin with $1$, because $10^{18}\le L$ and $U\lt2\cdot10^{18}$.

3. The last digits of a square

Write $n=10q+r$, where $r$ is the units digit of $n$. Then $n^2=10\,(10q^2+2qr)+r^2$, so $n^2$ and $r^2$ have the same units digit: the last digit of a square depends only on the last digit of its root. In modular arithmetic, $a\bmod d$ is the remainder of $a$ on division by $d$, and $a\equiv b\pmod d$ means that $a$ and $b$ leave the same remainder; in this language, $n\equiv r\pmod{10}$ implies $n^2\equiv r^2\pmod{10}$. ^[5] The squares $0,1,4,9,16,25,36,49,64,81$ of the digits $r=0,1,\dots,9$ end in $0,1,4,9,6,5,6,9,4,1$, and two conclusions follow from this list. ^[4]

The root ends in $0$. The pattern ends in $0$, and only $r=0$ gives a square ending in $0$. So $n=10m$ for a positive integer $m$, and $n^2=100m^2$ ends in $00$. The blank in position $1$ is therefore always $0$, and the digits of $m^2$ are those of $n^2$ without its last two zeros: $m^2$ has the $17$-digit form 1_2_3_4_5_6_7_8_9.
Then $m$ ends in $3$ or $7$. The units digit of $m^2$ is the fixed $9$ in position $2$ of $n^2$, and only $r=3$ and $r=7$ give a square ending in $9$. So $m$ ends in $3$ or $7$, and $n=10m$ ends in $30$ or $70$.

Every root therefore satisfies $n\equiv30$ or $n\equiv70\pmod{100}$. The filter loses no root, but it only guarantees that $n^2$ ends in $900$; the other fixed digits must still be checked.

4. Checking the fixed digits with arithmetic

Dividing a whole number by $100$ and dropping the remainder removes its last two digits: $12345$ becomes $123$ and then $1$, and the units digits $5$, $3$ and $1$ of these three numbers are the digits of $12345$ in positions $0$, $2$ and $4$. In general, with $s_0=s$ and

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

the number $s_r=\lfloor s/100^r\rfloor$ is $s$ without its last $2r$ digits, so the units digit of $s_r$ is the digit of $s$ in position $2r$. ^[2] A number $s$ with $19$ digits therefore has the form exactly when, for $r=1,2,\dots,9$,

$$\begin{aligned}s_0\bmod10&=0,\\s_r\bmod10&=10-r.\end{aligned}$$

The conditions do not check the length of $s$, but inside the range of Section 2 every square has $19$ digits. For $s=L$ the numbers $s_1=10203040506070809$, $s_2=102030405060708$, and so on down to $s_9=1$, end in $9,8,\dots,1$, so $L$ passes, as it must. The number $1020304050607080000$, which differs from $L$ only in position $2$, fails at $r=1$: $s_1=10203040506070800$ ends in $0$, not in $9$.

5. Worked example: the pattern 1_4_9_0

The same three steps solve a small cousin of the problem by hand: find the positive integer whose square has the seven-digit form 1_4_9_0.

Range. The smallest and the largest number of this form are $1040900$ and $1949990$. Since $1020^2=1040400$ is too small and $1397^2=1951609$ is too large, the root lies between $1021$ and $1396$, a range of $376$ integers.
Last digits. The pattern ends in 9_0 like the real one, so by Section 3 the root ends in $30$ or $70$. Eight candidates remain: $1030$, $1070$, $1130$, $1170$, $1230$, $1270$, $1330$ and $1370$.
Digits. Their squares are $1060900$, $1144900$, $1276900$, $1368900$, $1512900$, $1612900$, $1768900$ and $1876900$. All of them end in $900$ and begin with $1$, as Sections 2 and 3 predict. Their digits in position $4$ are $6,4,7,6,1,1,6,7$, and only $1144900$ has the required $4$.

So $1070$ is the only root: $1070^2=1144900$ reads 1_4_9_0 with the blanks $1$, $4$ and $0$. Uniqueness is not automatic: by the same steps 1_1_9_0 has two roots, $1230$ and $1270$, and 1_2_9_0, which keeps the first two and the last two fixed digits of the real pattern, has none.

6. How much is left to search

The range of Section 2 contains $37\,892\,561$ multiples of $10$, from $1010101020$ to $1389026620$, and $7\,578\,512$ of them end in $30$ or $70$, from $1010101030$ to $1389026570$: about $132$ times fewer candidates than fillings of the blanks.

Stronger filters exist, because the last $k$ digits of $m^2$ depend only on the last $k$ digits of $m$. ^[5] Only $24$ of the $1000$ possible last three digits of $m$ give a square with units digit $9$ and hundreds digit $8$, such as $053$, since $53^2=2809$; requiring the $7$ in position $4$ as well leaves $240$ of the $10^5$ possible last five digits. Of the $37\,892\,561$ values of $m=n/10$ in the range, $909\,420$ end in one of the $24$ and $90\,942$ in one of the $240$. The published programs keep the plain filter, which suffices.

How the Code Works

The C++ program ^[8] starts in main. parse_arguments accepts only --skip-checkpoints; any other argument gives an error message and exit code $1$. Unless the checkpoints are skipped, run_checkpoints runs the two tests of Section 4: matches_pattern must accept $L$ and reject $1020304050607080000$, and a failure gives exit code $2$. Then main prints the value returned by solve.

solve stores $L$ and $U$ as the unsigned 64-bit constants low_sq and high_sq and takes the ceiling and the floor of their square roots, computed in long double, as the bounds low and high of Section 2. A short loop raises low to $1010101020$, the next multiple of $10$. The main loop steps base through the multiples of $10$ up to high, skips every value whose last two digits base % 100 are not $30$ or $70$ (Section 3), squares the others in unsigned 64-bit arithmetic and passes the square to matches_pattern. That function is Section 4 step by step: it rejects a square whose units digit is not $0$, divides by $100$, and then, for d from $9$ down to $1$, compares the units digit with d and divides by $100$ again. solve returns the first base that passes, which by uniqueness is the root; its fallback value $-1$ is never reached.

Every square formed is at most $1389026623^2$, which is below $1.93\cdot10^{18}\lt2^{63}$, so it fits into the 64-bit integers of C++ and into Java's long. Java, and C++ wherever long double is no wider than double, first convert the constants to double, which moves them by less than $256$, the spacing of doubles near $U$, whichever neighbouring double is chosen. With IEEE arithmetic, whose square roots are correctly rounded, ^[7] the computed roots then stay within $10^{-6}$ of $\sqrt L$ and $\sqrt U$, which both lie about $0.1$ above an integer, so the bounds come out exactly as in Section 2.

The Python program uses exact integers and takes both bounds with math.isqrt, the floor of the exact square root. ^[6] Its lower bound $1010101010$ is one less than the ceiling and already a multiple of $10$, so its loop starts one step earlier, at a number ending in $10$ that the filter discards. It writes the digit test out inside the loop with a flag ok, and solve prints the root instead of returning it. The Java program has the loop of solve in main and the test in matchesPattern, without options or checkpoints.

Complexity and Verification

The loop visits at most $37\,892\,561$ multiples of $10$, one more in Python, and squares at most $7\,578\,512$ candidates, each tested with at most ten divisions and comparisons, so the time is linear in the width of the range of roots and the memory is a few integers. On a laptop with an Apple M4 Max chip (Apple clang with -O2, OpenJDK 17, CPython 3.11), even a pass over the whole range that does not stop at the match takes about $0.03$ s in C++, $0.1$ s in Java and $4$ s in Python.

The C++ checkpoints test the digit check of Section 4 on one number of the form and one that is not. Further checks, not part of the published solutions, were run for this article. An independent C program tested every $n$ from $10^9$ to $3162277660$, all $2\,162\,277\,661$ integers whose squares have $19$ digits, without the range of Section 2 or the filter of Section 3, and found exactly one whose square has the form, the number printed by all three published programs. So the root is unique, and the range and the filter lose nothing. The small cases of Section 5, the counts of Section 6 and the floating-point bounds were checked by separate brute-force and exact computations.

Footnotes and References

The references below supply the background facts used above; the range, the filter, the worked example and all counts are derived in this article.

Project Euler 206 — Concealed Square. The official statement asks for the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0, where each “_” is a single digit; it gives no further examples.
Wikipedia — Positional notation. Each digit is weighted by the power of the base that belongs to its position, and the digits can be found from the right as the remainders of repeated divisions by the base.
Wikipedia — Integer square root. The integer square root isqrt(n) of a non-negative integer n is the greatest integer less than or equal to √n, that is ⌊√n⌋.
Wikipedia — Square number. In base 10 a square can end only in 0, 1, 4, 5, 6 or 9; the square of a number ending in 0 ends in 00, and the square of a number ending in 3 or 7 ends in an even digit followed by 9.
Wikipedia — Modular arithmetic. Two integers are congruent modulo m when their difference is a multiple of m; congruences are compatible with multiplication and powers, so for the modulus 10ᵏ the last k digits of a square depend only on those of its root.
Python 3.11 documentation — math.isqrt. The function returns the floor of the exact square root of a nonnegative integer n, the greatest a with a² ≤ n; for positive n the ceiling of the square root is 1 + isqrt(n − 1).
Java — Math.sqrt returns the double closest to the true square root, and cppreference — std::sqrt, with overloads for float, double and long double, notes that the IEEE standard requires the result to be correctly rounded. By cppreference — Implicit conversions, an integer that cannot be represented exactly becomes the closest higher or lower value, as the implementation chooses; IEEE arithmetic rounds to nearest.
C++ — Euler206.cpp. The linked immutable revision contains parse_arguments, matches_pattern, solve and run_checkpoints. It is the implementation record for this article.

Problem 206 source code

C++

#include <cmath>
#include <cstdint>
#include <iostream>
#include <string>

namespace {

using i64 = std::int64_t;
using u64 = std::uint64_t;

struct Options {
    bool run_checkpoints = true;
};

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return true;
}

bool matches_pattern(u64 sq) {
    if (sq % 10ULL != 0ULL) {
        return false;
    }
    sq /= 100ULL;

    for (int d = 9; d >= 1; --d) {
        if (sq % 10ULL != static_cast<u64>(d)) {
            return false;
        }
        sq /= 100ULL;
    }

    return true;
}

i64 solve() {
    const u64 low_sq = 1020304050607080900ULL;
    const u64 high_sq = 1929394959697989990ULL;

    i64 low = static_cast<i64>(std::ceil(std::sqrt(static_cast<long double>(low_sq))));
    const i64 high = static_cast<i64>(std::floor(std::sqrt(static_cast<long double>(high_sq))));

    while (low % 10 != 0) {
        ++low;
    }

    for (i64 base = low; base <= high; base += 10) {
        const int tail = static_cast<int>(base % 100);
        if (tail != 30 && tail != 70) {
            continue;
        }

        const u64 sq = static_cast<u64>(base) * static_cast<u64>(base);
        if (matches_pattern(sq)) {
            return base;
        }
    }

    return -1;
}

bool run_checkpoints() {
    if (!matches_pattern(1020304050607080900ULL)) {
        std::cerr << "Checkpoint failed for pattern matcher positive case" << '\n';
        return false;
    }
    if (matches_pattern(1020304050607080000ULL)) {
        std::cerr << "Checkpoint failed for pattern matcher negative case" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve() << '\n';
    return 0;
}

Python

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

from math import isqrt

def solve():
    # Pattern: 1_2_3_4_5_6_7_8_9_0
    # Square ends in 0 so root ends in 0
    # Range: sqrt(1020304050607080900) to sqrt(1929394959697989990)
    low = isqrt(1020304050607080900)
    high = isqrt(1929394959697989990)
    # Root must end in 0, so step by 10. Actually ends in 30 or 70 mod 100.
    while low % 10 != 0:
        low += 1

    for base in range(low, high+1, 10):
        tail = base % 100
        if tail != 30 and tail != 70:
            continue
        sq = base * base
        # Check pattern: 1_2_3_4_5_6_7_8_9_0
        if sq % 10 != 0: continue
        sq //= 100
        ok = True
        for d in range(9, 0, -1):
            if sq % 10 != d:
                ok = False
                break
            sq //= 100
        if ok:
            print(base)
            return

solve()

Java

public class Euler206 {
    public static void main(String[] args) {
        long low = (long) Math.ceil(Math.sqrt(1020304050607080900.0));
        long high = (long) Math.floor(Math.sqrt(1929394959697989990.0));
        while (low % 10 != 0)
            low++;
        for (long base = low; base <= high; base += 10) {
            int tail = (int) (base % 100);
            if (tail != 30 && tail != 70)
                continue;
            long sq = base * base;
            if (matchesPattern(sq)) {
                System.out.println(base);
                return;
            }
        }
    }

    static boolean matchesPattern(long sq) {
        if (sq % 10 != 0)
            return false;
        sq /= 100;
        for (int d = 9; d >= 1; d--) {
            if (sq % 10 != d)
                return false;
            sq /= 100;
        }
        return true;
    }
}