wu :: forums - Print Page


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

        riddles >> cs >> When triangles are squares
        
(Message started by: towr on Oct 20^th, 2002, 1:17pm)

Title: When triangles are squares
Post by towr on Oct 20^th, 2002, 1:17pm

problem: Make an algorithm that runs in linear time which can find all pairs x,y (both integer > 0) so that x(x+1)/2 == y^2

It's a problem arising from looking at triangles and squares (made from circles) and trying to find when they're equal in surfacearea (measured in circles)

It's an easy problem.. Though finding a linear solution makes it sufficiently harder to make it interesting =)

Title: Re: NEW PROBLEM: When triangles are squares
Post by Pietro K.C. on Oct 20^th, 2002, 2:51pm

I don't get it... linear in terms of what? What is the input parameter? If there are an infinite number of such pairs, an algorithm to find ALL of them would run forever; if there is only a finite number, the algorithm would take constant time! :)

Title: Re: NEW PROBLEM: When triangles are squares
Post by TimMann on Oct 20^th, 2002, 7:30pm

I would think it's supposed to be either linear in the size of x or linear in the number of pairs found. That is, either finding all pairs with x < N should be O(N), or finding the first n pairs should be O(n). Which is it, towr?

p.s. I have an algorithm that's O(N^1/2). That's either better than requested or not good enough... :)

Title: Re: NEW PROBLEM: When triangles are squares
Post by towr on Oct 21^st, 2002, 1:20am

It's linear in terms of number of answers..

So 1000 pairs takes about 10 times as long as 100 pairs.. (actually if you find x then y is trivial to find, so you don't even need to find a whole pair)

Title: Re: NEW PROBLEM: When triangles are squares
Post by S. Owen on Oct 21^st, 2002, 2:19pm

I have a result and algorithm that I spotted purely by inspection and luck, though I don't know why it works. Anyone care to tell me why?

The first two pairs are of course (1,1) and (8,6).

You can compute y in the n^th pair (call it y_n) from the previous two y's. y_n = (y_n-1²-1) / y_n-2. I don't see why just yet, but it appears to hold:
(1,1)
(8,6)
(49,35)
(288,204)
(1681,1189)
(9800,6930)
...

Title: Re: NEW PROBLEM: When triangles are squares
Post by TimMann on Oct 22^nd, 2002, 1:30am

Nice, that's a lot farther than I got.

I managed to do enough analysis to know that either x or x+1 must be an odd square, which forms the basis for an O(N^1/2) algorithm. That's fast enough to quickly compute some example values, but I didn't spot the pattern SOwen did, and I don't yet see why the pattern holds either.

I read something about Diophantine equations of degree greater than 1 recently, but I can't remember where...

Title: Re: NEW PROBLEM: When triangles are squares
Post by towr on Oct 22^nd, 2002, 6:21am

S. Owen did indeed find my answer.. [edit](well almost anyway, I just use y_n-1^{^2}/y_n-2 and an extra constant. It also works for x but with another constant, but same factor. dunno which is better)[/edit] And I also don't know why it works.. But, it does seem to work in some variant for all ax^2+bx+c = dy^2 + ey +d

I found the square-triangle solution half a dozen years ago or so.. And more recently I was working with a hexagonal field and found a similar relation (one solution is a side 8 hexagon and a side 13 square and of course 1,1).. I have no idea how to prove it is mathematicly sound though..

Title: Re: NEW PROBLEM: When triangles are squares
Post by TimMann on Oct 22^nd, 2002, 9:36pm

It turns out there's a page on this problem at MathWorld. See
http://mathworld.wolfram.com/SquareTriangularNumber.html, and be sure to follow the link to "Pell equation" too.