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

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Re: 106 - Wrong Examples?

cthompson wrote:I am working on problem 106, the program seems to work correctly, except my output is different to the sample output.

input:
10
25
100

my output:
1 4
4 9
36 27

sample output:
1 4
4 9
16 27

I tailored the program to print out all the hits to see why I counted 36 and the sample counted only 16. After looking through all of them, I could see no valid reason, does anyone have any insight?
Read the problem description carefully. The first integer for each output line is the number of relatively prime triples. For example, 3,4,5 are relatively prime or coprime, but 6,8,10 are not. And did you double count the triples? You can also take a look at this website: http://rle-vlsi.mit.edu/people/gjcoram/triples.html It has a list of relatively prime triples, where the first number in each triple is < 400. Hope this helps.

Gaolious
New poster
Posts: 28
Joined: Mon Nov 04, 2002 8:03 pm
Location: South Korea, Seoul
Contact:

I know,

x = r^2 - s^2
y = 2 * r * s
z = r^2 + s^2

x^2 = (r^2 - s^2)^2 = r^4 - 2*r^2*s^2 + s^4
y^2 = (2 * r * s)^2 = 4*r^2*s^2

x^2 + y^2 = r^4 + 2*r^2*s^2 + s^4 = (r^2+s^2)^2 = z^2

and i think r, s range is ,

3 <= x < y < z <= n

or

3 <= y < x < z <= n

3 <= r^2 - s^2 , 2 * r * s < r^2+s^2 <= n

so,

range of r is 1<= r < sqrt(n)
range of s is

under = max (r^2 - 3, 0);
upper = min (n/(2*r), r-1);

Code: Select all

limitR = (int)sqrt(n);

for (r = limitR ; r>=1 ; r-- )
{
under = max (r^2 - 3, 0);
upper = min (n/(2*r), r-1);

for ( s = under ; s <= upper; s++)
{
x = r*r - s*s ;
y = 2*r*s;
z = r*r + s*s ;
if ( x*x+y*y == z*z && x>0 && y>0 && z>0 && z<=n )
{

if ( ( !check[x-1] || !check[y-1] || !check[z-1] ) && ( gcd(x,y) || gcd(y,z) || gcd(x,z)) )
{
for (k=1 ; k*z <=n ; k++)
{
check[ x*k - 1 ] = 1 ;
check[ y*k - 1 ] = 1 ;
check[ z*k - 1 ] = 1 ;
}
count ++;
}
}
}
}

Code: Select all

int gcd( int x, int y )
{
if ( x > y ) swap(x,y);

while ( x > 0 )
{
y %= x;
swap(x,y);
}

return ( y == 1 ) ;
}
and gcd code is

this code gives correct ouputs in case n<=100 but, n is over then 1000 gives incorrect outputs. maybe incorrect outputs between 100, 1000 ..

please give me outputs in case n>= 500 or 1000 ..

ps. the outputs of this code
• 1
0 1
10
1 4
100
16 27
1000
156 207
10000
1526 1765
100000
14912 16627
1000000
146039 160508
500
79 110
600
93 131
700
110 147
800
126 166
900
138 183
ps. it's same outputs in limitR = sqrt(n)+1, under=1 and upper=r

pentium8
New poster
Posts: 1
Joined: Mon May 24, 2004 6:53 am
Contact:
I don't know
It's too difficult~ chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
Try using unsigned long (this is equivalent to a 64 bit integer).

NothingElse
New poster
Posts: 2
Joined: Thu Jun 10, 2004 6:02 pm
Contact:

Is there any idea to save time of running problem 106?

My source code has just been accepted, but it took at least 6.3s for running. What I did was:

firstly, I created array to save all relative prime triples ( the number of triples is less than 200000 )

secondly, I read the required number and checked on the array that how many triples which satified the fact that its components are less than or equal the required number.

thirdly, I generated all numbers which can be in any triple which its components are less than or equal required number and I counted which is not used.

That's what I had done. Anybody has some idea to improve?

Thanks a lot.
Nothing to Lose

Chocobo
New poster
Posts: 2
Joined: Sat Jul 24, 2004 5:25 am

Re: Problem Fermat vs. Pythagoras(106) - the second number

How do you find all triples?
If you can find all triples include not relatively primes(e.g 6,8,10),
(the second number)=N-(the number of all triples)

i hope there are some useful for you... my English is not well... chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
Chocobo, your method is ok, but I think there is another way.

Use an array to mark out numbers used in all triples in the given range, maintaining the count of numbers that are not marked as in a triple. The final count you obtain is the second number.

Using C++ or Java, use a bool(C++) or boolean array. In C, a simple int array is sufficient.

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:
Chocobo said:
(the second number)=N-(the number of all triples)
This is not true. Let's take a really easy example, N=5.

The number of all triples with x<y<z and x^2 + y^2 = z^2 is
1 (the only one is 3,4,5). Your method would say then that there are
N - 1 = 5 - 1 = 4 numbers not appearing in triples when the correct

