the sequence A181392 are perfect squares and any digit in the sequence says "I am part of an integer in which you'll find d digits "d"" (see A108571, How can we call them? "digit-valid"?)
How to get all these number in sequence A108571? This is maybe (hopefully) more a theoretical problem instead of using brute-force. I know two approaches:
- compute sequence A108571 and check if the number is a perfect square (use this topic)
- test every perfect square if it has the correct "format"
The first one seems to be very slow (there are many numbers in A108571= multinom.coeff. (45,9,8,7,6,5,4,3,2,1)). Of course we can create a suffixset containing the last 5 digits numbers of any squares, and put digits before the suffix such that the number is in sequence A108571, permute the all digits except the last 5 digits and test whether it is a perfect square.
The second approach has the advantage that there are "only" $\sqrt{999999999888888887777777666666555554444333221}$ numbers to test.
Are there some theorems I can use? Hensel's lemma gives me a statement about the three last digits of every odd square. So it would be more effective to use store the last 5 digits and start from there.
Is there another tricky theorem or statement I can use?
Define a string of nonzero digits to be $n$-consistent if when read in base 10, for all $1 \leq d \leq 9$ it has at most $d$ digits equal to $d$ and is congruent to a square mod $10^n$.
Build a tree whose root is the empty string and whose edges represent extensions of a $k$-consistent number to a $(k+1)$-consistent number, recording square integers (in A181392) as they appear. The tree can be built depth-first and fully explored branches deleted. It is useful to keep track of the powers of $2$ and $5$ dividing each number and maybe the part prime to $10$, and probably also to have computed the nontrivial 2-adic square roots of 1 to mod $2^{45}$ precision.
Some thought may be needed on how to do the mod $10^k$ liftings using the base 10 representation without recomputing in base $2$ and $5$.