Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
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? –  wieschoo May 16 '13 at 16:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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