18
\$\begingroup\$

Generate the shortest possible code in any programming language that can generate all Pythagorean triples with all values not exceeding a given integer limit. A Pythagorean triple is a set of three integers \$(a, b, c)\$ that satisfy the equation \$a^2 + b^2 = c^2\$. The program should output the triples in any format, such as a list of tuples or a newline-separated list of strings.

Input: An integer limit \$n\$ (1 ≤ \$n\$\$10^6\$)

Output: All Pythagorean triples \$(a, b, c)\$ such that \$1 ≤ a, b, c ≤ n\$ and \$a^2 + b^2 = c^2\$.

Test Cases

Input: 20
Output:
(3, 4, 5)
(5, 12, 13)
(6, 8, 10)
(8, 15, 17)
(9, 12, 15)
(12, 16, 20)
Input: 5
Output:
(3, 4, 5)

Note: The output order does not matter as long as all the correct Pythagorean triples are included. Duplicate triples should not be included. But, specifying the order might help.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Can I output numbers without parentheses like 3,4,5? \$\endgroup\$
    – EzioMercer
    Feb 27, 2023 at 13:25
  • 2
    \$\begingroup\$ Suggested test cases: a number less than 5 and a number that isn't equal to any possible \$c\$ value. \$\endgroup\$
    – Yousername
    Feb 27, 2023 at 23:28
  • 1
    \$\begingroup\$ Suggested Test-Case: n=16, because answers iterating only over a and b might produce the wrong solution with c=17 \$\endgroup\$
    – Falco
    Feb 28, 2023 at 14:14

24 Answers 24

6
\$\begingroup\$

05AB1E, 9 bytes

L3.Æʒn`αQ

Try it online or verify all test cases.

The last three bytes could alternatively be RÆ_ for the same byte-count:

Try it online or verify all test cases.

Explanation:

L         # Push a list in the range [1, (implicit) input-integer]
 3.Æ      # Create all triplet-combinations of this list
    ʒ     # Filter this list of [a,b,c]-triplets by:
     n    #  Square each inner integer in the triplet
      `   #  Push all three values separated to the stack
       α  #  Get the absolute difference of the top two: |b²-c²|
        Q #  Check if it's equal to the third one: a² == |b²-c²|
          # (after which the filtered list of triplets is output implicitly as result)

      R   #  Reverse the triplet to [c²,b²,a²]
       Æ  #  Reduce it by subtracting: c²-b²-a²
        _ #  Check if this is 0
\$\endgroup\$
6
\$\begingroup\$

Vyxal, 9 8 bytes

ɾ3ḋ'²÷ε=

Try it Online!

I'm surprised I didn't manage to make this horribly inefficient.

-1 thanks to Kevin!

Explained

ɾ3ḋ'²÷ε=
ɾ          # Range [1, input]
 3ḋ        # Combinations of length 3
   '       # filtered by:
    ²      #   squaring everything
     ÷     #   dumping the triplet onto the stack in reverse order
      ε    #   absolute difference of b**2 and c**2
       =   #   equals a**2
\$\endgroup\$
2
  • \$\begingroup\$ ^+ can be ε for -1 byte (port of my top 05AB1E answer). \$\endgroup\$ Feb 27, 2023 at 13:22
  • \$\begingroup\$ @KevinCruijssen good catch. Didn't think to think that the equation could be written in terms of equalling a squared \$\endgroup\$
    – lyxal
    Feb 27, 2023 at 23:10
5
\$\begingroup\$

Factor + math.combinatorics, 57 bytes

[ [1,b] 3 [ 2 v^n first3 -rot + = ] filter-combinations ]

Try it online!

  • [1,b] 3 [ ... ] filter-combinations select combinations of three from \$[1..n]\$ where...
  • 2 v^n square the elements of the triplet
  • first3 place each element onto the stack
  • -rot move \$c^2\$ from the top of the stack to the bottom
  • + add \$a^2\$ and \$b^2\$
  • = equal?
