106  Fermat vs. Pythagoras
Moderator: Board moderators
See also http://acm.uva.es/board/viewtopic.php?t=2085. My solution (the algorithm itself hasn't changed) uses this overflow checking functions.
My integer data containers are all of type int, so this should be a prove that you do not have to use data containers longer than a machine word itself. This is also a performance issue, as an addition of an integer longer than one machine word takes multiple assembler statements. So the additional effort checking if an overflow occured should take almost the same time as a long word addition. So there is an efficient solution which only uses native data types declared by ISO  C or C++.
Regards,
Franz
My integer data containers are all of type int, so this should be a prove that you do not have to use data containers longer than a machine word itself. This is also a performance issue, as an addition of an integer longer than one machine word takes multiple assembler statements. So the additional effort checking if an overflow occured should take almost the same time as a long word addition. So there is an efficient solution which only uses native data types declared by ISO  C or C++.
Regards,
Franz

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
My Accepted solution gives that answer:
Regards
Dominik MIchniewski
Code: Select all
78 101
144 182
168 219
1394 1474
13109 12308
121648 103370
103831 88566
159139 133926
Dominik MIchniewski
106  triples needed
I've just started to solve this problem, and according to example there are 4 triples for N = 25. I found following triples:
Could you supply me with triple #4 for this case, and some more triple for N > 25.
Code: Select all
3,4,5
5,12,13
7,24,25

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:

 Experienced poster
 Posts: 192
 Joined: Sat Nov 30, 2002 5:14 am
Trouble with 106
Hi, i believe that my algorithm works.
however, I was wondering if someone could tell me how many pythagorean triples there are between 1 and 25 (inclusive).
ie. my program says the following:
3 4 5
8 6 10
8 15 17
5 12 13
12 16 20
7 24 25
which seems reasonable. but, there are only 15 distinct digits there, which makes 10 numbers between 1 and 25 left which haven't been used.
but the sample data says 9
!?
thanks, amir
however, I was wondering if someone could tell me how many pythagorean triples there are between 1 and 25 (inclusive).
ie. my program says the following:
3 4 5
8 6 10
8 15 17
5 12 13
12 16 20
7 24 25
which seems reasonable. but, there are only 15 distinct digits there, which makes 10 numbers between 1 and 25 left which haven't been used.
but the sample data says 9
!?
thanks, amir

