18
\$\begingroup\$

This challenge will have give you a positive integer \$n\$ and ask you to output \$t(n)\$, the number of triangles (up to congruence) satisfying the three conditions:

  • The triangles have perimeter of 1,
  • 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\$.

Examples

For \$n = 2\$, there are no such triangles, so \$t(2) = 0\$.

For \$n = 3\$, there is one such triangle, so \$t(3) = 1\$: $$ \frac{a_1}{b_1} = \frac{a_2}{b_2} = \frac{a_3}{b_3} = \frac 1 3 $$ For \$n = 4\$, there are no such triangles, so \$t(4) = 0\$.

For \$n = 5\$, there is one such triangle, so \$t(5) = 1\$: $$ \left(\frac{a_1}{b_1}, \frac{a_2}{b_2}, \frac{a_3}{b_3}\right) = \left(\frac 1 5, \frac 2 5, \frac 2 5\right) $$

For \$n = 6\$, there are no such triangles, so \$t(6) = 0\$.

For \$n = 7\$, there are two such triangles, so \$t(7) = 2\$: $$ \left(\frac{a_1}{b_1}, \frac{a_2}{b_2}, \frac{a_3}{b_3}\right) = \left(\frac 2 7, \frac 2 7, \frac 3 7\right) \hspace{1em} \text{and} \hspace{1em} \left(\frac{a_1}{b_1}, \frac{a_2}{b_2}, \frac{a_3}{b_3}\right) = \left(\frac 1 7, \frac 3 7, \frac 3 7\right) $$

For \$n = 8\$, there is one such triangle, so \$t(8) = 1\$: $$ \left(\frac{a_1}{b_1}, \frac{a_2}{b_2}, \frac{a_3}{b_3}\right) = \left(\frac 1 4, \frac 3 8, \frac 3 8\right) $$

The first thirty pairs, \$\left(n, t(n)\right)\$ are:

(1,0),(2,0),(3,1),(4,0),(5,1),(6,0),(7,2),(8,1),(9,2),(10,1),(11,4),(12,2),(13,5),(14,2),(15,5),(16,4),(17,8),(18,4),(19,10),(20,8),(21,10),(22,6),(23,14),(24,8),(25,15),(26,9),(27,16),(28,14),(29,21),(30,13)

This is a challenge, so shortest code wins.

\$\endgroup\$
10
  • \$\begingroup\$ Is it any different from counting integer-sided triangles of perimeter n? \$\endgroup\$
    – Bubbler
    Oct 16, 2020 at 5:57
  • 1
    \$\begingroup\$ @Bubbler, it is different! For example, there is an integer-sided triangle with perimeter 6. \$\endgroup\$ Oct 16, 2020 at 6:01
  • 1
    \$\begingroup\$ Oh, right. I was thinking of a harder counterexample, something like 5/12, 2/15, 9/20, where common denominator is actually larger than n. \$\endgroup\$
    – Bubbler
    Oct 16, 2020 at 6:06
  • 2
    \$\begingroup\$ @NahuelFouilleul I guess degenerate triangles are excluded. (But this should be specified.) \$\endgroup\$
    – Arnauld
    Oct 16, 2020 at 9:10
  • 2
    \$\begingroup\$ @KevinCruijssen Sorry, I was on mobile and gave you a solution that is actually not a triangle. A valid one is 9/20 + 1/12 + 7/15. \$\endgroup\$
    – Arnauld
    Oct 16, 2020 at 12:44

5 Answers 5

8
\$\begingroup\$

JavaScript (ES6),  188 184  183 bytes

n=>{for(o=r=[],a=n;x=--a/n;)for(P=n;P;P--)for(p=P;y=--p/P;)for(Q=n;Q;)!(z=Q-x*Q-y*Q,g=(a,b)=>b?g(b,a%b):z%1||a>1)(a,n)&!o[k=[x,y,z/=Q--].sort()]&x+y>z&x+z>y&y+z>x?o[k]=++r:0;return+r}

Try it online!

How?

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\$

Commented

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
}                            //
\$\endgroup\$
6
\$\begingroup\$

05AB1E, 26 bytes

