Help: Pythagorean Triples

Printable View

12-25-2010, 02:00 AM
mchahal22

1 Attachment(s)

Help: Pythagorean Triples

SOLVED. THANKS TO EVERYONE THAT HELPED.
when i set the max to 500, which is what i need to compute to, the program leaves out triples such as 3,4,5 and 5,12,13, but when i set the max to a smaller number such as 50, it includes those triples. i dont get whats wrong. and also, the order goes from least "a" to greatest "a" and i would like it to go from least hypotenuse("c") to greatest. plz help. i use blue j to write the code/make the programs. i included a screenshot of the code too.

Code:

import javax.swing.JOptionPane; public class C5_17 { public static void main() { int max=500; for (int a=1;a<=max;a++) { for (int b=1;b<=max;b++) { for (int c=1;c<=max;c++) { if ((a*a)+(b*b)==(c*c)) if(a<b) System.out.println(a+" "+b+" "+c); } } } } }
12-25-2010, 02:12 AM
Eranga

What's the smallest value that you've tried?
12-25-2010, 02:38 AM
al_Marshy_1981

your code is either miles away or you choose not to post it, cannot make head or tails what you you are at from that snippet
12-25-2010, 03:43 AM
JavaHater

i changed

Code:

public static void main()

to

Code:

public static void main(String[] args)

and ran the program. I can see 3 4 5 and 5 12 13. So what's really wrong?
12-25-2010, 11:32 AM
JosAH

The OP's algorithm runs in O(n^3) where n == the maximum value for each of the three component numbers. This can be done much cheaper; a well know theory states that all Pythagorean triple can be generated by using the numbers n > m; the triple (n*n-m*m, 2*m*n, n*n+m*m) is a Pythagorean triple. Also the non-coprime triples are generated, i.e. if (a, b, c) is a PT then (n*a, n*b, n*c) for n > 1 is also a PT. The triples are not generated in increasing order of the hypothenuse but a small Comparable<PT> implementation can cure that. This is a little class for Pythagorean Triples:

Code:

class PT implements Comparable<PT> { private int a, b, c; public PT(int a, int b, int c) { if (b < a) { int t= a; a= b; b= t; } this.a= a; this.b= b; this.c= c; } public String toString() { return "("+a+", "+b+", "+c+")"; } public int compareTo(PT that) { if (this.c != that.c) return this.c-that.c; if (this.b != that.b) return this.b-that.b; return this.a-that.a; } }

A PT object assumes that c >= a and c >= b; it takes care that b >= a. The generation of all PTs isn'nt difficult either:

Code:

SortedSet<PT> ptSet= new TreeSet<PT>(); for (int m= 1; m <= max; m++) for (int n= m+1; n <= max; n++) ptSet.add(new PT(n*n-m*m, 2*n*m, n*n+m*m)); for (PT pt : ptSet) System.out.println(pt);

kind regards,

Jos
12-25-2010, 07:00 PM
mchahal22

Quote:

Originally Posted by JavaHater

i changed

Code:

public static void main()

to

Code:

public static void main(String[] args)

and ran the program. I can see 3 4 5 and 5 12 13. So what's really wrong?

this is my output

232 435 493
234 312 390
237 316 395
238 240 338
240 252 348
240 275 365
240 320 400
240 364 436
240 418 482
243 324 405
246 328 410
249 332 415
252 275 373
252 336 420
252 405 477
255 340 425
255 396 471
258 344 430
260 273 377
260 288 388
261 348 435
261 380 461
264 315 411
264 352 440
266 312 410
267 356 445
270 360 450
273 364 455
276 368 460
279 372 465
280 294 406
280 342 442
280 351 449
282 376 470
285 380 475
288 330 438
288 384 480
291 388 485
294 392 490
297 304 425
297 396 495
300 315 435
300 400 500
319 360 481
320 336 464
325 360 485
340 357 493
12-25-2010, 07:03 PM
mchahal22

Quote:

Originally Posted by JosAH

The OP's algorithm runs in O(n^3) where n == the maximum value for each of the three component numbers. This can be done much cheaper; a well know theory states that all Pythagorean triple can be generated by using the numbers n > m; the triple (n*n-m*m, 2*m*n, n*n+m*m) is a Pythagorean triple. Also the non-coprime triples are generated, i.e. if (a, b, c) is a PT then (n*a, n*b, n*c) for n > 1 is also a PT. The triples are not generated in increasing order of the hypothenuse but a small Comparable<PT> implementation can cure that. This is a little class for Pythagorean Triples:

Code:

class PT implements Comparable<PT> { private int a, b, c; public PT(int a, int b, int c) { if (b < a) { int t= a; a= b; b= t; } this.a= a; this.b= b; this.c= c; } public String toString() { return "("+a+", "+b+", "+c+")"; } public int compareTo(PT that) { if (this.c != that.c) return this.c-that.c; if (this.b != that.b) return this.b-that.b; return this.a-that.a; } }

A PT object assumes that c >= a and c >= b; it takes care that b >= a. The generation of all PTs isn'nt difficult either:

Code:

SortedSet<PT> ptSet= new TreeSet<PT>(); for (int m= 1; m <= max; m++) for (int n= m+1; n <= max; n++) ptSet.add(new PT(n*n-m*m, 2*n*m, n*n+m*m)); for (PT pt : ptSet) System.out.println(pt);

kind regards,

Jos

thats a lil too complex. im in a computer progaramming class in 10th grade and this is what i have to do

"(Pythagorean Triples) A right triangle can have sides whose lengths are all integers. The set
of three integer values for the lengths of the sides of a right triangle is called a Pythagorean triple. The
lengths of the three sides must satisfy the relationship that the sum of the squares of two of the sides
is equal to the square of the hypotenuse. Write an application to find all Pythagorean triples for
side1, side2 and the hypotenuse, all no larger than 500. Use a triple-nested for loop that tries
all possibilities. This method is an example of “brute force” computing. You will learn in more advanced
computer science courses that there are large numbers of interesting problems for which there
is no known algorithmic approach other than using sheer brute force."
12-25-2010, 07:56 PM
Zack

This might sound odd, but honestly I think that perhaps scrolling up might reveal the rest of the numbers. Running the code, just like for others, produces all numbers for me, and there is no logic in that program that will cut it off.

Perhaps your console output cuts off after so many bytes? I know that in the Python interpreter it cuts off after 16,384 characters (I think, it might be 32,768) so perhaps your output is just being lost.

To test my theory, change:
System.out.println(a+" "+b+" "+c);
...to:
if (a < 50) System.out.println(a+" "+b+" "+c);
...and see what the result is.
12-25-2010, 08:03 PM
JosAH

Quote:

Originally Posted by mchahal22

thats a lil too complex. im in a computer progaramming class in 10th grade and this is what i have to do

If the algoritm I presented is a little over your head keep it for later and see if you can appreciate the method then ...

kind regards,

Jos
12-26-2010, 02:37 AM
mchahal22

Quote:

Originally Posted by JosAH

If the algoritm I presented is a little over your head keep it for later and see if you can appreciate the method then ...

kind regards,

Jos

im talking about things like "return" and "compare" and "implements". i havent been taught any of that. the point is to use a triple nested for loop not just a formula :kanyeshrug:
12-26-2010, 02:40 AM
mchahal22

Quote:

Originally Posted by Zack

This might sound odd, but honestly I think that perhaps scrolling up might reveal the rest of the numbers. Running the code, just like for others, produces all numbers for me, and there is no logic in that program that will cut it off.

Perhaps your console output cuts off after so many bytes? I know that in the Python interpreter it cuts off after 16,384 characters (I think, it might be 32,768) so perhaps your output is just being lost.

To test my theory, change:
System.out.println(a+" "+b+" "+c);
...to:
if (a < 50) System.out.println(a+" "+b+" "+c);
...and see what the result is.

i got

28 96 100
28 195 197
29 420 421
30 40 50
30 72 78
30 224 226
31 480 481
32 60 68
32 126 130
32 255 257
33 44 55
33 56 65
33 180 183
34 288 290
35 84 91
35 120 125
36 48 60
36 77 85
36 105 111
36 160 164
36 323 325
38 360 362
39 52 65
39 80 89
39 252 255
40 42 58
40 75 85
40 96 104
40 198 202
40 399 401
42 56 70
42 144 150
42 440 442
44 117 125
44 240 244
44 483 485
45 60 75
45 108 117
45 200 205
45 336 339
48 55 73
48 64 80
48 90 102
48 140 148
48 189 195
48 286 290
49 168 175

after changing to a<50
can u post a screen of your outputs?
12-26-2010, 02:47 AM
mchahal22

ok i figured it out. with system out print, it doesnt print all the outputs. but when i used a plain message box, it does, but the problem is that it shows each triplet individually, so i have to go through all the boxes. is there any other method of output that would show all the results?
12-26-2010, 02:50 AM
Zack

It is what I thought.

Instead of doing println, try something like System.out.print(a+" "+b+" "+c+", "); and see what happens.That will keep it all on one line as best it can.
12-26-2010, 02:53 AM
mchahal22

Quote:

Originally Posted by Zack

It is what I thought.

Instead of doing println, try something like System.out.print(a+" "+b+" "+c+", "); and see what happens.That will keep it all on one line as best it can.