It's not even safe to say N-num_triples*3 since some numbers might appear in more than one triple.

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:
Ryan Pai wrote:
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...
Doesn't this only prove that the method generates all relatively prime triples? How do you deal with counting the number of numbers <=N that don't appear in any triple at all? (even the ones that aren't relatively prime).

 Woops, I see now..all non-coprime triples are scalar multiples of coprime ones. Cool. [/Edit]

New poster
Posts: 3
Joined: Tue Sep 03, 2002 3:31 am
this therem does not generate ALL the triples, it generates ALL the relativy prime triples and SOME triples that are not relativy prime.

so you shoud generate all other not relativy prime triples from relativy prime for calculating the number of numbers that are not in any triple.

if you program good the two while cycles it will work. I still don't know why my program is slow, this therem is very "fast", but the program run 8 sec.

good luck

palespower
New poster
Posts: 6
Joined: Fri Aug 15, 2003 9:12 am
I guess. u have a mistake in defining the limits of s....

variable under should be always 1
and variable upper should be min(sqrt(N-r*r), r-1)

Try those modifications .. I hope this helps

palespower
New poster
Posts: 6
Joined: Fri Aug 15, 2003 9:12 am

Help Pleeease... . WA 106 -- Fermat vs. Pythagoras

Hello guys ... my code for this program solves it correctly.. including the 1000000 but the online judge is insisting on giving me a wrong answer... I guess there is something wrong with how to end the program.. like the eof thingy.. so can anybody check it for me.. show me the way to do it please...

[cpp]
#include <iostream>
#include <cmath>

using namespace std;

bool check(long, long, long);

inline long minim(long a, long b) {
return a<b?a:b;
}

inline bool gcd( long x, long y )
{
long temp;
if ( x > y ) temp = x, x = y, y = temp;

while ( x > 0 )
{
y %= x;
temp = x;
x = y;
y = temp;
}

return ( y == 1 ) ;
}

void main() {
long a, b, x, y, z;
long N, i, limit, under;
long count_triple, count;

while (!cin.eof()) {
cin >> N;
if (N<1) break;

bool *triples = new bool[N];
count_triple = 0;
count = 0;
limit = (long)sqrt(N);
for (a = limit; a > 1; a--) {
under = minim((long)sqrt(N-(a*a)),a-1);
for (b = under; b >= 1; b--) {
x = a*a - b*b;
y = 2*a*b;
z = a*a + b*b;

if(check(x,y,z)) count_triple++;

for (i = 1; i*z <= N; i++) {
triples[x*i-1] = false;
triples[y*i-1] = false;
triples[z*i-1] = false;
}
}
}

for (a = 0; a <N; a++) {
if (triples[a]) count++;
}

cout << count_triple << " " << count << endl;

delete [] triples;
}
}

bool check(long x, long y, long z) {
if (gcd(x,y) || gcd(x,z) || gcd(y,z))
return true;
return false;
}

[/cpp]

dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am
Your code doesn't even succeed on the sample input.

input:

Code: Select all

10
25
100

Code: Select all

1 0
4 1
16 0
16 0
correct output:

Code: Select all

1 4
4 9
16 27
For starters you process the last input twice since you check cin.eof() before your cin >> N; statement.
Try changing it to:

Code: Select all

//while (!cin.eof()) {
//cin >> N;
while (cin >> N) {
I'm not even going to look at the rest of your code, but obviously something is wrong there too.

Good luck

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

test data

Some sample data from an ACC program.

INPUT

Code: Select all

1
2
3
4
5
6
7
8
9
10
11
12
15
20
22
50
55
80
100
500
600
700
800
900
1000
10000
100000
1000000

OUTPUT

Code: Select all

0 1
0 2
0 2
0 2
1 2
1 3
1 4
1 5
1 6
1 4
1 5
1 6
2 5
3 7
3 9
7 15
8 14
12 22
16 27
80 107
95 127
112 142
128 162
140 180
158 205
1593 1669
15919 14844
159139 133926

I hope it will be useful for someone.

Callosciurus
New poster
Posts: 4
Joined: Tue Jul 19, 2005 6:32 pm

test data output

Hi Sedefcho,

I do not understand the output of the acc program above. Please help me to understand it!

For an input

Code: Select all

1
2
3
4
5
6
7
the output is

Code: Select all

0 1
0 2
0 2
0 2
1 2
1 3
1 4
My problem concerns the second number of the output. We know that pythagorian triples 3,4,5 and 6,8,10 exist. The second value of the output is the number of values p, 1 <= p <= N, that are not part of any such triple. So for N = 2..5 an output of two is correct if we consider the first triple 3,4,5. But what about N=6? Why is the output 3, since 6 is part of the next triple? The same for N=7.

Alright, on the other hand one might interpret the second value as the number of values p, 1 <= p <= N, that are not part of any triple x,y,z that can be constructed of values <=N. In that case the output for N=6,7 seems reasonable, but the values for N = 2..5 are not clear to me.

I appreciate any help,
Thanks!