wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Concatenated Squares
        
(Message started by: THUDandBLUNDER on Jan 13th, 2004, 7:32am)
Title: Concatenated Squares
Post by THUDandBLUNDER on Jan 13th, 2004, 7:32am
Find two four-digit numbers A,B such that when they are concatenated they form an eight-digit number N equal to A2 + B2, as in the simpler example below.

122 + 332 = 1233

(Numbers with leading zeros are inadmissible.)
Title: Re: Concatenated Squares
Post by towr on Jan 13th, 2004, 11:16am
::[hide]
first analyze the problem a bit
a^2+b^2=10000*a + b
a^2 -10000a + b^2-b = 0
a = (5000+-sqrt(25000000-b^2+b))))

and by trying out b's between 1000 and 5000
we find a=9412 b=2353
[/hide]::
Title: Re: Concatenated Squares
Post by Quetzycoatl on Jan 13th, 2004, 11:23am
::[hide] 9412, 2353 [/hide]::

Dagnabit Towr, I just noticed you snuck your answer in before mine. Anyway I got mine the same way you did.
Title: Re: Concatenated Squares
Post by THUDandBLUNDER on Jan 13th, 2004, 5:25pm

on 01/13/04 at 11:16:37, towr wrote:
we find.....

In fact, brute force is not required on this one.

Let 10000A + B = A2 + B2

Multiplying by 4 and completing the square,
(2A - 10000)2 + (2B - 1)2 = 1 + 100002 = 17*5882353

As both prime factors are of the form 4n+1, we can express them as the sum of two squares.
17 = 12 + 42 = x2 + y2 (say)
5882353 = 5882 + 23532 = z2 + w2 (say)

(x2 + y2)(z2 + w2) = (xz - yw)2 + (xw + yz)2
or
(x2 + y2)(z2 + w2) = (xz + yw)2 + (xw - yz)2

The first identity yields nothing interesting.
The second gives 47052 + 88242

So
2A - 10000 =  [smiley=pm.gif]8824
and
2B - 1 =  [smiley=pm.gif]4705

Hence
A = 9412 (588 is inadmissible)
B = 2353
N = 94122353
Title: Re: Concatenated Squares
Post by towr on Jan 14th, 2004, 12:21am

on 01/13/04 at 17:25:18, THUDandBLUNDER wrote:
In fact, brute force is not required on this one.
It's not like I tried to match any 1000<=B<=9999 to any 1000<=A<=9999 , So it's not that brute..

Yours is a nice solution. But I don't really see how I could have found it, unless I knew about it beforehand.. At least not without using a lot more time, or some luck (which I never have).

And how did you find

Quote:
5882353 = 5882 + 23532 = z2 + w2 (say)
?
(interesting how that second square is B squared..)
Title: Re: Concatenated Squares
Post by THUDandBLUNDER on Jan 15th, 2004, 3:28am

Quote:
And how did you find...

I used the function FactorInteger in Mathematica. FactorInteger[5882353, GaussianIntegers -> True]
(I guess that's also brute force.) I don't think there's an analytical method, as opposed to an algorithm, for finding two squares which when added equal a given prime of the form 4n+1.


Quote:
(interesting how that second square is B squared..)

Do you mean it's interesting that one of the factors (5882353) of 1000001 happens to feature in the answer? Yes, it is.

I looked at some smaller numbers.

10A + B = A2 + B2
(2A - 100)2 - (2B - 1)2 = 1 + 102 = 101
As 101 is prime we can conclude that there are no numbers such that 10A + B = A2 + B2
(except A = 10, B = 1)

===========================================

100A + B = A2 + B2

(2A - 100)2 + (2B - 1)2 = 1 + 1002 = 11*13*17

13 = 22 + 32
17 = 12 + 42

We get
A = 12 or 88
B = 33
N = 1233 or 8833

=========================================

1000A + B = A2 + B2

(2A - 1000)2 + (2B - 1)2 = 1 + 10002 = 101*9901

101 = 12 = 102
9901 = 102 + 992

We get
A = 990
B = 100
N = 990100



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board