Author |
Topic: Pythagorean Triplet Efficiency (Read 1157 times) |
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
    
 
Gender: 
Posts: 767
|
 |
Pythagorean Triplet Efficiency
« on: Apr 15th, 2004, 8:39am » |
 Quote  Modify
|
Devise an algorithm to calculate Pythagorean triplets that maximizes time efficiency and disregards space (you do not need to store the results, just calculate them). What is the O() notation for this algorithm?
Edit: I did not define the problem correctly. Given an integer upper bound x, find all triplets where all three numbers are less than or equal to x.
|
| « Last Edit: Apr 15th, 2004, 9:30am by John_Gaughan » |
 IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Pythagorean Triplet Efficiency
« Reply #1 on: Apr 15th, 2004, 8:54am » |
Quote Modify
|
::
for(int r=0; r++; r< maxr)
for(int s=0; s++; s< maxs)
{
m1 = m2 = n3 = r*r+rs+s*s;
n1 = r*r-s*s;
n2 = 2*r*s+s*s;
m3 = r*r+2*r*s
cout << triple(m1*m1-n1*n1, 2*m1*n1, m1*m1+n1*n1)
<< triple(m2*m2-n2*n2, 2*m2*n2, m2*m2+n2*n2)
<< triple(m3*m3-n3*n3, 2*m3*n3, m3*m3+n3*n3)
<<endl;
}
time complexity O(n), where n is the number of triplets
::
|
| « Last Edit: Apr 15th, 2004, 8:54am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: Pythagorean Triplet Efficiency
« Reply #2 on: Apr 15th, 2004, 9:26am » |
Quote Modify
|
where do you get maxr and maxs?
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Pythagorean Triplet Efficiency
« Reply #3 on: Apr 15th, 2004, 10:55am » |
Quote Modify
|
They could be given as arguments, or simply be defined as MAX_INT, or anything really. You could leave r as 0, and let s count to infinity if you want (though your computer won't actually do that)
Any natural number r and s should give a triplet of Pythagorean triangles of equal area.. Unless I misread mathworld on the subject 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: Pythagorean Triplet Efficiency
« Reply #4 on: Apr 15th, 2004, 1:10pm » |
Quote Modify
|
Ah, so you were trying to get all of them. I went back and edited the problem, I screwed it up the first time. It is supposed to be bounded by an integer such that all the triplets' values are less than that integer, not to get n number of triplets.
The best I can get is O(n2)
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Pythagorean Triplet Efficiency
« Reply #5 on: Apr 15th, 2004, 1:16pm » |
Quote Modify
|
on Apr 15th, 2004, 1:10pm, John_Gaughan wrote:| Ah, so you were trying to get all of them. |
|
I wouldn't say that. I don't even know if all triplets are characterized by an r and s, I only know that infinitely many are..
If they have to be bounded by some number x, I think you can still get all of these in O(n), but there may be other triplets that slip through.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Pythagorean Triplet Efficiency
« Reply #6 on: Apr 16th, 2004, 12:29am » |
Quote Modify
|
on Apr 15th, 2004, 1:10pm, John_Gaughan wrote:| The best I can get is O(n2) |
|
What’s n in your notation?
As far as I know, every triplet is generated by the scheme (u2-v2, 2uv, u2+v2) for suitable choice of positive integers u > v. So, it’s clear that the set of required triplets is just { u2+v2 [le] x | 1 [le] v < u}. There are O(x) of these, and maybe easily generated as a double loop.
The things become a bit more complicated if only primitve triplets are considered.
|
| « Last Edit: Apr 16th, 2004, 12:39am by Barukh » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Pythagorean Triplet Efficiency
« Reply #7 on: Apr 16th, 2004, 1:04am » |
Quote Modify
|
on Apr 16th, 2004, 12:29am, Barukh wrote:| The things become a bit more complicated if only primitve triplets are considered. |
|
Only a wee bit, u and v then need to be relatively prime..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: Pythagorean Triplet Efficiency
« Reply #8 on: Apr 16th, 2004, 5:37am » |
Quote Modify
|
O(n2) means that it takes quadratic time to find all triplets lower than an arbitrary integer n
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Pythagorean Triplet Efficiency
« Reply #9 on: Apr 16th, 2004, 11:19am » |
Quote Modify
|
you can get O(n) because
v goes from 1 to [sqrt]n
u goes from 2 to [sqrt](n-v2)
This way you get all triples and only the triples with sides less than n.
|
|
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