5
\$\begingroup\$

The Pythagorean Theorem states that for a right triangle with sides a, b, and c, a2+b2=c2.

A Pythagorean triplet is a set of three numbers, where a2+b2=c2, a To extend this even further, a primitive Pythagorean triplet is a Pythagorean triplet where gcd(a,b,c)=1.

The goal is to find 100 primitive Pythagorean triplets.

Input: No input.

Output: 100 primitive Pythagorean triplets, in whatever order and shape, as long as the output contains only those triplets.

Shortest code wins. Good luck!

\$\endgroup\$
  • \$\begingroup\$ Is a < b or are (a,b,c) and (b,c,a) 2 solutions. \$\endgroup\$ – user unknown Jun 22 '12 at 23:44
  • \$\begingroup\$ @user unknown: a<b<c \$\endgroup\$ – beary605 Jun 23 '12 at 0:49
  • \$\begingroup\$ They're called "triples", not "triplets". \$\endgroup\$ – mbomb007 Oct 28 '16 at 15:04
10
\$\begingroup\$

Python, 42

i=4
while i<203:print 2*i,i*i-1,i*i+1;i+=2
\$\endgroup\$
  • 1
    \$\begingroup\$ i**2 -> i*i to save a couple of characters. \$\endgroup\$ – breadbox Jun 23 '12 at 3:17
  • \$\begingroup\$ I should mark this as cheating, but oh well. :) \$\endgroup\$ – beary605 Jun 23 '12 at 16:00
  • \$\begingroup\$ How is it cheating? \$\endgroup\$ – grc Jun 24 '12 at 1:09
  • 5
    \$\begingroup\$ "hoping for brute force" -- there's something you don't hear every day. \$\endgroup\$ – breadbox Jun 25 '12 at 16:14
  • 2
    \$\begingroup\$ @beary605 why have you accepted the answer that isn't the shortest? \$\endgroup\$ – Griffin Jun 27 '12 at 15:35
5
\$\begingroup\$

Javascript, 44 characters

Update:

for(i=s=0;i^400;)s+=[i+=4,r=i*i/4-1,r+2]+' '

I should have looked up an algorithm first. Well, can't beat python anyway.

Run in a console to see the result.

Old, slow, brute-force variant (140 characters)

for(q=a=[];563>++a;)for(b=a;--b;)(k=Math.sqrt(a*a+b*b))==~~k==function c(e,d,f){return f?c(c(f,e),d):d?c(d,e%d):e}(a,b,k)&&q.push([b,a,k]);q
\$\endgroup\$
5
\$\begingroup\$

J, 64 60 38 49 characters

100$}.~.(/:~*(0<*/*1=+./))"1[4$.$.(=/+/~)2^~i.699

Should've realised that such a big gain was probably flawed. Still uses the brute-force method, but done a bit more efficiently.

Explanation:

x=.2^~i.699 generates a list of ints from 0 to 699 and squares 2^~ them (~ here reverses the order of the arguments).

(=+/~) is a hook that generates an addition table and compares the result to the list. This gives me a three dimensional array with items which are either 1 or 0. A 1 means that a2+b2=c2.

$. converts to a sparse array. For my smaller (9) example I get:

   $.(=/+/~)2^~i.9
0 0 0 | 1
1 0 1 | 1
1 1 0 | 1
2 0 2 | 1
2 2 0 | 1
3 0 3 | 1
3 3 0 | 1
4 0 4 | 1
4 4 0 | 1
5 0 5 | 1
5 3 4 | 1
5 4 3 | 1
5 5 0 | 1
6 0 6 | 1
6 6 0 | 1
7 0 7 | 1
7 7 0 | 1
8 0 8 | 1
8 8 0 | 1

4$. just gives me the left part of this list.

(/:~*(0<*/*1=+./))"1[ decides which rows meet the criteria. (verb)"1 tells the verb to act on the individual rows rather than on the list. [ just separates the 1 and 4, otherwise J will think that 1 4 is a list of 2 numbers. '1=+./' gets the GCD of the three numbers and checks if it's 1. */ multiplies each triple together (getting 0 if it contains a 0) and these two are multiplied together. 0< turns the result into a boolean. * multiplies this result by each triple which eliminates all triples which contain a 0 or have a GCD which is not 1. /:~ sorts each triple.

~. selects the unique items from the list.

}. removes the first item (0 0 0) from the list.

100$ takes the first 100 items from the list.

The above is my answer to this question, but as a matter of interest I implemented grc's method, (27 characters):

2(*,.<:@^~,.>:@^~)2*2+i.100
\$\endgroup\$
2
\$\begingroup\$

Scala 180:

def g(a:Int,b:Int):Int=if(a==b)a else
if(a>b)g(a-b,b)else
g(b,a)
for(c<-(5 to 629);
a<-(1 to c-2);
b<-(a to c-1);
if((a*a+b*b==c*c)&&g(c,g(a,b))==1)&&a<400)println(a+"  "+b+" "+c)

Ungolfed:

def gcd (a: Int, b: Int) : Int = if (a == b) 
  a else 
    if (a > b) gcd (a-b, b) else
      gcd (b, a)

def gcd (a: Int, b: Int, c:Int): Int = gcd (c, gcd (a, b))

def pythagorean (a: Int, b: Int, c: Int) = (a * a + b * b == c * c)

for (c <- (5 to 629);
  a <- (1 to c-2); 
  b <- (a to c-1);
  if (pythagorean (a, b, c) && gcd (a, b, c) == 1)) yield {
    println (a + "² + "  + b + "² = " + c + "² => " + (a*a) + " + " + (b*b) + " = " + (c*c))
    c*c
  }
\$\endgroup\$
2
\$\begingroup\$

APL (31)

↑{(2×⍵),(A-1),1+A←⍵×⍵}¨2+2×⍳100

It uses basically the same approach as the Python program.

\$\endgroup\$
2
\$\begingroup\$

MATLAB 29

i=2:2:200;[2*i;i.*i-1;i.*i+1]
\$\endgroup\$
2
\$\begingroup\$

Mathematica 33

{2#,#^2-1,#^2+1}&/@Range[4,203,2]
\$\endgroup\$
1
\$\begingroup\$

APL(NARS), 26 chars, 52 bytes

{k(4×⍵),2+k←¯1+×⍨2×⍵}¨⍳100

test:

  a←{k(4×⍵),2+k←¯1+×⍨2×⍵}¨⍳100
  ≢a
100
  +/{(x y z)←⍵⋄(z*2)=(y*2)+x*2}¨a
100
  +/{∨/⍵}¨a
100
  10↑a
3 4 5  15 8 17  35 12 37  63 16 65  99 20 101  143 24 145  195 28 197  255 32 257  323 36 325  399 40 401
\$\endgroup\$
0
\$\begingroup\$

R, 49 characters

translated from the Python solution:

i=4;while(i<203){print(c(2*i,i*i-1,i*i+1));i=i+2}
\$\endgroup\$
  • 1
    \$\begingroup\$ You should take advantage of the functional nature of R i=seq(2,200,2);c(2*i,i*i-1,i*i+1) (though the output is a bit messy). \$\endgroup\$ – Griffin Jun 26 '12 at 13:55
  • \$\begingroup\$ Ops! I posted without taking a look at all the other answers! :-P \$\endgroup\$ – Paolo Jun 26 '12 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.