[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

1189.0. "digits of N^2 are all 1, 4, or 9." by AITG::DERAMO (Dan D'Eramo, nice person) Tue Feb 06 1990 20:26

	There is an interesting problem going around the usenet:

	For which positive integers N do all of the digits of the
	base ten representation of N^2 come from {1, 4, 9}?  Are
	there finitely many or infinitely many such N?  How can
	you save hours of CPU time by thinking a little bit before
	searching for such N?  :-)

	Dan

	(sample N follow ... go to the next note if you do not wish
	to see them)

	Sample N:     N			N^2
		----------	-------------------
			 1			  1
			 2			  4
			 3			  9
			 7			 49
			12			144
			21			441
			38		       1444
		     .			.
		     .			.
		     .			.
		 446653271	 199499144494999441
		3148717107	9914419419914449449

	Should I have left out the three dots in the above table?
	Should I have placed three dots between the last two examples? :-)
T.RTitleUserPersonal
Name
DateLines
1189.1first dots are necessaryUTRUST::DEHARTOG925Wed Feb 07 1990 08:115
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).
1189.24GL::GILBERTOwnership ObligatesWed Feb 07 1990 14:2118
>	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.
1189.3... and another thing ...VMSDEV::HALLYBThe Smart Money was on GoliathWed Feb 07 1990 17:1715
    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
1189.4dubiousAKQJ10::YARBROUGHI prefer PiWed Feb 07 1990 17:389
>  ... 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 
1189.5Some data and some nonsense...SSDEVO::LARYunder the Big Western SkyThu Feb 08 1990 17:2835
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 
1189.6more restrictions on NUTRUST::DEHARTOG925Thu Feb 08 1990 18:167
.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?).
1189.7648070211589107021 ^ 2 = 419994999149149944149149944191494441AITG::DERAMODan D'Eramo, nice personThu Feb 15 1990 23:4057
	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