lotus

previous page: 383 pickover/pickover.07.p
  
page up: Puzzles FAQ
  
next page: 385 pickover/pickover.09.p

384 pickover/pickover.08.p




Description

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.

384 pickover/pickover.08.p


Title: Cliff Puzzle 8: Squares and Squares and Squares ....
From: cliff@watson.ibm.com

If you respond to this puzzle, if possible please send me your name,
address, affiliation, e-mail address, so I can properly credit you if
you provide unique information. PLEASE ALSO directly mail me a copy of
your response in addition to any responding you do in the newsgroup. I
will assume it is OK to describe your answer in any article or
publication I may write in the future, with attribution to you, unless
you state otherwise. Thanks, Cliff Pickover

* * *

1. What is the smallest square with leading digit 1 which remains a
square when the leading 1 is replaced by a 2?

In other words, if x**2 = 1.........., is there a y**2 = 2......... ?

2. What is the smallest square with leading digit 1 which remains a
square when the leading 1 is replaced by a 2 and also remains a square
when the leading digit is replaced by a 3?

3. What is the smallest square with leading digit 1 which remains a
square when the leading 1 is replaced by a 2, and also remains a square
when the leading digit is replaced by a 3, and also remains a square
when the leading digit is replaced by a 4?

pickover/pickover.08.s

-------------------------

> 1. What is the smallest square with leading digit 1 which remains a
> square when the leading 1 is replaced by a 2?
>
11025 ( 105 * 105 ) ---- 21025 ( 145 * 145 )

>
> 2. What is the smallest square with leading digit 1 which remains a
> square when the leading 1 is replaced by a 2 and also remains a square
> when the leading digit is replaced by a 3?
>
No solution till 1,000,000,000.

> 3. What is the smallest square with leading digit 1 which remains a
> square when the leading 1 is replaced by a 2, and also remains a square
> when the leading digit is replaced by a 3, and also remains a square
> when the leading digit is replaced by a 4?
>
>
No solution till 1,000,000,000.

The property that you are looking for ( however with different leading

digits ) is owned by the following numbers.

2025    3025
-------------
11025   21025
57600   67600
---------------
202500   302500
342225   442225
------------------
1102500   2102500
3515625   4515625
5760000   6760000
-------------------
11390625   21390625
20250000   30250000
34222500   44222500
----------------------
110250000     210250000
196700625     296700625
351562500     451562500
576000000     676000000
-------------------------

This is probably of no use to you, but, anyway.

-------------------------

In article <1992Oct20.184149.51596@watson.ibm.com> you write:
>Title: Cliff Puzzle 8: Squares and Squares and Squares ....
>1. What is the smallest square with leading digit 1 which remains a
>square when the leading 1 is replaced by a 2?

>In other words, if x**2 = 1.........., is there a y**2 = 2......... ?

