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

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

Re: 106 - Wrong Examples?

Post by chunyi81 » Wed Apr 28, 2004 4:39 pm

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:

Please Help me.. Problem 106

Post by Gaolious » Fri May 21, 2004 7:58 am

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:

Post by pentium8 » Mon May 24, 2004 6:56 am

I don't know
It's too difficult~ :cry:

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

Post by chunyi81 » Mon May 24, 2004 10:51 am

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?

Post by NothingElse » Mon Jul 12, 2004 2:27 pm

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

Post by Chocobo » Thu Jul 29, 2004 8:52 am

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... :wink:
my English is not well... :cry:

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

Post by chunyi81 » Thu Jul 29, 2004 10:35 am

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:

Post by Minilek » Mon Aug 02, 2004 2:35 pm

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
answer is 2.

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:

Post by Minilek » Mon Aug 02, 2004 2:48 pm

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).

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

Sasko
New poster
Posts: 3
Joined: Tue Sep 03, 2002 3:31 am

Post by Sasko » Sat Aug 28, 2004 11:19 pm

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

Post by palespower » Fri Sep 24, 2004 5:39 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

Post by palespower » Fri Sep 24, 2004 6:01 am

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]

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Sun Oct 03, 2004 3:28 pm

Your code doesn't even succeed on the sample input.

input:

Code: Select all

10
25
100
your output:

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

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

test data

Post by Sedefcho » Sun Jun 26, 2005 9:31 pm

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

Post by Callosciurus » Tue Jul 19, 2005 7:12 pm

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!

Post Reply

Return to “Volume 1 (100-199)”