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?

  • $\begingroup$ There is a link to "source of generating exe", but unfortunately it is dead. $\endgroup$ May 14, 2013 at 19:31
  • $\begingroup$ this was my program which use a simple bruteforce checking all squares. $\endgroup$
    – wieschoo
    May 14, 2013 at 19:36
  • $\begingroup$ 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. $\endgroup$ May 14, 2013 at 19:43
  • $\begingroup$ Does the line "current rsults" imply I could still get merits by completing the sequemce? :) $\endgroup$ May 14, 2013 at 19:51
  • $\begingroup$ @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. $\endgroup$ Sep 10, 2014 at 7:15

1 Answer 1


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

  • $\begingroup$ Where exactly do you prune the search space? Hensel lifting lemma states that an odd perfect root must be a square mod 10 (and thus a square mod 2 and a square mod 5). But this only gives a necessary condition what the last three digits have to be? $\endgroup$
    – wieschoo
    May 16, 2013 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.