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

Home > Shapes
Pythagorean Chain (Posted on 2006-03-20) Difficulty: 3 of 5
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.)
Some Thoughts 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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information