From: cet1@cus.cam.ac.uk (Chris Thompson)
Newsgroups: sci.math
Subject: Re: Bi-digit Squares (base 10)
Date: 1 Apr 1995 23:39:58 GMT
Keywords: Squares, composed of two unique digits

In article <3lcl0p$1i5s@coyote.csusm.edu>, randall@coyote.csusm.edu (Randall Rathbun)
writes:
|> Has anyone done any more research into bi-digit squares, or those composed
|> of two unique digits? A computer search quickly located the following
|> non-trivial ones...
|>                           n  n^2
|>                           4  16
|>                           5  25
[snip]
|>                         264  69696
|>                        3114  9696996
|>                       81619  6661661161
|> 
|>        (n=100,200,300,1000,2000,3000,.. etc. are considered trivial)

I would count n=10,20,30 as "trivial" as well.

|> are there any others? If so, the square must have more than 15 digits if it
|> does exist. Squares composed of three digits seem much more common.
|> If anyone has found additional results, could you please post? 

We had a long thread involving squares whose digits were in {1,4,9} a few
years ago. I will dig it out my archives if you are interested.

The "natural heuristic hypothesis" if you are looking for squares whose
representation in base b has digits in a set A, |A| = a, is that there
will be finitely many if a < \sqrt{b} and infinitely many if a > \sqrt{b},
because there are a^n candidates less than b^n with a "probability" of
being square around b^{-n/2}. One has to eliminate parametric solutions
like your {1,4,9}.10^{2m} to make this work, of course. (There are less
trivial parametric solutions for a=3,b=10: consider for example 38^2,
338^2, 3338^2, ...). 

For a=2, b=10 the solutions die out pretty rapidly, and it seems very
likely that 81619^2 is the largest. The fun with a=3, b=10 is that 
although one expects the solutions to die out, they do so very slowly,
as (9/10)^m goes only slowly to zero. Although some extremely large
squares with A={1,4,9}, b=10 were found, I don't think we ever got to
the point were the "expected" number of larger ones was < 1 !

AFAIK, there are absolutely no non-trivial theoretical results in this area.

Computationally, one can improve on brute force search, of course.
Suppose b and A are given, and we are looking for n-digit squares. One
can work from the high-order end: after choosing n/2 digits, the square
root of the potential square is completely determined, and we just square
it and check whether the remaining digits are in A or not. Or one can
work from the low-order end, working out the possible square roots mod
b^{n/2} of various n/2-digit endings, squaring them, and checking the
resulting top halves. Either of these methods takes time about a^{n/2}.
By working from *both* ends, one can reduce this to a^{n/3}: I never 
did get round to programming this, although others did, and got the
largest solutions that way.

Chris Thompson
Internet: cet1@cus.cam.ac.uk
JANET:    cet1@uk.ac.cam.cus