# effective way to get the integer sequence A181392 from oeis

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:

1. compute sequence A108571 and check if the number is a perfect square (use this topic)
2. 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?

-
There is a link to "source of generating exe", but unfortunately it is dead. – Hagen von Eitzen May 14 '13 at 19:31
this was my program which use a simple bruteforce checking all squares. – wieschoo May 14 '13 at 19:36
One slight speedup: The digit sum of any A108571 number is the sum of some of the numbers $1, 4, 9, 16, 25, 36, 49, 64, 81$ and at the same time determines $n\bmod 9$, which must be one of $0,1,4,7$. This rules out (only) half of all digit selections. – Hagen von Eitzen May 14 '13 at 19:43
Does the line "current rsults" imply I could still get merits by completing the sequemce? :) – Hagen von Eitzen May 14 '13 at 19:51
@zyx If I am not mistaken, you have created the oeis tag. It is discussed on meta whether this tag is needed. So I thought it might be a good idea to let you know about this. – Martin Sleziak Sep 10 '14 at 7:15

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