that worked, thx, but that just looks wrong, any suggestions on how to make it look better?
12-26-2010, 03:01 AM
mchahal22

ive made it to output this in one long line, which is good enough. can u explain why the problem happens with println? also is there anyway to order form least hypotenuse to greatest?

3,4,5 / 5,12,13 / 6,8,10 / 7,24,25 / 8,15,17 / 9,12,15 / 9,40,41 / 10,24,26 / 11,60,61 / 12,16,20 / 12,35,37 / 13,84,85 / 14,48,50 / 15,20,25 / 15,36,39 / 15,112,113 / 16,30,34 / 16,63,65 / 17,144,145 / 18,24,30 / 18,80,82 / 19,180,181 / 20,21,29 / 20,48,52 / 20,99,101 / 21,28,35 / 21,72,75 / 21,220,221 / 22,120,122 / 23,264,265 / 24,32,40 / 24,45,51 / 24,70,74 / 24,143,145 / 25,60,65 / 25,312,313 / 26,168,170 / 27,36,45 / 27,120,123 / 27,364,365 / 28,45,53 / 28,96,100 / 28,195,197 / 29,420,421 / 30,40,50 / 30,72,78 / 30,224,226 / 31,480,481 / 32,60,68 / 32,126,130 / 32,255,257 / 33,44,55 / 33,56,65 / 33,180,183 / 34,288,290 / 35,84,91 / 35,120,125 / 36,48,60 / 36,77,85 / 36,105,111 / 36,160,164 / 36,323,325 / 38,360,362 / 39,52,65 / 39,80,89 / 39,252,255 / 40,42,58 / 40,75,85 / 40,96,104 / 40,198,202 / 40,399,401 / 42,56,70 / 42,144,150 / 42,440,442 / 44,117,125 / 44,240,244 / 44,483,485 / 45,60,75 / 45,108,117 / 45,200,205 / 45,336,339 / 48,55,73 / 48,64,80 / 48,90,102 / 48,140,148 / 48,189,195 / 48,286,290 / 49,168,175 / 50,120,130 / 51,68,85 / 51,140,149 / 51,432,435 / 52,165,173 / 52,336,340 / 54,72,90 / 54,240,246 / 55,132,143 / 55,300,305 / 56,90,106 / 56,105,119 / 56,192,200 / 56,390,394 / 57,76,95 / 57,176,185 / 60,63,87 / 60,80,100 / 60,91,109 / 60,144,156 / 60,175,185 / 60,221,229 / 60,297,303 / 60,448,452 / 63,84,105 / 63,216,225 / 63,280,287 / 64,120,136 / 64,252,260 / 65,72,97 / 65,156,169 / 65,420,425 / 66,88,110 / 66,112,130 / 66,360,366 / 68,285,293 / 69,92,115 / 69,260,269 / 70,168,182 / 70,240,250 / 72,96,120 / 72,135,153 / 72,154,170 / 72,210,222 / 72,320,328 / 72,429,435 / 75,100,125 / 75,180,195 / 75,308,317 / 76,357,365 / 77,264,275 / 77,420,427 / 78,104,130 / 78,160,178 / 80,84,116 / 80,150,170 / 80,192,208 / 80,315,325 / 80,396,404 / 81,108,135 / 81,360,369 / 84,112,140 / 84,135,159 / 84,187,205 / 84,245,259 / 84,288,300 / 84,437,445 / 85,132,157 / 85,204,221 / 87,116,145 / 87,416,425 / 88,105,137 / 88,165,187 / 88,234,250 / 88,480,488 / 90,120,150 / 90,216,234 / 90,400,410 / 91,312,325 / 93,124,155 / 93,476,485 / 95,168,193 / 95,228,247 / 96,110,146 / 96,128,160 / 96,180,204 / 96,247,265 / 96,280,296 / 96,378,390 / 98,336,350 / 99,132,165 / 99,168,195 / 99,440,451 / 100,105,145 / 100,240,260 / 102,136,170 / 102,280,298 / 104,153,185 / 104,195,221 / 104,330,346 / 105,140,175 / 105,208,233 / 105,252,273 / 105,360,375 / 108,144,180 / 108,231,255 / 108,315,333 / 108,480,492 / 110,264,286 / 111,148,185 / 112,180,212 / 112,210,238 / 112,384,400 / 112,441,455 / 114,152,190 / 114,352,370 / 115,252,277 / 115,276,299 / 117,156,195 / 117,240,267 / 119,120,169 / 119,408,425 / 120,126,174 / 120,160,200 / 120,182,218 / 120,209,241 / 120,225,255 / 120,288,312 / 120,350,370 / 120,391,409 / 120,442,458 / 123,164,205 / 125,300,325 / 126,168,210 / 126,432,450 / 128,240,272 / 129,172,215 / 130,144,194 / 130,312,338 / 132,176,220 / 132,224,260 / 132,351,375 / 132,385,407 / 132,475,493 / 133,156,205 / 133,456,475 / 135,180,225 / 135,324,351 / 135,352,377 / 136,255,289 / 136,273,305 / 138,184,230 / 140,147,203 / 140,171,221 / 140,225,265 / 140,336,364 / 140,480,500 / 141,188,235 / 144,165,219 / 144,192,240 / 144,270,306 / 144,308,340 / 144,420,444 / 145,348,377 / 145,408,433 / 147,196,245 / 150,200,250 / 150,360,390 / 152,285,323 / 152,345,377 / 153,204,255 / 153,420,447 / 155,372,403 / 155,468,493 / 156,208,260 / 156,320,356 / 156,455,481 / 159,212,265 / 160,168,232 / 160,231,281 / 160,300,340 / 160,384,416 / 161,240,289 / 162,216,270 / 165,220,275 / 165,280,325 / 165,396,429 / 168,224,280 / 168,270,318 / 168,315,357 / 168,374,410 / 168,425,457 / 170,264,314 / 170,408,442 / 171,228,285 / 174,232,290 / 175,288,337 / 175,420,455 / 176,210,274 / 176,330,374 / 176,468,500 / 177,236,295 / 180,189,261 / 180,240,300 / 180,273,327 / 180,299,349 / 180,385,425 / 180,432,468 / 183,244,305 / 184,345,391 / 185,444,481 / 186,248,310 / 189,252,315 / 189,340,389 / 190,336,386 / 190,456,494 / 192,220,292 / 192,256,320 / 192,360,408 / 195,216,291 / 195,260,325 / 195,400,445 / 196,315,371 / 198,264,330 / 198,336,390 / 200,210,290 / 200,375,425 / 201,268,335 / 203,396,445 / 204,253,325 / 204,272,340 / 207,224,305 / 207,276,345 / 208,306,370 / 208,390,442 / 210,280,350 / 210,416,466 / 213,284,355 / 216,288,360 / 216,405,459 / 219,292,365 / 220,231,319 / 222,296,370 / 224,360,424 / 224,420,476 / 225,272,353 / 225,300,375 / 228,304,380 / 228,325,397 / 231,308,385 / 231,392,455 / 232,435,493 / 234,312,390 / 237,316,395 / 238,240,338 / 240,252,348 / 240,275,365 / 240,320,400 / 240,364,436 / 240,418,482 / 243,324,405 / 246,328,410 / 249,332,415 / 252,275,373 / 252,336,420 / 252,405,477 / 255,340,425 / 255,396,471 / 258,344,430 / 260,273,377 / 260,288,388 / 261,348,435 / 261,380,461 / 264,315,411 / 264,352,440 / 266,312,410 / 267,356,445 / 270,360,450 / 273,364,455 / 276,368,460 / 279,372,465 / 280,294,406 / 280,342,442 / 280,351,449 / 282,376,470 / 285,380,475 / 288,330,438 / 288,384,480 / 291,388,485 / 294,392,490 / 297,304,425 / 297,396,495 / 300,315,435 / 300,400,500 / 319,360,481 / 320,336,464 / 325,360,485 / 340,357,493 /
12-26-2010, 03:06 AM
Zack

