Triangles with rational side lengths

JavaScript (ES6),  188 184  183 bytes


Try it online!


Given \$n\$, we look for all pairs \$(x,y)\$ defined as:

$$x=\dfrac{a}{n},\:1\le a <n$$ $$y=\dfrac{p}{P},\:1\le p < P \le n$$

For each pair \$(x,y)\$, we compute \$z=1-x-y\$.

The triplet \$(x,y,z)\$ is valid if all the following conditions are met:

  • \$a\$ and \$n\$ are coprime
  • there is some \$Q,\:1\le Q \le n\$ such that \$Qz\$ is an integer
  • we have \$x+y>z\$, \$x+z>y\$ and \$y+z>x\$


NB: this is the 184-byte version, which is slightly more readable

n => {                       // n = input
  for(                       // 1st loop:
    o = r = [],              //   o = lookup object, r = output counter
    a = n; x = --a / n;      //   go from a = n - 1 to 1
  )                          //   and define x = a / n
  for(                       // 2nd loop:
    P = n; P; P--            //   go from P = n to 1
  )                          //
  for(                       // 3rd loop:
    p = P; y = --p / P;      //   go from p = P - 1 to 1
  )                          //   and define y = p / P
  for(                       // 4th loop:
    Q = n; Q;                //   go from Q = n to 1
  ) (                        //
      z = Q - x * Q - y * Q, //   define z = Q(1 - x - y)
      g = (a, b) =>          //   g is a helper function which
        b ?                  //     recursively computes the GCD
          g(b, a % b)        //     of 2 given integers
        :                    //
          a < 2              //     and returns true if it equals 1
    )(a, n) &                //   use it to figure out if a and n are coprime
    !(z % 1) &               //   make sure that z is an integer
    !o[                      //   make sure that the key k ...
      k = [x, y, z /= Q--]   //     ... made of [ x, y, z / Q ] ...
          .sort()            //     ... and sorted (lexicographically)
    ] &                      //   was not already found
    x + y > z &              //   make sure that all triangle inequalities
    x + z > y &              //   are fulfilled
    y + z > x ?              //   if all of the above is true:
      o[k] = ++r             //     increment r and save the key in o
    :                        //   else:
      0;                     //     do nothing
  return +r                  // return the final result
}                            //

05AB1E, 26 bytes


Brute-force approach, so extremely slow. Already times out for \$t(10)\$..

Try it online or verify the first 15 test cases (ã has been replaced with 2.Æʒ`¿} to speed things up slightly).


L              # Push a list in the range [1,(implicit) input]
 ã             # Get all pairs with these integers
  3ã           # Create all possible triplets of these pairs
    ʒ          # Filter this list of triplets by:
     à         #  Get the flattened maximum
      Q        #  And check that it's equal to the (implicit) input
    }€         # After the filter: map over each triplet:
      €        #  Map over each pair in this triplet:
       .«      #   Right-reduce this pair by:
         /     #    Dividing
     D         # Then duplicate the list of triplets
      O        # Sum each inner triplet
     Ï         # And only keep the triplets at the truthy (==1) indices
      €        # Map over each triplet of decimal values:
       {       #  Sort them from lowest to highest
        ʒ      # Filter the list of triplets further by:
         R     #  Reverse the triplet from highest to lowest
          `    #  Pop and push all three separated to the stack
           +   #  Add the top two (the lowest two) together
            ‹  #  And check that they're larger than the highest one
        }Ù     # After this filter: uniquify the list of triplets
          g    # And pop and push its length
               # (after which this is output implicitly as result)

Here all the rules, and which piece of codes covers them:

  • The triangles have a perimeter of 1: DOÏ
  • The triangles have side lengths \$\displaystyle\frac{a_1}{b_1}, \frac{a_2}{b_2}\$, and \$\displaystyle\frac{a_3}{b_3}\$, and when written in lowest terms, \$\max(b_1, b_2, b_3) = n\$: ʒàO}
  • The triangles are not degenerate, thus \$a+b>c\land a+c>b\land b+c>a\$: €{ʒR`+‹} (after sorting \$[a,b,c]\$ in descending order, we can check whether \$a<b+c\$)

The other pieces of code are to generate all possible triplets of pairs: Lã3ã; actually getting their decimal values: €€.«/; and counting the final amount of triplets that are valid: g. The uniquify Ù is to filter out duplicated triplets which are in a different order from the .

Explanation of the snippet that slightly sped up the test suite:

 2.Æ         # Get all possible pairs in ascending order with unique values
    ʒ        # Filter this list of pairs by:
     `       #  Pop and push both values separated to the stack
      ¿      #  Get the greatest common divisor between the two: gcd(a,b)
             #  (Note: only 1 is truthy in 05AB1E, so this filter checks that the
             #   fraction cannot be lowered in terms any further)
    }        # Close the filter
             # (Now there are less pairs we create triplets with and have to check in
             #  the other filters)

Python 3, 190 bytes

lambda x:sum(1for a,b,c in i.product(*[q(range(1,x+1))]*3)if{a,b,c}&q([x])and a<=b<=c<1==a+b+c>2*c)
q=lambda a:{x/y for y in a for x in range(y)if math.gcd(x,y)<2}
import math,itertools as i

Try it online!

The fraction part is just so it doesn't run into precision errors. It also makes it really slow though; this causes test case 20 (and supposedly later ones) to fail if disabled but uncomment it if you want to test larger numbers (though TIO won't be able to do it in time anyway; 20 takes about 10 minutes I believe).