(Isn't this first part an old puzzle?)

105^2=11025; 145^2=21025. In general we want 10^k=(y-x)(y+x) and
1.5 < (y/x)^2 < 2. Thus y+x and y-x must be factors of 10^k of
the same parity whose ratio is between 5.828... and 9.899...
(these are (t+1)/(t-1) for t^2=2 and 1.5 respectively). The
smallest solution (x,y)=(105,145) corresponds to the factorization
10^4=40*250; gp/pari's "fordiv" function allows one to easily list
all primitive solutions [i.e. not obtained from a smaller solution
by multiplying x,y by the same power of 10] with x^2 and y^2 each
having at most (say) 50 digits:

[x,y]=

[145, 105]
[17225, 14025]
[454625, 326625]
[53948125, 43708125]
[1425503125, 1015903125]
[168971890625, 136203890625]
[529265958203125, 424408358203125]
[1657888279384765625, 1322343959384765625]
[5193483785077392578125, 4119741961077392578125]

In fact it can be seen that the primitive solutions correspond to
integer linear combinations of log(2) and log(5) lying in a certain
fixed interval (determined by the bounds 5.828... and 9.899...),
which probably explains the regular growth of this list.

>2. What is the smallest square with leading digit 1 which remains a
>square when the leading 1 is replaced by a 2 and also remains a square
>when the leading digit is replaced by a 3?

There is no such beast, since the three squares would constitute an
arithmetic progression of integer squares of common difference 10^k,
and so give an A.P. of 3 rational squares of common difference 1 or 10 ---
which is known to be impossible by a "2-descent" argument (the case of
common difference 1 is already due to Fermat). [We were lucky here:
in a different number system this argument might fail; for instance the
squares of 7/2, 17/2, 23/2 are an A.P. of common difference 60, the
sexagesimal base. (Some numerology: 7,17,23 are the first three primes
of which 2 is a quadratic residue.) Still, given the base b, the general
theory of elliptic curves indicates that the rational solutions of
Y^2-X^2=Z^2-X^2=b are rather sparsely distributed (the number of d-digit
solutions growing as some power of d), and the extra condition that they
arise by changing only the initial digits of three integer squares is
strong enough to ensure that there are at most finitely many solutions;
with yet more powerful methods one can even provably list them all.]

>3. What is the smallest square with leading digit 1 which remains a
>square when the leading 1 is replaced by a 2, and also remains a square
>when the leading digit is replaced by a 3, and also remains a square
>when the leading digit is replaced by a 4?

Of course the above solution to part 2 also disposes of this part;
alternatively I could apeal to another classic result of Fermat:
there is no 4-term A.P. of rational squares.

My question: why all the blank spaces at the end of every line?

--Noam D. Elkies (elkies@zariski.harvard.edu)
Dept. of Math., Harvard Univ., Cambridge, MA 02138
-------------------------

I dunno the direct answer to your squares problem. I do know,
however, that phi (from the Golden Ratio--approx 0.61), which is
defined as the number x such that x + 1 = x^2. It just so happens
that phi+1 and (phi+1)^2 differ by only 1. (1.61 and 2.61) The
rest of the digits are the SAME! Phi = (Sqrt(5)-1)/2.

Phi+1 = (Sqrt(5)+1)/2 phi+2 = (Sqrt(5)+3)/2
(Phi+1)^2= (5+2*Sqrt(5)*1+1)/4 = (2*Sqrt(x)+6)/4 = (Sqrt(x) + 3)/2

Notice how that all works out? Perhaps this property will bring you
closer to an answer. I just sent you all my personal data in
a previous letter concerning your 123 problem. Let me know
what you think of this approach, ok? Thanks in advance!

--Joseph Zbiciak im14u2c@camelot.bradley.edu

-------------------------

In article <1992Oct20.184149.51596@watson.ibm.com> you write:
: 2. What is the smallest square with leading digit 1 which remains a
: square when the leading 1 is replaced by a 2 and also remains a square
: when the leading digit is replaced by a 3?

This is not possible. One of these numbers would leave a remainder
of 2 when divided by 3, and no square is congruent to 2 modulo 3.

--
David Radcliffe
radcliff@csd4.csd.uwm.edu
-------------------------

In article <1992Oct20.184149.51596@watson.ibm.com> you write:
: 1. What is the smallest square with leading digit 1 which remains a
: square when the leading 1 is replaced by a 2?

11025. I found, by hand, all integral solutions to
(x+y)(x-y) = 10000. The solution (145,105) is the only
one with 10000 < y^2 < 20000.

You have permission to use my solution, but not my name.

--
David Radcliffe
radcliff@csd4.csd.uwm.edu
-------------------------

Well, as a previous poster already mentioned on Rec.puzzles, there are only 4
solutions to the initial problem. They are 192, 219, 293, and 327. None of
these solutions can be connected to others as in part 2 of your problem.

I first extended the problem to allow any multipliers. So the second row must
be some multiple of the first and the third some other multiple of the first.
I found 19 solutions to this problem. However, there is still no way to chain
a second solution to the first.

Then I allowed 0s. Now there are 134 solutions. There are also 17 2-chains.
There are two 3-chains which I will list here:

    192     394
*2= 384 *3=1182
*3= 576 *4=1576
*7=4032  now the same as the other solution.
*9=5184
*4= 736
*5= 920

I will be more than happy to send you all 134 solutions if you really want
them! I also have Pascal source code.

Comments on some of your other problems will follow.

Dan Cory
Senior, Stanford

perm. address:
55 Cedar St.
Chapel Hill, NC 27514

school address:
PO Box 13113
Stanford, CA 94309

Should you use any of my results, please send a copy of the work to the
permanent address above.
-------------------------

In article <1992Oct20.184149.51596@watson.ibm.com>, you write:
|> Title: Cliff Puzzle 8: Squares and Squares and Squares ....
|> 1. What is the smallest square with leading digit 1 which remains a
|> square when the leading 1 is replaced by a 2?

11025 = 105^2, 21025 = 145^2.

|> 2. What is the smallest square with leading digit 1 which remains a
|> square when the leading 1 is replaced by a 2 and also remains a square
|> when the leading digit is replaced by a 3?
|>
|> 3. What is the smallest square with leading digit 1 which remains a
|> square when the leading 1 is replaced by a 2, and also remains a square
|> when the leading digit is replaced by a 3, and also remains a square
|> when the leading digit is replaced by a 4?

These two cases never occur.

Proof: (This was a LOT harder than I thought it would be when I started!)
The original problem can be reduced to:
"Find positive integers x,y,n such that
y^2-x^2 = 10^n and 10^n < x^2 < 2*10^n." [1]

The second problem amounts to finding x,y,z,n which meet the above
conditions, plus z^2-y^2=10^n.

For the second problem, look at the set of solutions to
z^2-y^2 = 10^n, 2*10^n < y^2 < 3*10^n. [2]

A solution to the second problem consists of x,y,z,n, where x,y,n solve
the original problem and y,z,n solve the above system.

The first equation in [1] can be factored into (y-x)(y+x) = 10^n = 2^n * 5^n.
Similarly (z-y)(z+y) = 10^n. Since x,y,z are integers, we must have
y+x = 2^a * 5^b, y-x = 2^(n-a) * 5^(n-b)
z+y = 2^c * 5^d, z-y = 2^(n-c) * 5^(n-d)
where a,b,c,d are integers. When a=c and b=d, y+x = z+y and y-x = z-y,
which leads to a contradiction.

Then 2y = 2^a * 5^b + 2^(n-a) * 5^(n-b) = 2^c * 5^d + 2^(n-c) * 5^(n-d)
However, in the last equality above, divide both sides by 2^f, where f is
the smallest of a, c, n-a, and n-c. The result is:

2^(a-f) * 5^b + 2^(n-a-f) * 5^(n-b) = 2^(c-f) * 5^d + 2^(n-c-f) * 5^(n-d) [3]

Now, at least one of the four products above is a product of only 5's, and
is odd.  Only one is odd unless a=c, 2a=n, or 2c=n.
    If a=c, then either b=d (contradiction) or z+y is at least
  a factor of 5 larger than y+x.  However, considering
    sqrt(3)*sqrt(10^n) < z < 2*sqrt(10^n)
    sqrt(2)*sqrt(10^n) < y < sqrt(3)*sqrt(10^n)
	    sqrt(10^n) < x < sqrt(2)*sqrt(10^n)
  we have:
    (sqrt(3)+sqrt(2))*sqrt(10^n) < z+y <       (2+sqrt(3))*sqrt(10^n)
	  (1+sqrt(2))*sqrt(10^n) < y+x < (sqrt(3)+sqrt(2))*sqrt(10^n)
  and then (z+y)/(y+x) < (2+sqrt(3))/(1+sqrt(2)) < 5.
    If a exactly equals n/2:
  In the case that b=a=n/2, y+x = y-x, so x=0 (not possible).
  If b<n/2, y-x>y+x, but we want x to be positive, so b>n/2.  Since b and
  n/2 are integers (remember n/2=a), b-(n-b) >= 2, and (y+x)/(y-x) >= 25.
  This gives     (y+x) >= 25(y-x),
	(y+x+y-x) = 2y >= 26(y-x),
		     y >= 13y-13x,
		   13x >= 12y,
		   x/y >= 12/13
	       x^2/y^2 >= 144/169

However, we know 10^n < x^2 < 2*10^n, and y^2 = x^2 + 10^n, so x^2/y^2
varies between 1/2 and 2/3, and cannot be greater than 144/169.
Similarly, when c=n/2, the same argument applies, and in the final step
we know y^2/z^2 varies between 2/3 and 3/4.
Finally, we've eliminated all cases where more than one of the terms in [3]
is odd. With exactly one term odd, we have odd=even, a contradiction,
so there is no solution.

--
----w-w--------------Joseph  De Vincentis--jwd2@owlnet.rice.edu----------------
   ( ^ )   Disclaimer: My opinions do not represent those of Owlnet.
   (O O)   Owlnet: George R. Brown School of Engineering Educational Network.
    v-v    (Unauthorized use is prohibited.)  (Being uwop-ap!sdn is allowed.)
-------------------------

G'day Cliff!

> * * *
>
> 1. What is the smallest square with leading digit 1 which remains a
> square when the leading 1 is replaced by a 2?
>
> In other words, if x**2 = 1.........., is there a y**2 = 2......... ?

The smallest I could find was 105**2 = 11025
145**2 = 21025

Indeed, an exhaustive search shows that this is the smallest.

The other pairs I found (after a few minutes playing with pen and paper - I
could probably write a program to generate them ad nauseum, but I've got a
draft thesis to write...) were:

    3375**2 = 11390625,       4625**2 = 21390625
   14025**2 = 196700625,     17225**2 = 296700625
  326625**2 = 106683890625, 454625**2 = 206683890625

I don't know what pattern there is in them. Of course, if x is a solution,
then so is 10*x. So these give solutions for 1050*1050 = 1102500, etc.

> 2. What is the smallest square with leading digit 1 which remains a
> square when the leading 1 is replaced by a 2 and also remains a square
> when the leading digit is replaced by a 3?
>
> 3. What is the smallest square with leading digit 1 which remains a
> square when the leading 1 is replaced by a 2, and also remains a square
> when the leading digit is replaced by a 3, and also remains a square
> when the leading digit is replaced by a 4?

I'll answer part 3 first. If such a square exists, then observe that we have
4 squares in arithmetic progression (common difference a power of 10). There
is a well known theorem that there is no set of four squares in arithmetic
progression, so there is no solution to part 3.

Now, for part 2. We have 3 squares in arithmetic progression. Another well
known (and not too hard to derive) theorem states that for three squares in
arithmetic progression, their common difference is of the form:

D = 4 * K^2 * m * n * (m^2 - n^2) = 4 * K^2 * m * n * (m + n) * (m - n)

Now, this value is a power of 10. So the only primes in its factorisation are
2 and 5. Hence neither m nor n is divisible by 3. So (m^2 - n^2) is
divisible by 3. Hence a power of 10 is divisible by 3. Contradiction. So
now such set of three squares exist (which also proves part 3).

Cheers,
Geoff.

PS: I assume you still have whatever details of mine you care about.

-------------------------------------------------------------------------------
Geoff Bailey (Fred the Wonder Worm)   |   Programmer by trade --
ftww@cs.su.oz.au                      |       Gameplayer by vocation.
-------------------------------------------------------------------------------

-------------------------

Here is the solution I just posted to rec.puzzles. Note that I changed my mind
on this puzzle!

Dan Cory
Senior, Stanford
PO Box 13113
Stanford, CA 94309
ypay@leland.stanford.edu

Newsgroups: rec.puzzles
Subject: Re: Cliff Puzzle 8: Squares and Squares ... (SPOILER)
Approved: news-answers-request@MIT.Edu
Summary: solutions to part 1, no solutions to parts 2 or 3
Expires:
Sender:
Followup-To:
Distribution:
Keywords: squares, cliff, 8, gcd

In article <1992Oct20.184149.51596@watson.ibm.com> cliff@watson.ibm.com (cliff)
>1. What is the smallest square with leading digit 1 which remains a
>square when the leading 1 is replaced by a 2?
>In other words, if x**2 = 1.........., is there a y**2 = 2......... ?

We write this condition as the following equations with x,y,a integers:
y^2-x^2=10^a
1*10^a<=x^2<=2*10^a
2*10^a<=y^2<=3*10^a
We factor the first equation:
(y-x)(y+x)=10^a.
Let u=x+y. Then 10^a/u=x-y. Since x+y>x-y, u>10^a/u so u>10^(a/2)
Then x=(u-10^a/u)/2 and y=(u+10^a/u)/2.

Subsitute these equations into the inequalities above.
For x we get:
10^a<=((u-10^a/u)/2)^2<=2*10^a
Take the square root of both (all three?) sides:
10^(a/2)<=(u-10^a/u)/2<=sqrt(2)*10^(a/2)
Multiply through by 2 and divide through by 10^(a/2).
2<=u/10^(a/2)-10^(a/2)/u<=2*sqrt(2)
Let v=u/10^(a/2). So v>1. Then:
2<=v-1/v<=2*sqrt(2).

We solve these two inequalities. First the left:
v-1/v>=2
v^2-2v-1>=0
v>=(1+sqrt(2)) or v<=(1-sqrt(2)).
v-1/v<=2*sqrt(2)
v>=(sqrt(2)+sqrt(3)) or v<=(sqrt(2)-sqrt(3)).
Since v>1, we drop the negative solutions and find:
1+sqrt(2) <= v <= sqrt(2)+sqrt(3).
or
1+sqrt(2) <= u/10^(a/2) <= sqrt(2)+sqrt(3).

We can do the same for y but we will find the same restriction on u.

Now we remember that u|10^a (u divides 10^a). Therefore u must be a power of
2 times a power of 5. Let u=5^b*2^c with b,c integers less than or equal to a.
Since we are going to divide it by 2, we must have c>=1.
Then we need to find a,b,c such that:
1+sqrt(2) <= 5^b*2^c/10^(a/2) <= sqrt(2)+sqrt(3)
These will give us u which will in turn determine x and y.
So take the log base 10 of all three sides. Since log is increasing, we do not
change the direction of inequality. Thus:
log(1+sqrt(2)) <= b*log(5)+c*log(2)-a/2 <= log(sqrt(2)+sqrt(3))
Multiply through by 2:
2*log(1+sqrt(2)) <= 2*b*log(5)+2*c*log(2)-a <= 2*log(sqrt(2)+sqrt(3))

If we approximate log(5) and log(2), this is sort of a Diophantine equation.
Since log(5) is very very close to 0.7 and log(2) is very very close to 0.3,
our approximations will be okay to find low solutions. If we want big solutions
then we need to use better convergents. We can calculate the boundary logs
as accurately as necessary. So:
0.77 <= 7/5*b+3/5*c-a <= 0.99
Multiply through by 5:
3.8 <= 7*b+3*c-5*a <= 4.9
So we must find a,b,c such that 7*b+3*c-5*a = 4, with a>b>=0 and a>=c>0.
There are many good ways to solve this but we will just pick a small solution.
b=3, c=1, a=4 (7*3+3-5*4=21+3-20=4)
Then u=5^3*2^1=250.
So y+x=250 and y-x=10^a/u=10^4/250=40.
Then y=145 and x=105.
y^2=21025 and x^2=11025.

This is, in fact, the smallest solution (it is easy to show that there is no
solution to the 7*b+3*c-5*a with a<4 and a>b>=0,a>=c>0).

>2. What is the smallest square with leading digit 1 which remains a
>square when the leading 1 is replaced by a 2 and also remains a square
>when the leading digit is replaced by a 3?

We note from above that y=(5^b*2^c+10^a/(5^b*2^c)/2 or
2y=5^b*2^c+5^(a-b)*2^(a-c).

Should we now repeat the problem for a square with leading digit 2 that is
replaced by a 3, everything is the same except that y is now the smaller of the
pair. Thus:
2y=5^B*2^C-5^(a-B)*2^(a-C)
where B and C are different from b and c above but a is necessarily the same
(since we want the difference to be the same power of 10 for each transition).

Combining the two we get:
5^b*5^c+5^(a-b)*2^(a-b)=5^B*2^C-5^(a-B)*2^(a-C).
The proof that this has no solutions is too small to fit in the margin of this
posting.

>3. What is the smallest square with leading digit 1 which remains a
>square when the leading 1 is replaced by a 2, and also remains a square
>when the leading digit is replaced by a 3, and also remains a square
>when the leading digit is replaced by a 4?
There is no solution since there is no solution to part 2.

Dan Cory

 

Continue to:













TOP
previous page: 383 pickover/pickover.07.p
  
page up: Puzzles FAQ
  
next page: 385 pickover/pickover.09.p