All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Pythagorean Chain (Posted on 2006-03-20)
Take a right triangle with integer sides A, B, & C.
(C need not be the hypotenuse.)

To side C attach another right triangle with integer sides C, D & E.

On this new triangle attach another right triangle to either side D or E. Continue the process of attaching a new right triangle to the previous; creating a chain of right triangles.

Three further rules:
1. No side length may be repeated.
2. No triangles may overlap.
3. No side may have length over 10000.

How many triangles can you make in this chain?

 See The Solution Submitted by Jer Rating: 3.5000 (4 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer exploration --- but ... | Comment 10 of 18 |

I don't know if it's definitely certain that finding a chain of Pythagorean triples implies that that chain can be created without causing the chain to curve around on itself to force overlapping triangles.  It would seem that at any given stage, you have the choice of two orientations to place the next triangle, and that one of them would steer the remainder of the chain away from this self-intersection, but I don't know I could prove this, or even be truly certain it was true.

With that caveat aside, I did write a program to find chains of Pythagorean triples.  It uses three files, each containing all the Pythagorean triples with no number exceeding 10000. One of the files is sorted on the shorter leg, one on the longer leg, and one on the hypotenuse.  It uses these to do binary searches to find matching sides.  Here's the program:

DECLARE SUB build ()
DECLARE SUB ckMatch (s\$, n!)
CLEAR , , 30000

OPEN "pythchn.txt" FOR OUTPUT AS #4

OPEN "pythchn1.txt" FOR BINARY AS #1
OPEN "pythchn2.txt" FOR BINARY AS #2
OPEN "pythchn3.txt" FOR BINARY AS #3

DIM SHARED a\$(230), b\$(230), c\$(230), lvl, n\$, maxLvl, used(10000), builtOn\$

r\$ = SPACE\$(17): n\$ = SPACE\$(5)

FOR i = 1 TO 12471
GET #1, i * 19 - 18, r\$
a1\$ = LEFT\$(r\$, 5): used(VAL(a1\$)) = 1
b1\$ = MID\$(r\$, 7, 5): used(VAL(b1\$)) = 1
c1\$ = RIGHT\$(r\$, 5): used(VAL(c1\$)) = 1

a\$(1) = a1\$: b\$(1) = b1\$: c\$(1) = c1\$:
lvl = 1
build

used(VAL(a1\$)) = 0
used(VAL(b1\$)) = 0
used(VAL(c1\$)) = 0
NEXT

CLOSE

SUB build
FOR i = 1 TO 3
ckMatch a\$(lvl), i
ckMatch b\$(lvl), i
ckMatch c\$(lvl), i
NEXT
END SUB

SUB ckMatch (s\$, n)
IF s\$ = builtOn\$ THEN EXIT SUB
r\$ = SPACE\$(17)
low = 1: high = 12471
DO
mid = INT((low + high) / 2)
GET #n, 19 * mid - 18, r\$
cmpar\$ = MID\$(r\$, n * 6 - 5, 5)
IF cmpar\$ < s\$ THEN
low = mid + 1
ELSEIF cmpar\$ > s\$ THEN
high = mid - 1
ELSE
EXIT DO
END IF
LOOP UNTIL low > high
IF cmpar\$ = s\$ THEN
j = mid
DO
j = j - 1
IF j > 0 THEN
GET #n, 19 * j - 18, r\$
cmpar\$ = MID\$(r\$, n * 6 - 5, 5)
END IF
LOOP UNTIL j = 0 OR cmpar\$ <> s\$
i = j + 1
DO
GET #n, 19 * i - 18, r\$
cmpar\$ = MID\$(r\$, n * 6 - 5, 5)
IF cmpar\$ <> s\$ THEN EXIT DO
good = 1
FOR j = 1 TO 3
IF j <> n THEN
c = VAL(MID\$(r\$, j * 6 - 5, 5))
IF used(c) THEN
good = 0: EXIT FOR
END IF
END IF
NEXT
IF good THEN
lvl = lvl + 1
FOR j = 1 TO 3
c = VAL(MID\$(r\$, j * 6 - 5, 5))
used(c) = 1
NEXT
a\$(lvl) = LEFT\$(r\$, 5)
b\$(lvl) = MID\$(r\$, 7, 5)
c\$(lvl) = RIGHT\$(r\$, 5)
IF lvl > maxLvl THEN
maxLvl = lvl
FOR j = 1 TO lvl
PRINT j, a\$(j); "-"; b\$(j); "-"; c\$(j)
PRINT #4, j, a\$(j); "-"; b\$(j); "-"; c\$(j)
NEXT
PRINT "----------"
PRINT #4, "----------"
END IF

bu\$ = builtOn\$
builtOn\$ = s\$

build

FOR j = 1 TO 3
IF j <> n THEN
c = VAL(MID\$(r\$, j * 6 - 5, 5))
used(c) = 0
END IF
NEXT
lvl = lvl - 1
builtOn\$ = bu\$
END IF
i = i + 1
LOOP
END IF
END SUB

It's recursive, so needs stack space; uses strings, so needs string space; and of course regular storage space.  These factors seem to have determined the limit of the chain size arbitrarily, so the actual size limit has not been found. (i.e., the program crashes due to space limitations before exhausting the possibilities).

The longest it found before crashing was:

` 1                3-    4-    5 2                5-   12-   13 3               12-   16-   20 4               16-   30-   34 5               30-   40-   50 6               40-   42-   58 7               42-   56-   70 8               56-   90-  106 9               90-  120-  150 10             120-  126-  174 11             126-  168-  210 12             168-  224-  280 13             224-  360-  424 14             360-  378-  522 15             378-  504-  630 16             504-  550-  746 17             550- 1320- 1430 18            1320- 1386- 1914 19            1386- 1848- 2310 20            1848- 1989- 2715 21            1989- 2652- 3315 22            2652- 2961- 3975 23            2961- 3948- 4935 24            3948- 5264- 6580 25            5264- 8052- 9620 26             635- 8052- 8077 27             635- 1524- 1651 28            1524- 2032- 2540 29            2032- 3810- 4318 30            3810- 5080- 6350 31            5080- 5334- 7366 32            5334- 7112- 8890 33            4191- 7112- 8255 34            4191- 5588- 6985 35            6096- 6985- 9271 36            4572- 6096- 7620 37            1905- 4572- 4953 38            1905- 7952- 8177 39            1065- 7952- 8023 40            1065- 1420- 1775 41            1420- 1491- 2059 42            1491- 1988- 2485 43            1988- 3195- 3763 44            3195- 4260- 5325 45            4260- 4473- 6177 46            4473- 5964- 7455 47             923- 5964- 6035 48             923- 2436- 2605 49            2436- 2923- 3805 50            3805- 9132- 9893 51             468- 9120- 9132 52             468-  595-  757 53             595-  600-  845 54             600-  800- 1000 55             800-  840- 1160 56             840-  882- 1218 57             882- 1176- 1470 58            1176- 1568- 1960 59            1568- 2145- 2657 60            2145- 2300- 3145 61            2300- 2415- 3335 62            2415- 3220- 4025 63            3220- 3381- 4669 64            3381- 4508- 5635 65            4508- 6720- 8092 66            6720- 7056- 9744 67             833- 7056- 7105 68             833- 1056- 1345 69            1056- 1210- 1606 70            1210- 2904- 3146 71            2904- 3465- 4521 72            3465- 3876- 5199 73            3876- 4480- 5924 74            4480- 4704- 6496 75            4704- 5278- 7070 76            5278- 7440- 9122 77             244- 7440- 7444 78             244- 3717- 3725 79            3717- 4560- 5883 80            4560- 4788- 6612 81            4788- 5225- 7087 82            5225- 6660- 8465 83            6660- 6731- 9469 84            3556- 5715- 6731 85            5715- 7052- 9077 86             336- 7052- 7060 87             336-  377-  505 88             377- 5460- 5473 89            5460- 5733- 7917 90            5733- 7644- 9555 91             567- 7644- 7665 92             567-  756-  945 93             756-  825- 1119 94             825- 1100- 1375 95            1100- 1155- 1595 96            1155- 1292- 1733 97            1292- 5415- 5567 98            5415- 7220- 9025 99            4959- 7220- 8759 100           2160- 4959- 5409 101           2160- 2268- 3132 102           2268- 2475- 3357 103           2475- 2992- 3883 104           2992- 3294- 4450 105           3294- 4392- 5490 106           4392- 5856- 7320 107           5856- 6290- 8594 108           5400- 6290- 8290 109           5400- 5670- 7830 110           5670- 7560- 9450 111            213- 7560- 7563 112            213-  284-  355 113            284- 5037- 5045 114           5037- 6716- 8395 115           3213- 6716- 7445 116           3213- 3240- 4563 117           3240- 3402- 4698 118           3402- 6120- 7002 119           6120- 6426- 8874 120           6426- 6480- 9126 121           6480- 6804- 9396 122           1053- 6804- 6885 123           1053- 1404- 1755 124           1404- 1785- 2271 125           1785- 1800- 2535 126           1800- 1890- 2610 127           1890- 2520- 3150 128           2520- 2646- 3654 129           2646- 3528- 4410 130           3528- 3850- 5222 131           3850- 5304- 6554 132           5304- 5922- 7950 133           5922- 7896- 9870 134            890- 7896- 7946 135            890- 2136- 2314 136           2136- 2848- 3560 137           2848- 5340- 6052 138           5340- 5607- 7743 139           5607- 7476- 9345 140           1157- 7476- 7565 141            348- 7565- 7573 142            348-  464-  580 143            464-  777-  905 144            777- 1036- 1295 145           1036- 1173- 1565 146           1173- 1564- 1955 147           1564- 1827- 2405 148           1827- 2660- 3227 149           2660- 2793- 3857 150           2793- 3060- 4143 151           3060- 3472- 4628 152           3472- 5580- 6572 153           5580- 5859- 8091 154           5859- 7812- 9765 155            125- 7812- 7813 156            125-  300-  325 157            300-  315-  435 158            315-  420-  525 159            420-  441-  609 160            441-  588-  735 161            588-  784-  980 162            784- 1260- 1484 163           1260- 1680- 2100 164           1680- 1885- 2525 165           1885- 2088- 2813 166           2088- 2091- 2955 167           2091- 2788- 3485 168           2788- 6435- 7013 169           6435- 6900- 9435 170            576- 6900- 6924 171            576-  660-  876 172            660-  693-  957 173            693- 1560- 1707 174           1560- 1638- 2262 175           1638- 2184- 2730 176           2184- 2650- 3434 177           2650- 6360- 6890 178           6360- 6678- 9222 179           6678- 7104- 9750 180           1035- 7104- 7179 181           1035- 1120- 1525 182           1120- 1368- 1768 183           1368- 1824- 2280 184           1824- 1943- 2665 185           2665- 2952- 3977 186           2952- 3936- 4920 187           3936- 4275- 5811 188           4275- 5168- 6707 189           5168- 8526- 9970 190           2800- 8526- 8974 191           2800- 2940- 4060 192           2940- 3087- 4263 193           3087- 4116- 5145 194           4116- 5488- 6860 195           3234- 5488- 6370 196           3234- 4312- 5390 197           4312- 4641- 6335 198           4641- 4680- 6591 199           4680- 4914- 6786 200           4914- 6552- 8190 201           6552- 6586- 9290 202            810- 6536- 6586 203            810- 1080- 1350 204           1080- 1134- 1566 205           1134- 2040- 2334 206           2040- 2142- 2958 207           2142- 2856- 3570 208           2856- 2880- 4056 209           2880- 3024- 4176 210           3024- 3300- 4476 211           3300- 3731- 4981 212           3731- 5292- 6475 213           5292- 5775- 7833 214           5775- 6460- 8665`

Perhaps someone can port the program to Visual Basic (from the Quick Basic it's in), and gain the extra resources of Windows (rather than the DOS environment it's in). The syntax is similar; the big difference is you can't use both the string n\$ and the numeric variable n, for example.

 Posted by Charlie on 2006-03-20 21:54:20

 Search: Search body:
Forums (0)