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

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

}

}

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

#### PHP Warning

lib/DbaDatabase.php:154: Warning: dba_optimize() [<a href='function.dba-optimize'>function.dba-optimize</a>]: You cannot perform a modification to a database without proper access

lib/DbaDatabase.php:134: Warning: dba_replace() [<a href='function.dba-replace'>function.dba-replace</a>]: You cannot perform a modification to a database without proper access