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.

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: