## 106 - Fermat vs. Pythagoras

Moderator: Board moderators

prilmeie
New poster
Posts: 13
Joined: Fri Jan 03, 2003 2:21 pm
Location: Germany
Contact:
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
New poster
Posts: 18
Joined: Wed Jan 15, 2003 4:35 pm
roger! thx!

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

### 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:

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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
That's no problem .... Making querys is very good way to win )

Dominik
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
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
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
I actually need relatively prime triple... a*k,b*k,c*k are not relatively prime if k > 1...

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
Thanks, it should help me a lot.

amir2099
New poster
Posts: 10
Joined: Sun Jun 01, 2003 7:52 pm
Contact:

### 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
-------------------------------------------
"my name is amir"
-amir

amir2099
New poster
Posts: 10
Joined: Sun Jun 01, 2003 7:52 pm
Contact:
found my problem.
-------------------------------------------
"my name is amir"
-amir

Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States
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
New poster
Posts: 10
Joined: Sun Jun 01, 2003 7:52 pm
Contact:

btw, can you take a look at my post for 107 now ? lol
-------------------------------------------
"my name is amir"
-amir

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

### 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^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
New poster
Posts: 5
Joined: Thu Jun 19, 2003 6:22 am

### 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=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
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:
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.