\$\endgroup\$
4
\$\begingroup\$

Thunno, \$13\log_{256}(96)\approx\$ 10.70 bytes

R1+3zQg2^Au_=

Attempt This Online!

Port of Kevin Cruijssen's 05AB1E answer.

Explanation

R1+3zQg2^Au_=  # Implicit input
R1+            # Push range(1, input+1)
   3zQ         # Combinations with length 3
      g        # Filter by:                     STACK: [a, b, c]
       2^      #  Square each                   STACK: [a**2, b**2, c**2]
         Au    #  Dump onto stack               STACK: a**2, b**2, c**2
           _   #  Subtract top two              STACK: a**2, c**2 - b**2
            =  #  Are they equal?               STACK: a**2 == c**2 - b**2
               # Implicit output
\$\endgroup\$
4
\$\begingroup\$

Noether, 62 bytes

!aI~n(!a~bn1+({a2^!b2^+0.5^~cn<cn=|cc_=&}{aP","PbP","PcP?}b)a)

Try it in your browser!

Surprisingly this is the first time I've realised the severe lack of \$\leq\$ and \$\geq\$ operators in the language.

Explanation:

!a                                                             # Initialiase variable a to 1
  I~n                                                          # Store user input in n: outer loop exit condition
     (                                                       ) # Outer loop
      !a~b                                                     # Increment a and store value in b                                                      
          n1+                                                  # Add 1 to n: inner loop exit condition
             (                                             )   # Inner loop
              {                         }{               }     # If ... Else
               a2^                                             # Square a                                     
                  !b2^                                         # Increment value of b and square                       
                      +0.5^                                    # Sum a and b and square root                            
                           ~cn<                                # Store value in c and check if less than n                         
                               cn=                             # c == n                       
                                  |                            # Bitwise OR                   
                                   cc_=                        # c == floor(c)                  
                                       &                       # Bitwise AND                
                                          aP","PbP","PcP?      # If true, output variable values, comma separated
                                                          b    # Push b to stack (inner loop exit condition)
                                                            a  # Push a to stack (outer loop exit condition)
\$\endgroup\$
3
\$\begingroup\$

Japt, 14 bytes

õ à3 fÈ̲ѶXx²

Try it

õ à3 fÈ̲ѶXx²     :Implicit input of integer U
õ                  :Range [1,U]
  à3               :Combinations of length 3
     f             :Filter by
      È            :Passing each X through the following function
       Ì           :  Last element
        ²          :  Square
         Ñ         :  Multiply by 2
          ¶        :  Is equal to
           Xx      :  X reduced by addition
             ²     :  After squaring each
\$\endgroup\$
4
  • \$\begingroup\$ 12 bytes by (roughly) porting Kevin's O5AB1E answer \$\endgroup\$
    – noodle man
    Feb 27, 2023 at 15:52
  • \$\begingroup\$ Could be 11 if there were a reduce-right builtin :| \$\endgroup\$
    – noodle man
    Feb 27, 2023 at 16:01
  • \$\begingroup\$ Why multiply by 2 after squaring? \$\endgroup\$
    – Falco
    Feb 28, 2023 at 14:17
  • 1
    \$\begingroup\$ @Falco the program checks if \$c^2 \times 2 = a^2 + b^2 + c^2\$, which simplifies to pythagorean theorem \$\endgroup\$
    – noodle man
    Mar 1, 2023 at 16:17
3
\$\begingroup\$

><> (Fish), 111 bytes

