Author |
Topic: When triangles are squares (Read 2037 times) |
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
 |
When triangles are squares
« on: Oct 20th, 2002, 1:17pm » |
 Quote  Modify
|
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 =)
|
| « Last Edit: Nov 7th, 2002, 10:29am by towr » |
 IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Pietro K.C.
Full Member
 
Gender:
Posts: 213
|
|
Re: NEW PROBLEM: When triangles are squares
« Reply #1 on: Oct 20th, 2002, 2:51pm » |
Quote Modify
|
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! 
|
| « Last Edit: Oct 20th, 2002, 4:44pm by Pietro K.C. » |
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PROBLEM: When triangles are squares
« Reply #2 on: Oct 20th, 2002, 7:30pm » |
Quote Modify
|
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(N1/2). That's either better than requested or not good enough...
|
| « Last Edit: Oct 20th, 2002, 7:36pm by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: NEW PROBLEM: When triangles are squares
« Reply #3 on: Oct 21st, 2002, 1:20am » |
Quote Modify
|
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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: NEW PROBLEM: When triangles are squares
« Reply #4 on: Oct 21st, 2002, 2:19pm » |
Quote Modify
|
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 nth pair (call it yn) from the previous two y's. yn = (yn-12-1) / yn-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)
...
|
|
IP Logged |
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PROBLEM: When triangles are squares
« Reply #5 on: Oct 22nd, 2002, 1:30am » |
Quote Modify
|
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(N1/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...
|
|
IP Logged |
http://tim-mann.org/
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: NEW PROBLEM: When triangles are squares
« Reply #6 on: Oct 22nd, 2002, 6:21am » |
Quote Modify
|
S. Owen did indeed find my answer.. [edit](well almost anyway, I just use yn-1^2/yn-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..
|
| « Last Edit: Oct 22nd, 2002, 6:33am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print