Keep the Ordering (Problem K, CS3233 Midterm Contest 2025, 2025)
Time limit: 1 sec
Memory limit: 1024 MB

# Problem Statement

Call a positive integer sorted in base $b$ if its base-$b$ digits appear in non-decreasing order. For example, 1223 is sorted in base 10, 132 or 120 are not.

It has been shown that there are infinitely many integers $n$ such that both $n$ and $n^2$ are sorted in base $b$ if and only if $b - 1$ is divisible by a nontrivial square (though I can’t track down the source). Therefore, fortunately, when $b = 10$ therefore infinitely many integers such that both $n$ and $n^2$ are sorted in base 10.

The problem: given $X$ as an input, output number of integers $n \in \{1, \ldots, X\}$ such that both $n$ and $n^2$ are sorted in base 10.

# Input

The first line is a positive integer, the number of test cases $T \le 10^5$. There are $T$ more lines, each contains a positive integer $X \le 10^{18}$.

# Output

For each test case, output a line containing the result.

# Sample Input #1
```
3
5
8
13
```
# Sample Output #1
```
5
7
9
```

Sample inputs:
3
5
8
13

Sample outputs:
5
7
9

# Solution Analysis

The intended solution is to precompute all numbers that satisfy the condition in advance by iterating all $\le \sum_{i=1}^{18} \binom{i+9}{9}$ sorted numbers and checking their squares, then (optionally) hard code all the numbers in the source code and process each query in $\mathcal{O}(1)$. Python or `__int128` is needed to avoid overflow.

As a side note, I am unable to track down the source or the proof of the claim. However, the book “Unsolved Problems in Number Theory” by Richard Guy has the following

> If the digits of a number are monotonic, as in 24779, call it sorted. John Guilford & John Hamilton have proved the equivalence of “$b - 1$ is divisible by a square” and “there are infinitely many integers $n$ such that the base-$b$ digits of both $n$ and $n^2$ are sorted”. So base 10 admits infinitely many solutions. In fact Hamilton can find infinitely many $n$ such that $n$, $n^2$, $n^3$, $\ldots$, $n^m$ are all sorted in base $b$ provided $b - 1$ is divisible by an $m$-th power.

OEIS sequence: https://oeis.org/A234841

**A234841**  
*Integers n such that digits in n and n² are in nondecreasing order.*  
0, 1, 2, 3, 4, 5, 6, 7, 12, 13, 15, 16, 17, 34, 35, 37, 38, 67, 116, 117, 167, 334, 335, 337, 367, 667, 1667, 3334, 3335, 3337, 3367, 3667, 6667, 16667, 33334, 33335, 33337, 33367, 33667, 36667, 66667, 166667, 333334, 333335, 333337, 333367, 333667, 336667

I’m unable to prove the pattern continues indefinitely. Thanks to huajun for suggesting bumping the limit to $10^{18}$.


Special judge (C++ scorer):