i:*&43::*{:}:*+\
/*::<5[1;?)&:&:/
\:{:}(?!v~1+31.
/]v?)}:{/|.!051+1~\
n \]~~>1+$:@$:@= ?^50.
\' 'o}:n' 'o}:nao$~$64.

Try it

Explanation

enter image description here

><> lacks a square root function so this simply tries all numbers until it finds one greater than the square of the inputs.

First, we square the input. We start searching at a,b=4,3. We check if \$a^2\$, (::*) + \$b^2\$ is more than the input squared, if so we exit.

Then we push 5, the starting third value. Square it, if it is more than a^2+b^2, go to the next iteration. Otherwise, add 1 to C.

If A^2+B^2=C^2, print A, B, and C, then go to next.

When we go to the next iteration, add 1 to B. If B>A, add 1 to A instead and reset B to 1. This is 1+$:@$:@=?~1+1. Then we jump back to the start to try another iteration.

\$\endgroup\$
3
\$\begingroup\$

Scala, 71 bytes

(n:Int)=>for{c<-5 to n;b<-4 to c;a<-3 to b if a*a+b*b==c*c}yield(a,b,c)

or styled differently:

(n:Int)=>for{c<-5 to n
b<-4 to c
a<-3 to b
if a*a+b*b==c*c}yield(a,b,c)

It's not often that Scala gets a chance to do well in golfing, but the .to() method is perfect for inclusive ranges.

Try it online or on Scastie!

\$\endgroup\$
3
\$\begingroup\$

JavaScript, 81 bytes

n=>{for(a=0;++a<n;)for(b=a;b<n;++b)(c=(a*a+b*b)**.5)%1||c<=n&&console.log(a,b,c)}

Try it:

f=n=>{for(a=0;++a<n;)for(b=a;b<n;++b)(c=(a*a+b*b)**.5)%1||c<=n&&console.log(a,b,c)}

;[
  1,
  3,
  5,
  7,
  10,
  17,
  20
].forEach(n=>{console.log(n+':');f(n)})

\$\endgroup\$
5
  • \$\begingroup\$ 64 bytes \$\endgroup\$
    – Shaggy
    Feb 27, 2023 at 15:00
  • \$\begingroup\$ @Shaggy Thank you! But I deliberately did not write such an option because of this is the @Aranuld's answer just with for instead of while :) \$\endgroup\$
    – EzioMercer
    Feb 27, 2023 at 15:04
  • \$\begingroup\$ @Shaggy the shorter solution errs for n=16, because then c will be 17, which is too large \$\endgroup\$
    – Falco
    Feb 28, 2023 at 14:13
  • 1
    \$\begingroup\$ @PierrePaquette There are no duplicates in either my solution or Shaggy's solution. \$\endgroup\$
    – EzioMercer
    Feb 28, 2023 at 23:38
  • \$\begingroup\$ Indeed; I just noticed I didn’t run Shaggy’s solution properly. Apologies. \$\endgroup\$ Feb 28, 2023 at 23:44
3
\$\begingroup\$

JavaScript (V8), 63 bytes

n=>{for(;p=n;n--)while(--p>(q=(n*n-p*p)**.5))q%1||print(q,p,n)}

Try it online!

Commented

n => {                  // n = input
  for(                  // outer loop:
    ;                   //
    p = n;              //   before each iteration, initialize p to n
                        //   stop when n = 0
    n--                 //   decrement n after each iteration
  )                     //
    while(              //   inner loop:
      --p > (           //     decrement p and test whether it's greater
        q =             //     than q defined as:
        (n * n - p * p) //       the square root of the difference
        ** .5           //       between n² and p²
      )                 //     stop as soon as the test fails
    )                   //
      q % 1 ||          //     if q is an integer:
        print(q, p, n)  //       print the triplet (q, p, n)
}                       //
\$\endgroup\$
4
  • \$\begingroup\$ I'm not aware of the "print" function in JavaScript. window.print() seems to print the currently open HTML document. I think you need console.log ? \$\endgroup\$
    – Falco
    Feb 28, 2023 at 13:08
  • \$\begingroup\$ @Falco This is a V8 instruction, which is unrelated to window.print(). \$\endgroup\$
    – Arnauld
    Feb 28, 2023 at 13:26
  • \$\begingroup\$ Oh I didn't know this. Also your program errs on n=16 (printing 17,15,8 as a valid solution, but 17 > 16) \$\endgroup\$
    – Falco
    Feb 28, 2023 at 13:31
  • 1
    \$\begingroup\$ @Falco Thanks. Now fixed. \$\endgroup\$
    – Arnauld
    Feb 28, 2023 at 14:18
2
\$\begingroup\$

Arturo, 50 bytes

$=>[select combine.by:3@1..&'x[=+x\0^2x\1^2x\2^2]]

Try it

$=>[                      ; an anonymous function
    select                ; select elements from a block
    combine.by:3 @1..&    ; combinations of 3 from the range 1 to n
    'x                    ; assign current triplet to x in the select
    [                     ; begin select
        =+x\0^2x\1^2x\2^2 ; is a^2+b^2 equal to c^2?
    ]                     ; end select
]                         ; end function
\$\endgroup\$
2
\$\begingroup\$

Python, 91 88 bytes

lambda n,r=range:[(k,j,i)for i in r(1,n+1)for j in r(1,i)for k in r(1,j)if i*i==j*j+k*k]

Attempt This Online!

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

Nekomata, 12 bytes

RS3Lᵖ{:*Ɔ$∑=

Attempt This Online!

A port of @Fatalize's Brachylog answer.

RS3Lᵖ{:*Ɔ$∑=
R               Range from 1 to the input
 S              Subset
  3L            Length should be 3
    ᵖ{          Start a block; treat the block as a predicate,
                  and return the original value if the block does not fail
      :*        Multiply by itself
        Ɔ$∑=    The last element should equals to the sum of the other elements

By default, the Nekomata interpreter will print all possible results.

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 26 bytes

IΣΣE⊕NEιEΦλ⁼×ιι⁺×λλ×νν⟦νλι

Attempt This Online! Link is to verbose version of code. Explanation:

     N                      Input integer
    ⊕                       Incremented
   E                        Map over implicit range
       ι                    Current value
      E                     Map over implicit range
          λ                 Current value
         Φ                  Filter over implicit range
            ×ιι             Square of outer value
           ⁼                Equals
                ×λλ         Square of inner value
               ⁺            Plus
                   ×νν      Square of innermost value
        E                   Map over matches
                      ⟦     List of
                       ν    Innermost value
                        λ   Inner value
                         ι  Outer value
  Σ                         Flatten
 Σ                          Flatten
I                           Cast to string
                            Implicitly print
\$\endgroup\$
1
\$\begingroup\$

MathGolf, 21 bytes

╒■■mÅ─╡gæ_▀s=gƲxε-┬▀

Try it online.

Explanation:

╒         # Push a list in the range [1, (implicit) input-integer]
 ■        # Get the cartesian product with itself to create pairs
  ■       # Get the cartesian product with itself to create pairs of pairs
   m      # Map over each pair of pairs,
    Å     # using 2 characters as inner code-block:
     ─    #  Flatten the pair to a quadruplet
      ╡   #  Discard the last item to make it a triplet
 g        # Filter this list of triplets by,
  æ       # using 4 characters as inner code-block:
   _      #  Duplicate the current list
    ▀     #  Uniquify the values in the copy
     s    #  Sort it from lowest to highest
      =   #  Check if the two lists are still the same
 g        # Filter this list further by,
  Æ       # using 5 characters as inner code-block:
   ²      #  Square each integer in the triplet
    x     #  Reverse it
     ε    #  Reduce the triplet by:
      -   #   Subtracting
       ┬  #  Check if the result of this c²-b²-a² equals 0
 ▀        # After the filter: uniquify the remaining list of triplets
          # (after which the entire stack is output implicitly as result)
\$\endgroup\$
1
\$\begingroup\$

Pyth, 14 bytes

f!-F^R2_T.CSQ3

Try it online!

Explanation

                  # implicitly assign Q = eval(input())
         .C  3    # all sorted lists of three elements from
           SQ     # range(1,Q+1)
f                 # filter these lists on lambda T
       _T         #   reverse T
    ^R2           #   map elements to their squares
  -F              #   fold on subtraction (subtract all elements from the first)
 !                #   not (only true for zero)
\$\endgroup\$
1
\$\begingroup\$

Befunge-93 (PyFunge), 125 bytes

v
&
>35g:*25g:*+15g:*-|
  ,*52.g51.g52.g53<v
^p53+1_v#`\g52:g53<<
^111   >$135p25g:1 5g\`!#v_1+25p
^ p51+1_@#`g51\g51 :p521$<

Try it online!

Note: The three "1"s shown here on line 6 ((1,5),(2,5) and (3,5) in Funge-Space) are actually be U+0001 in the source code. This is reflected correctly in TIO.

I may be able to save some bytes by moving those storage characters to line 1 or 2, and send line 6 left and wrap it, and if I can find a way to reduce the number of "g"s required to get the incremented values.

I'll do a nice writeup for this when I have time.

\$\endgroup\$
1
\$\begingroup\$

Python 3, 112 104 bytes

lambda n,r=range:{(*sorted((i,j,k)),)for i in r(1,n+1)for j in r(1,n+1)for k in r(1,n+1)if i*i+j*j==k*k}

Literally the same thing as the other answers.

\$\endgroup\$
1
\$\begingroup\$

Python, 98 bytes

Two solutions already exist for Python, but this one uses a slightly different approach that I thought might be informative:

from itertools import *
lambda n:[(k,j,i)for(k,j,i)in combinations(range(0,n+1),3)if i*i==j*j+k*k]
\$\endgroup\$
1
\$\begingroup\$

Brachylog, 13 bytes

⟦₁⊇Ṫ.^₂ᵐṅᵗ+0∧

Try it online!

Explanation

This is a generator, which will unify with each triplet.

⟦₁                 Range [1, …, N]
  ⊇Ṫ.              Subset of 3 elements
     .^₂ᵐ          Square each element
         ṅᵗ        Negate the last one (which is the biggest)
           +0∧    The sum must be 0

Much faster, 19 bytes

≥~hṪ≥₁ℕ₁ᵐ^₂ᵐṅʰ+0∧Ṫ≜

Try it online!

Takes about 1.5s for N = 200 on TIO. This uses integer constraint programming mechanisms which is way more efficient than brute forcing combinations in a range, but is longer to express in this case.

≥~hṪ                 A triplet of elements whose head is smaller than N
    ≥₁               The triplet is non-increasing
      ℕ₁ᵐ            Each element is in [1, +inf)
         ^₂ᵐ         Map square
            ṅʰ       Negate the first element
              +0∧    The sum must be 0
                 Ṫ≜  Assign values to satisfy these constraints
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 113 + 7 bytes

Compiled with -lm -DM=<input>

r,s,t;main(){for(;s<M;)for(t=++s;(r=sqrt(2*s*++t))<M;)r-sqrt(2*s*t)||(r+=s+t)>M||printf("%d %d %d\n",r-t,r-s,r);}

Try it online!

\$\endgroup\$
1
0
\$\begingroup\$

JavaScript 72 bytes

c=>{for(a=b=c;c;--a||(a=--b)||(a=b=--c))c*c-b*b-a*a||console.log(c,b,a)}

Formatted:

c => {
  for( a=b=c; c; /* until c is 0 */
     /* count down a, when a==0 reduce b and reset a=b, the same with c */
      --a || (a = --b) || (a = b = --c)
    )
    /* if c²-b²-a² == 0 log the tuple */
    c*c - b*b - a*a || console.log(c,b,a)
}

Try it online

\$\endgroup\$
0
\$\begingroup\$

Haskell, 56 bytes

q l=[(a,b,c)|c<-[1..l],a<-[1..c],b<-[a..l],a^2+b^2==c^2]

Try it online!

\$\endgroup\$
0
\$\begingroup\$

jq, 85 78 bytes

[range(3;.)]|combinations(3)|select(map(pow(.;2))|.[0]==.[1]+.[2]and.[1]>.[2])

Try it online! Try it online!

Generates all triples, then filters.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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