Conference rusure::math

The dots are necessary: 1,2,3,7,12,21,38,107,212,31488,70107,387288...
as I found after a few hours cpu_time (its cheaper, we've so many idle
cycles lying around).
My thinking doesn't give any clues (yet). However, I suspect that N's
rightmost digit can never be a 9 (although N^2 ends with a 1).

>	How can you save hours of CPU time by thinking a little bit before
>	searching for such N?  :-)

	The last digit of N must be 1, 2, 3, 7, 8, or 9.  The last two digits
	must be 07, 12, 21, 29, 38, 43, 57, 62, 71, 79, 88, or 93.  To find
	what the last three digits must be, prefix the above two-digit numbers
	with another digit, square that, and examine the last three digits
	of the result.

	Note that there are 12 two-digit possibilities.  I'd expect there
	to be about 12 x 3 three-digit numbers, since prefixing with another
	digit yields 12 x 10 possibilities, and the {1,4,9} requirement
	on the squared number should prune all but 3/10 of these.  After
	some checking, I found that there are actually 32 three-digit
	numbers that fit the bill.

	By this technique, there should be only about 12x3^8, or under 79,000
	ten-digit numbers to test.

    If N(i) is the i-th such number satisying "N^2 digits are 1,4,9"
    then does:
    		 oo
    		----      1
    		 \	-----
    		 /	 N(i)
    		----
    		 i=1
    
    converge?  (Assuming there are infinitely many, otherwise the problem
    is a bit boring).
    
    Can Peter's "3/10 rule" in .2 come into play here?
    
      John

>  ... I suspect that N's
rightmost digit can never be a 9 (although N^2 ends with a 1).

I see no reason in principle why 9 shouldn't work. 
317979^2 = 101110644441 and
50915324229^2 = 2592370241344194444441 
have a lot of the right digits in them.

Lynn 

The number of right-hand digit endings which yield numbers of the proper
form (right-hand digits equal to 1, 4, or 9) are, according to a Q&D C program:

	Digits		Candidates
	------		----------
	1		6
	2		12
	3		28 (discrepancy with .2 here)
	4		80
	5		224
	6		672
	7		1968
	8		5904

The only number I found not mentioned earlier is 95610729^2=9141411499911441.

The number of candidates (as well as the run time of the program that finds
them) goes up as approximately 3^(number of digits) or, even more approximately,
SQRT(N) where N is the highest number you try to square.

If you completely ignore any subtle number-theoretic properties of the integers
(after all, we're all engineers here) and look at the problem statistically, in
the range [10^(N-1),10^N) there are 3^N numbers with all digits in {1,4,9}. The
spacing between perfect squares in the range varies between 2*S^(N-1) and
2*S^N, where S = SQRT(10), so the "expected number" of N-digit squares of the
right form is between (S/2)*(3/S)^N and (3/S)^N. Summing these numbers you get
a (slowly) converging geometric series, so the total number of these special
squares "should" be finite. Certainly the rapid falloff in good numbers up to
10^16 would indicate this as well.

If you add "6" to the set of legal digits, the number of legal squares appears
to increase (though not monotonically) with the number of digits, at least up
to 10^12, which is as far as I looked; the sequence is (starting with single
digit squares): 3,3,5,1,9,3,7,11,17,18,23,16,...
							Richie 

.5 wakes me up from the dream that N can not end with a 9.
But here's another (easy to see) property which might help
in constraining the N's: N can not start with a 5 or an 8
(because N^2 then starts with 2 or 3 and 6 or 7 respectively).
Going further in this direction (i.e. from left to right),
one comes to the conclusion that if N starts with a 7, then
N should start with 70x, where x is smaller then 8 (or 7?).

	The technique in reply .2 is what I first thought of and
	was the first non brute force method discussed on the usenet.
	Someone else then suggested finding those n-1 and n digit
	sequences of 1's, 4's, and 9's that were the first half of
	the squares of n digit numbers.  Unfortunately I purged my
	copy of the earlier articles.  A newer article combined the
	two methods as advised:

Path: shlump.nac.dec.com!decuac!haven!aplcen!uakari.primate.wisc.edu!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!tut.cis.ohio-state.edu!pt.cs.cmu.edu!SHERLOCK.PC.CS.CMU.EDU!guy
From: guy@SHERLOCK.PC.CS.CMU.EDU (Guy Jacobson)
Newsgroups: rec.puzzles,sci.math,sci.math.symbolic
Subject: Problem12 (squares with {1,4,9})
Message-ID: <7987@pt.cs.cmu.edu>
Date: 14 Feb 90 21:08:42 GMT
Organization: Carnegie-Mellon University, CS/RI
Lines: 39
Xref: shlump.nac.dec.com rec.puzzles:5331 sci.math:9826 sci.math.symbolic:1182
 
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