Unique triples: Length of wire bent into triangle

I have attached a picture of the question for clarity.

My current code looks like this, I'm using a small range to test it out first. It's not working right though.

clear;
a=randi(10);
b=randi(10);
c=randi(10);
for L=1:20
    if c = sqrt(a^2 + b^2);
       L = a + b + c;
       disp([a,b,c]);
    else
        disp([0,0,0]);
    end;
end

[Guillaume]

I like this statement at the end of the assigment "you may NOT use any of the built in Matlab functions for this question except the fprintf function.", noting that the question asks to "write a function".

I invite you to type

edit function

at the matlab prompt and look at the last line of the code that pops up.

[Image Analyst]

http://www.mathworks.com/matlabcentral/answers/38787-what-can-be-programmed-without-any-built-in-functions

Answer 1

[John D'Errico]

(I could not resist posting this answer, as sometimes a solution is just too nice NOT to post. Since I've written no directly usable code to solve the homework problem, I don't feel too bad about it though. In fact, I invite tyerd to write code based on my approach.)

Simpler than brute force is to use the basic formulas for pythagorean triples.

a = m^2 - n^2
b = 2*m*n 
c = m^2 + n^2 

http://en.wikipedia.org/wiki/Pythagorean_triple

Given that, what is the sum of the side lengths?

L = a + b + c = 2*m^2 + 2*m*n = 2*m*(m+n)

So IF the sum of the side lengths (L) is given, then factor it. Use those factors to determine possible values for m and n. Note that m must be greater than n for a to be positive.

For example, suppose L = 30, which is trivially factored into 2*3*5.

Then we might try m=3, n=2, in which case the triple is given as

triples = @(m,n) [m.^2 - n.^2,2*m.*n,m.^2+n.^2];
triples(3,2)
ans =
     5    12    13

The point is, the solution is quite straightforward. No explicit loops are required at all, although you would need to factor L, presumably without the use of the function factor.

Oh, by the way, one quick test to see if a solution does not exist, is if n is odd. It is necessary, but not sufficient that L be even for a solution to exist. So for example, no solution appears to exist for L=54, despite the even parity.

Now lets try a bit more difficult example.

L = 13320;

We need to factor L/2 into pairs of integers, such that the product is L/2=13320/2.

I'll use my factorpairs code, as found on the File Exchange. In fact, I've intentionally used factorpairs to avoid giving a solution that does not use any built-in functions.

factorpairs(13320/2)
ans =
         1        6660
         2        3330
         3        2220
         4        1665
         5        1332
         6        1110
         9         740
        10         666
        12         555
        15         444
        18         370
        20         333
        30         222
        36         185
        37         180
        45         148
        60         111
        74          90

Clearly there are only two of those factor pairs which can satisfy the constraint that one member of the pair is m, while the second is m+n, where m>n.

The first is:

m = 74
n = 90 - 74 = 16

The second such solution is

m = 60
n = 111 - 60 = 51

See that is we go any higher up that list, such as m=48, then n would be 97, which fails the test that m>n.

So there are exactly two pythagorean triple solutions to the problem with L = 13320.

triples(74,16)
ans =
      5220        2368        5732

triples(60,51)
ans =
       999        6120        6201

Just a quick check to verify they are Pythagorean triples:

5220.^2 + 2368.^2 == 5732.^2
ans =
   1

999.^2 + 6120.^2 == 6201.^2
ans =
   1

Again, the point is that you CAN use brute force to find a solution to many problems. But a simple application of mathematics is often a far better choice. In fact, I could have written code to solve this entire problem trivially without even the use of my factorpairs code, or even the function factor. But HAD I done that, then I would have solved your homework problem for you. Feel free to use the idea though, but in order to do that, you will need to write some code.

If you do, a good test will be to find all four unique solutions to the problem with L = 435364354560, or to prove quickly that only one solution can exist for L = 4353643545645448, or to prove that no solution can exist for L = 123456789012346. Of course, feel free to solve those problems with triply nested loops, and see how quickly that runs. :)

[John D'Errico]

I will make an offer to tyerd. If you make a decent effort to write code based on the scheme I show above, I'll help you to make sure it works, and does so efficiently. My code for the test case:

timeit(@() pythagSum(4353643545645448))
ans =
         0.7434623939125

took well under 1 second to run.

[John D'Errico]

Too bad. I was hoping to see an attempt here. I've attached a nice little m-file. (I've deleted the original version, that missed some solutions.) The current version is attached below.

[Guillaume]

Hello John, it certainly is a nice solution. One issue though, is that euclid's formula does not generate all possible triples (as per the wikipedia article you've linked: "Despite generating all primitive triples, Euclid's formula does not produce all triples").

For example

>>pythagSum(225)
ans = 
   []
>>9^2 + 12^2
ans =
   225
>>15^2
ans =  
   225

As per the wiki article, it still can be adapted to actually generate all triples.

[John D'Errico]

Guillaume - you have managed to misunderstand the code.

pythagSum takes in the value L, the SUM of the three side lengths of the triangle. It does NOT take the square of the length of the hypotenuse. You should recall that this WAS the intention after all.

So in order to find the pythagorean triple [9 12 15], you need to call it as pythagSum(36), since 9+12+15 = 36.

Regardless, you are correct in the sense that pythagSum as I originally wrote it would have failed to find that triple.

So I've attached a new version, that factors the number into triples with the necessary property, that the sum L may be factored into integers of the form 2*k*m*(m+n), where m is strictly greater than n.

pythagSum(36)
ans =
   9    12    15

Next, for a larger input argument:

[triples,kmn] = pythagSum(12345678901236)
triples =
   173688310992   6084756071794   6087234518450
  6084756071794    173688310992   6087234518450
  2954294657073   4231018507740   5160365736423
  3086419725309   4115226300412   5144032875515

kmn =
              1         1769311         1719527
              2         1744419           24892
              3         1162946          606365
  1028806575103               2               1

sum(triples,2)
ans =
  12345678901236
  12345678901236
  12345678901236
  12345678901236

Answer 2

[Roger Stafford]

The question is asking you to start with just a given integer, L, and find integers a, b, and c which are the lengths of a right triangle which sum to L. You need to write code that in some way searches through all possible combinations of integers a, b, and c that are valid lengths of such a triangle.

One way to do this would be with a couple of nested for-loops that go through all possible a and b integers less than L and check whether c = L-a-b satisfies the requirement for a right triangle.

Another way, which requires only one for-loop, would go through, say, all possible values of 'a' less than L/sqrt(2). Then from the two equations that must be satisfied, you can calculate uniquely what b and c must be, and you could then check whether they were positive integers or not.

If you are designing this code for the possibility of very large values of L, there would be a decided advantage in computing time in using the method with only one for-loop, even though it is more complicated.