106 - Fermat vs. Pythagoras

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

prilmeie
New poster
Posts: 13
Joined: Fri Jan 03, 2003 2:21 pm
Location: Germany
Contact:

Post by prilmeie » Thu Jan 16, 2003 1:27 pm

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

Post by R » Thu Jan 16, 2003 1:35 pm

roger! thx! 8)

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

Post by Dominik Michniewski » Mon Feb 10, 2003 9:28 am

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

Post by minskcity » Mon Feb 10, 2003 7:32 pm

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:

Post by Dominik Michniewski » Tue Feb 11, 2003 8:48 am

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

Post by Red Scorpion » Tue Feb 11, 2003 9:50 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 :lol:

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Tue Feb 11, 2003 7:34 pm

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

Post by minskcity » Tue Feb 11, 2003 7:45 pm

Thanks, it should help me a lot. :)

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

Trouble with 106

Post by amir2099 » Thu Jun 05, 2003 10:26 pm

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
Location: Canada
Contact:

Post by amir2099 » Fri Jun 06, 2003 4:04 am

found my problem.
-------------------------------------------
"my name is amir"
-amir

rjhadley
Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States

Post by rjhadley » Fri Jun 06, 2003 4:28 am

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
Location: Canada
Contact:

Post by amir2099 » Fri Jun 06, 2003 5:00 am

thank you for your reply, i found my problem already :)

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

Post by Ryan Pai » Fri Jul 04, 2003 10:26 am

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

Post by capella » Fri Jul 04, 2003 10:20 pm

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:

Post by Ryan Pai » Sat Jul 05, 2003 7:00 am

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.

Post Reply

Return to “Volume 1 (100-199)”