106 - Fermat vs. Pythagoras

[prilmeie]

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

[R]

roger! thx!

[Dominik Michniewski]

My Accepted solution gives that answer:

Code: Select all

78 101
144 182
168 219
1394 1474
13109 12308
121648 103370
103831 88566
159139 133926

Regards
Dominik MIchniewski

[minskcity]

I've just started to solve this problem, and according to example there are 4 triples for N = 25. I found following triples:

Code: Select all

3,4,5
5,12,13
7,24,25

Could you supply me with triple #4 for this case, and some more triple for N > 25.

[Dominik Michniewski]

That's no problem .... Making querys is very good way to win )

Dominik

[Red Scorpion]

To get the other triple :
->3, 4 ,5 ;
the other triple : 3*2, 4*2, 5*2
--------------------3*3, 4*3, 5*3
--------------------3*4, 4*4, 5*4
--------------------3*k, 4*k, 5*k (k=1...)
etc..

GOOD LUCK
RED SCORPION

[minskcity]

I actually need relatively prime triple... a*k,b*k,c*k are not relatively prime if k > 1...

[minskcity]

Thanks, it should help me a lot.

[amir2099]

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

[amir2099]

found my problem.

[rjhadley]

4 3 5
8 6 10
12 9 15 <- you're missing this one
16 12 20
20 15 25 <- you're also missing this one
12 5 13
8 15 17
24 7 25

[amir2099]

thank you for your reply, i found my problem already

btw, can you take a look at my post for 107 now ? lol

[Ryan Pai]

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^2-s^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)(z-x)

Since y is even, y^2 is divisible by 4. Also z+x and z-x 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 * (z-x)/2

Now (z+x)/2 and (z-x)/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=(z-x)/2 and you can get the equation at the top.

I hope this helps.

[capella]

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=p-q,p=p-q;

while(q!=1){
p=p-q;
if(p<q) p=p+q,q=p-q,p=p-q;
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<MAX-1;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*a-b*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]

[Ryan Pai]

This segment of code:

[cpp]
for(i=1;z*i<=n;i++){
seen[x*i]=1;
seen[y*i]=1;
seen[z*i]=1;
}
[/cpp]

runs each time you find any pythagorean triple. Also since 3,4,5 and all multiple of it are triples this will take at the order of (n/5)^2, which for a large value of n will time out.