| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 133.1 | | TURTLE::GILBERT | | Wed Aug 22 1984 23:26 | 13 |
| (1) If n = 2,3,5,6 or 8 (mod 9), then any decimal number containing only zeros
and ones, with exactly n ones, is not a perfect square.
(2) If n = 0,1,4 or 7 (mod 9), it should be possible to construct a perfect
square containg exactly n ones.
Proof of (1) is simple. A perfect square must equal either 0,1,4 or 7 (mod 9).
Any decimal number containing only zeros and ones, with exactly n ones, must
equal n (mod 9).
Statement (2) is just conjecture.
- Gilbert
|
| 133.2 | | TURTLE::GILBERT | | Fri Aug 24 1984 15:44 | 2 |
| Perhaps I was a bit too hasty with the conjecture. Can somone supply ANY
perfect squares containing only 1s and 0s (other than the trivial (10^n)^2) ?
|
| 133.3 | | HARE::STAN | | Sat Aug 25 1984 19:56 | 3 |
| I've checked all positive integers less than 10^12 consisting only of 0's
and 1's, and I found no perfect squares other than the obvious ones of
the form 100^k.
|
| 133.4 | | TURTLE::GILBERT | | Sat Aug 25 1984 20:49 | 29 |
| For the square of a number to end with a 1, the number must be of the form:
10x + 9 or 10x + 1
Squaring these gives:
2 2
100(x +1) + 10(8x+8) + 1 100x + 2x + 1
For these forms to end with two zeroes or ones, we must have:
x = 5y + 4 x = 5y
Continuing, we see that the number must be of the form:
250z + 249 or 250z + 1
This can be continued to aid in the search for such squares (or, possibly,
to show that there are none).
Note that a search may also be reduced by noting that either:
m m
10 <= n < 10 sqrt(10)/3
or
m m+1
10 sqrt(10) < n < 10 /3, for some integer m.
- Gilbert
|
| 133.5 | | HARE::STAN | | Mon Aug 27 1984 03:27 | 8 |
| Note that we need not concern ourselves with perfect squares
ending in 00, because if one existed, we could divide by 100
(a perfect square) and get a SMALLER perfect square. Thus, if we
want to prove that no non-trivial perfect squares of 0's and 1's
exist, we need only look at numbers ending in 01, 10, or 11.
But no perfect square can end in 10 or 11 (just look at the
perfect squares modulo 100). Thus we need only search for perfect
squares ending in 01.
|
| 133.6 | | HARE::STAN | | Mon Aug 27 1984 06:35 | 3 |
| Close, but no cigar:
375501^2 = 141001001001
|
| 133.7 | | HARE::STAN | | Mon Aug 27 1984 06:46 | 177 |
| A computationally more efficient way to look at the problem is this:
Suppose we want a number of n digits to have the property that when it is
squared, the last n digits of the result consists of only 0's and 1's.
There are only a finite number of cases to check. Then we can also
notice if the entire square happens to contain only 0's and 1's.
Each case builds up to cases with more digits. For example, the
rightmost digit must be 0, 1, or 9. Then there are only 10 choices
for each of the next digits. We can try all 10 choices for each of the
3 previously found numbers. Again, any time we find a "winner", we can
append another digit to its left to try to extend the length of the number.
We vary that new digit from 0 to 9. We keep extending until some maximum
size is met. In the following printout, the maximum size is 6 digits
and numbers ending in 0 are automatically excluded. Note that only
trivial "winners" were found. The SNOBOL4 program that produced this
output is included at the end. Also, the order that the numbers are
searched is slightly different than as described above.
01^2 = 1 <------- A winner!
001^2 = 1 <------- A winner!
0001^2 = 1 <------- A winner!
00001^2 = 1 <------- A winner!
000001^2 = 1 <------- A winner!
500001^2 = 250001000001
50001^2 = 2500100001
050001^2 = 2500100001
550001^2 = 302501100001
5001^2 = 25010001
05001^2 = 25010001
005001^2 = 25010001
505001^2 = 255026010001
55001^2 = 3025110001
055001^2 = 3025110001
555001^2 = 308026110001
501^2 = 251001
0501^2 = 251001
30501^2 = 930311001
430501^2 = 185331111001
930501^2 = 865832111001
80501^2 = 6480411001
380501^2 = 144781011001
880501^2 = 775282011001
5501^2 = 30261001
25501^2 = 650301001
425501^2 = 181051101001
925501^2 = 856552101001
75501^2 = 5700401001
375501^2 = 141001001001
875501^2 = 766502001001
51^2 = 2601
251^2 = 63001
4251^2 = 18071001
24251^2 = 588111001
024251^2 = 588111001
524251^2 = 274839111001
74251^2 = 5513211001
474251^2 = 224914011001
974251^2 = 949165011001
9251^2 = 85581001
19251^2 = 370601001
219251^2 = 48071001001
719251^2 = 517322001001
69251^2 = 4795701001
269251^2 = 72496101001
769251^2 = 591747101001
751^2 = 564001
3751^2 = 14070001
23751^2 = 564110001
023751^2 = 564110001
523751^2 = 274315110001
73751^2 = 5439210001
473751^2 = 224440010001
973751^2 = 948191010001
8751^2 = 76580001
18751^2 = 351600001
218751^2 = 47852000001
718751^2 = 516603000001
68751^2 = 4726700001
268751^2 = 72227100001
768751^2 = 590978100001
9^2 = 81
49^2 = 2401
249^2 = 62001
1249^2 = 1560001
31249^2 = 976500001
231249^2 = 53476100001
731249^2 = 534725100001
81249^2 = 6601400001
281249^2 = 79101000001
781249^2 = 610350000001
6249^2 = 39050001
26249^2 = 689010001
026249^2 = 689010001
526249^2 = 276938010001
76249^2 = 5813910001
476249^2 = 226813110001
976249^2 = 953062110001
749^2 = 561001
0749^2 = 561001
30749^2 = 945501001
230749^2 = 53245101001
730749^2 = 533994101001
80749^2 = 6520401001
280749^2 = 78820001001
780749^2 = 609569001001
5749^2 = 33051001
25749^2 = 663011001
025749^2 = 663011001
525749^2 = 276412011001
75749^2 = 5737911001
475749^2 = 226337111001
975749^2 = 952086111001
99^2 = 9801
499^2 = 249001
4499^2 = 20241001
24499^2 = 600201001
124499^2 = 15500001001
624499^2 = 389999001001
74499^2 = 5550101001
074499^2 = 5550101001
574499^2 = 330049101001
9499^2 = 90231001
19499^2 = 380211001
119499^2 = 14280011001
619499^2 = 383779011001
69499^2 = 4830111001
069499^2 = 4830111001
569499^2 = 324329111001
999^2 = 998001
4999^2 = 24990001
44999^2 = 2024910001
444999^2 = 198024110001
944999^2 = 893023110001
94999^2 = 9024810001
494999^2 = 245024010001
994999^2 = 990023010001
9999^2 = 99980001
49999^2 = 2499900001
449999^2 = 202499100001
949999^2 = 902498100001
99999^2 = 9999800001
499999^2 = 249999000001
999999^2 = 999998000001
* Program to find all n-digit numbers whose square has its last n digits
* consisting only of 0's and 1's.
*
&ANCHOR = 1
MAXSIZ = 6
NUM = '1'
*
* Append a 0 to the left of the current number.
*
LOOP NUM = '0' NUM
*
* Square the number.
*
AGAIN S = SIZE(NUM)
SQUARE = NUM * NUM
*
* Are the final S digits only 0's and 1's?
*
SQUARE (RTAB(S) | NULL) REM . FINAL
FINAL SPAN('01') RPOS(0) :F(BUMP)
WINNER =
SQUARE SPAN('01') RPOS(0) :F(OUT)
WINNER = ' <------- A winner!'
OUT OUTPUT = LPAD(NUM,MAXSIZ) '^2 = ' SQUARE WINNER
LT(S,MAXSIZ) :S(LOOP)
*
* Bump first digit. If it was 9, delete it.
*
BUMP NUM LEN(1) . DIG REM . REST
DIG = NE(DIG,9) DIG + 1 :F(DEL)
NUM = DIG REST :(AGAIN)
DEL NUM = REST
DIFFER(NUM) :S(BUMP)
END
|
| 133.8 | | HARE::STAN | | Mon Aug 27 1984 07:09 | 3 |
| Another close one:
300000050000001^2 = 90000030000003100000100000001
|
| 133.9 | | HARE::STAN | | Mon Aug 27 1984 16:53 | 26 |
| I've now tested every number up to 10^30 and found no non-trivial
perfect squares containing only 0's and 1's.
Here is a list of some of the "near calls", i.e. perfect squares
with lots of 0's and 1's:
500000000000001^2 = 250000000000001000000000000001
50000000000001^2 = 2500000000000100000000000001
550000000000001^2 = 302500000000001100000000000001
5000000000001^2 = 25000000000010000000000001
55000000000001^2 = 3025000000000110000000000001
500000000001^2 = 250000000001000000000001
5500000000001^2 = 30250000000011000000000001
50000000001^2 = 2500000000100000000001
550000000001^2 = 302500000001100000000001
5000000001^2 = 25000000010000000001
500000001^2 = 250000001000000001
50000001^2 = 2500000100000001
300000050000001^2 = 90000030000003100000100000001
3000005000001^2 = 9000030000031000010000001
375501^2 = 141001001001
281249^2 = 79101000001
14526249^2 = 211011910010001
155280749^2 = 24112111010001001
316529780749^2 = 100191102101010011001001
124499^2 = 15500001001
|
| 133.10 | | TURTLE::GILBERT | | Mon Aug 27 1984 23:37 | 19 |
| The smallest n that's undecided is n=4. Is there a perfect square with exactly
4 ones in it, and the remaining digits all zero?
The following approach may be useful.
Consider numbers modulo m. If y contains exactly 4 ones, and has a 1 as
the least significant digit, then y mod m = Set1. Also, x^2 mod m = Set2.
The intersection of these two sets gives a (fairly) small set of possible
values (modulo m) for x^2 = y. This set of numbers can be converted back
to direct restrictions on the x values.
Using m = 8 shows that x^2 mod 1000 = 1. Using m = 101 shows that
x mod 101 = 0,2,3,9,11,27,30,35,43,58,66,71,74,90,92,98, or 99.
Another approach is to solve the following for y, and hope that it offers ideas.
10^ 2a + 10^b + 10^c + 1 = (10^a + y)^2, 2a > b > c > 2
or 10^(2a+1) + 10^b + 10^c + 1 = (10^a + y)^2, 2a+1 > b > c > 2
|
| 133.11 | | HARE::STAN | | Sat Sep 01 1984 21:23 | 24 |
| I've now searched all numbers up through 10^36 and have found no perfect
squares of just 0's and 1's.
A few findings:
500000000000000001^2 = 250000000000000001000000000000000001
425501^2 = 181051101001
375501^2 = 141001001001
10050375501^2 = 101010047711101001001
4251^2 = 18071001
43474251^2 = 1890010500011001
31624218751^2 = 1000091211611100000001
16768751^2 = 281191010100001
281249^2 = 79101000001
781249^2 = 610350000001
14526249^2 = 211011910010001
155280749^2 = 24112111010001001
284780749^2 = 81100075001001001
316529780749^2 = 100191102101010011001001
1025749^2 = 1052161011001
38975749^2 = 1519109010111001
24499^2 = 600201001
124499^2 = 15500001001
244949999^2 = 60000502010100001
|