Your C loop would have to be the outer loop instead of A or B loops.

As for the println explanation, I think your output just runs out of buffer lines and clears the earliest ones to save memory. You could confirm this by putting a 0.1 second timer after each println, and see for yourself when the initial lines disappear, if you wanted to.
12-26-2010, 06:23 AM
mchahal22

Quote:

Originally Posted by Zack

Your C loop would have to be the outer loop instead of A or B loops.

As for the println explanation, I think your output just runs out of buffer lines and clears the earliest ones to save memory. You could confirm this by putting a 0.1 second timer after each println, and see for yourself when the initial lines disappear, if you wanted to.

thx so much you're awesome
12-26-2010, 08:46 AM
JosAH

Quote:

Originally Posted by mchahal22

is there anyway to order form least hypotenuse to greatest?

Your hypothenuse is represented by loop variable c; make the loop over c the outermost loop so the hypothenuse will increase monotonically.

kind regards,

Jos
12-26-2010, 08:49 AM
JosAH

Quote:

Originally Posted by mchahal22

im talking about things like "return" and "compare" and "implements". i havent been taught any of that. the point is to use a triple nested for loop not just a formula :kanyeshrug:

As I wrote before: if my solution is over your head keep it for later and see if you appreciate it later; it is far better than a brute force method; and yes I know, that is not what you had to do but just doing what you have to do and nothing more isn't going to bring you anything.

kind regards,

Jos