80 arithmetic/digits/squares/length.9.p
Description
This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.
80 arithmetic/digits/squares/length.9.p
Is it possible to make a number and its square, using the digits from 1
through 9 exactly once?
arithmetic/digits/squares/length.9.s
Yes, there are two such pairs: (567, 567^2=321489) and (854,854^2=729316).
1. ==> arithmetic/digits/squares/three.digits.p
What squares consist entirely of three digits (e.g., 1, 4, and 9)?
arithmetic/digits/squares/three.digits.s
The full set of solutions up to 10**12 is
1 -> 1
2 -> 4
3 -> 9
7 -> 49
12 -> 144
21 -> 441
38 -> 1444
107 -> 11449
212 -> 44944
31488 -> 9914 94144
70107 -> 49149 91449
3 87288 -> 14 99919 94944
956 10729 -> 9 14141 14499 11441
4466 53271 -> 199 49914 44949 99441
31487 17107 -> 9914 41941 99144 49449
2 10810 79479 -> 4 44411 91199 99149 11441
If the algorithm is used in the form I presented it before, generating
the whole set P_n before starting on P_{n+1}, the store requirements
begin to become embarassing. For n>8 I switched to a depth-first
strategy, generating all the elements in P_i (i=9..12) congruent to
a particular x in P_8 for each x in turn. This means the solutions
don't come out in any particular order, of course. CPU time was 16.2
seconds (IBM 3084).
In article <1990Feb6.025205.28153@sun.soe.clarkson.edu>, Steven
Stadnicki suggests alternate triples of digits, in particular {1,4,6}
(with many solutions) and {2,4,8} (with few). I ran my program on
these as well, up to 10**12 again:
1 -> 1
2 -> 4
4 -> 16
8 -> 64
12 -> 144
21 -> 441
38 -> 1444
108 -> 11664
119 -> 14161
121 -> 14641
129 -> 16641
204 -> 41616
408 -> 1 66464
804 -> 6 46416
2538 -> 64 41444
3408 -> 116 14464
6642 -> 441 16164
12908 -> 1666 16464
25771 -> 6641 44441
78196 -> 61146 14416
81619 -> 66616 61161
3 33858 -> 11 14611 64164
2040 00408 -> 41 61616 64641 66464
6681 64962 -> 446 44441 64444 61444
8131 18358 -> 661 16146 41166 16164
40182 85038 -> 16146 61464 66146 61444 (Steven's last soln.)
1 20068 50738 -> 1 44164 46464 46111 44644
1 26941 38988 -> 1 61141 16464 66616 64144
1 27069 43631 -> 1 61466 41644 14114 64161
4 01822 24262 -> 16 14611 14664 16614 44644
4 05784 63021 -> 16 46611 66114 66644 46441
78 51539 12392 -> 6164 66666 14446 44111 61664
and
2 -> 4
22 -> 484
168 -> 28224
478 -> 2 28484
2878 -> 82 82884 (Steven's last soln.)
2109 12978 -> 44 48428 42888 28484
(so the answer to Steven's "Are there any more at all?" is "Yes".)
The CPU times were 42.9 seconds for {1,4,6}, 18.7 for {2,4,8}. This
corresponds to an interesting point: the abundance of solutions for
{1,4,6} is associated with abnormally large sets P_n (|P_8| = 16088
for {1,4,6} compared to |P_8| = 5904 for {1,4,9}) but the deficiency
of solutions for {2,4,8} is *not* associated with small P_n's (|P_8|
= 6816 for {2,4,8}). Can anyone wave a hand convincingly to explain
why the solutions for {2,4,8} are so sparse?
I suspect we are now getting to the point where an improved algorithm
is called for. The time to determine all the n-digit solutions (i.e.
2n-digit squares) using this last-significant-digit-first is essentially
constant * 3**n. Dean Hickerson in <90036.134503HUL@PSUVM.BITNET>, and
Ilan Vardi in <1990Feb5.214249.22811@Neon.Stanford.EDU>, suggest using
a most-significant-digit-first strategy, based on the fact that the
first n digits of the square determine the (integral) square root; this
also has a running time constant * 3**n. Can one attack both ends at
once and do better?
Chris Thompson
JANET: cet1@uk.ac.cam.phx
Internet: cet1%phx.cam.ac.uk@nsfnet-relay.ac.uk
Hey guys, what about
648070211589107021 ^ 2 = 419994999149149944149149944191494441
This was found by David Applegate and myself (about 5 minutes on a DEC 3100,
program in C).
This is the largest square less than 10^42 with the 149-property; checking
took a bit more than an hour of CPU time.
As somebody suggested, we used a combined most-significant/least-significant
digits attack. First we make a table of p-digit prefixes (most significant
p digits) that could begin a root whose square has the 149 property in its
first p digits. We organize this table into buckets by the least
significant q digits of the prefixes. Then we enumerate the s digit
suffixes whose squares have the 149 property in their last s digits. For
each such suffix, we look in the table for those prefixes whose last q
digits match the first q of the suffix. For each match, we consider the p +
s - q digit number formed by overlapping the prefix and the suffix by q
digits. The squares of these overlap numbers must contain all the squares
with the 149 property.
The time expended is O(3^p) to generate the prefix table, O(3^s) to
enumerate the suffixes, and O(3^(p+s) / 10^q) to check the overlaps (being
very rough and ignoring the polynomial factors) By judiciously chosing p, q,
and s, we can fix things so that each bucket of the table has around O(1)
entries: set q = p log10(3). Setting p = s, we end up looking for squares
whose roots have n = 2 - log10(3) digits, with an algorithm that takes time
O( 3 ^ [n / (2 - log10(3)]) ), roughly time O(3^[.66n]). Compared to the
O(3^n) performance of either single-ended algorithm, this lets us check 50%
more digits in the same amount of time (ignoring polynomial factors). Of
course, the space cost of the combined-ends method is high.
-- Guy and Dave
--
Guy Jacobson School of Computer Science
Carnegie Mellon arpanet : guy@cs.cmu.edu
Pittsburgh, PA 15213 csnet : Guy.Jacobson%a.cs.cmu.edu@csnet-relay
(412) 268-3056 uucp : ...!{seismo, ucbvax, harvard}!cs.cmu.edu!guy
Here is an algorithm which takes O(sqrt(n)log(n)) steps to find all perfect
squares < n whose only digits are 1, 4 and 9.
This doesn't sound too great *but* it doesn't use a lot of memory and only
requires addition and <. Also, the actual run time will depend on where the
first non-{1,4,9} digit appears in each square.
set n = 1
set odd = 1
while(n < MAXVAL)
{
if(all digits of n are in {1,4,9})
{
print n
}
add 2 to odd
add odd to n
}
This works because (X+1)^2 - x^2 = 2x+1.
That is, if you start with 0 and add successive odd
numbers to it you get 0+1=1, 1+3=4, 4+5=9, 9+7=16 etc.
I've started the algorithm at 1 for convenience.
The "O" value comes from looking at at most all digits
(log(n)) of all perfect squares < n (sqrt(n) of them)
at most a constant number of times.
I didn't save the articles with algorithms claiming to be
O(3^log(n)) so I don't know if their calculations needed
to (or did) account for multiplication or sqrt() of large
numbers. O(3^log(n)) sounds reasonable so I'm going to
assume they did unless I hear otherwise.
Any comments? Please email if you just want to refresh my memory
on the other algorithms.
Andrew Charles
acgd@ihuxy.ATT.COMM
Continue to:
My Books