"my name is amir"
amir
"my name is amir"
amir
The real way to do this problem
The obvious solution to the problem is to iterate through all x,y,z combinations and check and see if they work.
Of course this takes n^3 time which is too long.
The easy optimization to see is that once you know two of the variables, you can calculate the third so it's only n^2 now. Of course this still takes too long.
The actual solution takes a little bit of number theory (And all of this is right out of The Theory of Numbers Niven, Zuckerman, Montgomery).
Assume that I give you two numbers r,s (for now imagine out of nowhere). Then you can verify this equation:
(r^2s^2)^2 + (2*r*s)^2 = (r^2+s^2)^2
So, given an r,s pair you can easily create a pythagorean triple. The difficult thing to see is that all of them can be genererated from them. Knowing this, its easy to see an algorithm that can create all the triples, since you only have to check all r,s < sqrt(n). So if you don't want to know the math behind it then you can quit reading right there.
Ok, so why does this generate all triples?
Well, lets assume that x,y,z is a triple which is relatively prime, so not both of x,y can be even. However, one of them must be (otherwize z would be divisible by 2 but not by 4) so assume without loss of generality that y is even and x,z are odd. Rewrite the equation as:
y^2 = (z+x)(zx)
Since y is even, y^2 is divisible by 4. Also z+x and zx are both divisible by 2 (adding/subtracting an odd to an odd). so we can further write it as:
(y/2)^2 = (z+x)/2 * (zx)/2
Now (z+x)/2 and (zx)/2 must be relatively prime (if they had a common factor then their sum[z] and their difference[x] would have a common factor).
So now were are in a situation where a square number (y/2)^2 is factored into two numbers which are relatively prime. It's easy to see that each of these numbers must themselves be squares (this delves into unique factorization theorems). Just set r^2 = (z+x)/2 and s^2=(zx)/2 and you can get the equation at the top.
I hope this helps.
Of course this takes n^3 time which is too long.
The easy optimization to see is that once you know two of the variables, you can calculate the third so it's only n^2 now. Of course this still takes too long.
The actual solution takes a little bit of number theory (And all of this is right out of The Theory of Numbers Niven, Zuckerman, Montgomery).
Assume that I give you two numbers r,s (for now imagine out of nowhere). Then you can verify this equation:
(r^2s^2)^2 + (2*r*s)^2 = (r^2+s^2)^2
So, given an r,s pair you can easily create a pythagorean triple. The difficult thing to see is that all of them can be genererated from them. Knowing this, its easy to see an algorithm that can create all the triples, since you only have to check all r,s < sqrt(n). So if you don't want to know the math behind it then you can quit reading right there.
Ok, so why does this generate all triples?
Well, lets assume that x,y,z is a triple which is relatively prime, so not both of x,y can be even. However, one of them must be (otherwize z would be divisible by 2 but not by 4) so assume without loss of generality that y is even and x,z are odd. Rewrite the equation as:
y^2 = (z+x)(zx)
Since y is even, y^2 is divisible by 4. Also z+x and zx are both divisible by 2 (adding/subtracting an odd to an odd). so we can further write it as:
(y/2)^2 = (z+x)/2 * (zx)/2
Now (z+x)/2 and (zx)/2 must be relatively prime (if they had a common factor then their sum[z] and their difference[x] would have a common factor).
So now were are in a situation where a square number (y/2)^2 is factored into two numbers which are relatively prime. It's easy to see that each of these numbers must themselves be squares (this delves into unique factorization theorems). Just set r^2 = (z+x)/2 and s^2=(zx)/2 and you can get the equation at the top.
I hope this helps.
help on 106, it works well on my comp, but I got TLE
This program runs quickly on my computer, but I continously get Time Limit Exceeded. It's weird. Can anyone help me try it on your computer?[cpp]
#include<iostream>
#define MAX 1000001
using namespace std;
int cop(int p, int q){
if(p%2==0 && q%2==0) return 0;
if(p<q) p=p+q,q=pq,p=pq;
while(q!=1){
p=pq;
if(p<q) p=p+q,q=pq,p=pq;
if(p==q) return 0;
}
return 1;
}
void main(){
int n;
int seen[MAX];
while(cin>>n){
int i;
int x,y,z;
int ct=0,ct2=0;
for(i=0;i<MAX1;i++)
seen=0;
for(int b=1;b*b<=n/2;b++)
for(int a=b+1;a*a+b*b<=n;a++){
x=a*ab*b;
y=2*a*b;
z=a*a+b*b;
for(i=1;z*i<=n;i++){
seen[x*i]=1;
seen[y*i]=1;
seen[z*i]=1;
}
if(cop(x,y) && cop(x,z) && cop(y,z))
ct++;
}
for(i=1;i<=n;i++)
if(!seen)
ct2++;
cout<<ct<<' '<<ct2<<endl;
}
}[/cpp][/cpp]
#include<iostream>
#define MAX 1000001
using namespace std;
int cop(int p, int q){
if(p%2==0 && q%2==0) return 0;
if(p<q) p=p+q,q=pq,p=pq;
while(q!=1){
p=pq;
if(p<q) p=p+q,q=pq,p=pq;
if(p==q) return 0;
}
return 1;
}
void main(){
int n;
int seen[MAX];
while(cin>>n){
int i;
int x,y,z;
int ct=0,ct2=0;
for(i=0;i<MAX1;i++)
seen=0;
for(int b=1;b*b<=n/2;b++)
for(int a=b+1;a*a+b*b<=n;a++){
x=a*ab*b;
y=2*a*b;
z=a*a+b*b;
for(i=1;z*i<=n;i++){
seen[x*i]=1;
seen[y*i]=1;
seen[z*i]=1;
}
if(cop(x,y) && cop(x,z) && cop(y,z))
ct++;
}
for(i=1;i<=n;i++)
if(!seen)
ct2++;
cout<<ct<<' '<<ct2<<endl;
}
}[/cpp][/cpp]