Lã3ãʒàQ}€€.«/DOÏ€{ʒR`+‹}Ùg

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).

Explanation:

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)
\$\endgroup\$
5
\$\begingroup\$

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).

\$\endgroup\$
2
  • 1
    \$\begingroup\$ @Arnauld I'm pretty sure it's a precision error lol, I tried debugging by getting my outputs as Fraction objects and the number changed to 8. \$\endgroup\$
    – hyper-neutrino
    Oct 16, 2020 at 9:13
  • 1
    \$\begingroup\$ Yes, I'm pretty sure your code is otherwise correct. \$\endgroup\$
    – Arnauld
    Oct 16, 2020 at 10:42
3
\$\begingroup\$

Charcoal, 135 bytes

NθFΦθ∧ι¬﹪÷X²×ιθ⊖X²θ⊖X²ιF…·²θFΦκ∧λ¬﹪÷X²×λκ⊖X²κ⊖X²λF…·²θFΦμ∧ν¬﹪÷X²×νμ⊖X²μ⊖X²ν«≔××θκμη≔⟦×ι×κμ×λ×θμ×ν×θκ⟧ζ≔⟦η⌊ζ⌈ζ⟧ε¿∧∧⁼ηΣζ‹⊗⌈ζΣζ¬№υε⊞υε»ILυ

Try it online! Link is to verbose version of code. Explanation:

Nθ

Input \$ n \$. We'll assume \$ b_1=n \$ for now.

FΦθ∧ι¬﹪÷X²×ιθ⊖X²θ⊖X²ι

Loop for all values \$ 0<a_1<b_1 \$ such that \$ a_1 \$ and \$ b_1 \$ are coprime.

F…·²θ

Loop for all values \$ 2 \le b_2 \le n \$.

FΦκ∧λ¬﹪÷X²×λκ⊖X²κ⊖X²λ

Loop for all values \$ 0<a_2<b_2 \$ such that \$ a_2 \$ and \$ b_2 \$ are coprime.

F…·²θ

Loop for all values \$ 2 \le b_3 \le n \$.

FΦμ∧ν¬﹪÷X²×νμ⊖X²μ⊖X²ν«

Loop for all values \$ 0<a_3<b_3 \$ such that \$ a_3 \$ and \$ b_3 \$ are coprime.

≔××θκμη

Calculate a common denominator for the fraction \$ \frac {a_1} {b_1} + \frac {a_2} {b_2} + \frac {a_3} {b_3} \$.

≔⟦×ι×κμ×λ×θμ×ν×θκ⟧ζ

Calculate the numerators of the three fractions using the common denominator.

≔⟦η⌊ζ⌈ζ⟧ε

Get the denominator and minimum and maximum numerator. These don't depend on the order of the fractions, so will identify duplicates.

¿∧∧⁼ηΣζ‹⊗⌈ζΣζ¬№υε

Check that the numerators sum to the denominator (i.e. the perimeter is \$ 1 \$), that the largest numerator is less than half the sum (i.e. the triangle is not degenerate), and that the fractions haven't already been seen in a different order.

⊞υε

If all the tests pass then record this as a seen set of fractions.

»ILυ

Print the number of fractions found.

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

Perl 5, 241 bytes

sub{sub g{($a,$b)=@_;$b?g($b,$a%$b):$a}$r=0;for$a(@m=map{$N=$_;grep g(@$_)<2,map[$_,$N,$_/$N],1..$N-1}2..($n=pop)){for$b(@m){for(@m){($A,$B,$C)=map$$_[2],$a,$b,$_;$r++if$A<=$B&$B<=$C&1e-9>abs$A+$B+$C-1&$A+$B>$C&&grep$$_[1]==$n,$a,$b,$_}}}$r}

Try it online!

TIO times out at 60 seconds, it found 28 of the 30 test cases at that time. Very brute force.

sub t {
  $n=pop;                             #input number --> n
  sub g{($a,$b)=@_;$b?g($b,$a%$b):$a} #greatest common divisor,
                                      #about the worlds oldest algorithm
  $r=0;                               #result counter r
  @m=map {                            #m = list of 3-elem-arrays: nominator,
    $N=$_;                            #denominator and floating point fraction
    grep g(@$_)<2,                    #keep only irreducible fractions
   #grep g(@$_)<2&&g($$_[1],$n)>1,    #run faster with this grep but same result
    map [$_,$N,$_/$N], 1..$N-1        #all nominators 1 to N-1
  }
  2..$n;                              #with all denominators 2 to n
  for $a (@m){                        #loop through m on three levels a,b,c
    for $b (@m){
      for $c (@m){
        ($A,$B,$C)=map$$_[2],$a,$b,$c;#A,B,C is the fractions, side lengths
        $r++
          if $A<=$B                   #increase r result if length A < B
          && $B<=$C                   #and B < C lengths ABC sorted by length
          && 1e-9 > abs $A+$B+$C-1    #and A+B+C=1, taking care of f.p. errors
          && $A+$B > $C               #and A+B>C (not a trangle if not)
          && grep$$_[1]==$n,$a,$b,$_  #and at least one fraction must
                                      #have denominator = n
  }}}
  $r                                  #return result counter
}
\$\endgroup\$

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.