Définition

Un "triangle entier" est un triangle avec des coordonnées entières. Par exemple, le triangle suivant est un triangle entier:

(0, 0), (0, 1), (1, 2) with perimeter 1 + sqrt(2) + sqrt(5) ≈ 4.650.

Tâche

Le but de ce défi est de compter tous les triangles entiers (jusqu'à la congruence) avec un périmètre inférieur à n.

Entrée et sortie

L'argument sera donné sous forme d'entier et la sortie devrait être le nombre de triangles dont le périmètre est strictement inférieur à l'argument.

Exemples

Le plus petit triangle entier par périmètre est congru à

(0, 0), (0, 1), (1, 0) which has perimeter 2 + sqrt(2) ≈ 3.414

Les prochains plus petits sont:

(0, 0), (0, 1), (1, 2) with perimeter 1 + sqrt(2) + sqrt(5) ≈ 4.650,
(0, 0), (0, 2), (1, 1) with perimeter 2 + 2sqrt(2)          ≈ 4.828,
(0, 0), (0, 2), (1, 0) with perimeter 3 + sqrt(5)           ≈ 5.236, and
(0, 0), (1, 2), (2, 1) with perimeter sqrt(2) + 2sqrt(5)    ≈ 5.886

Cas de test:

a(1) = 0
a(2) = 0
a(3) = 0
a(4) = 1
a(5) = 3
a(6) = 5
a(7) = 11
a(8) = 18
a(9) = 29
a(10) = 44
a(12) = 94
a(20) = 738
a(30) = 3756
a(40) = 11875

J'ai des coordonnées pour chacun des triangles de ce Gist .

Avertissements

Notez que deux triangles non congruents peuvent avoir le même périmètre:

(0, 0), (0, 3), (3, 0) and (0, 0), (0, 1), (3, 4) both have perimeter 6 + 3sqrt(2).

Gardez également à l’esprit que l’inégalité est stricte ; le triangle pythagoricien 3-4-5 doit être compté par un (13), pas un (12).

Notation

Voici le code-golf : le code le plus court gagne!

Gelée , 28 27 25 23 octets

pḶŒcÆḊÐfḅı;I$€AṢ€QS€<¹S

Essayez-le en ligne!

Comment ça fonctionne

pḶŒcÆḊÐfḅı;I$€AṢ€QS€<¹S  Main link. Argument: n

 Ḷ                       Unlength; yield [0,...,n-1].
p                        Take the Cartesian product of [1,...,n] and [0,...,n-1].
  Œc                     Take all combinations of the resulting pairs.
                         The result are of the form [[a, b], [c, d]].
    ÆḊÐf                 Filter by determinant; keep only pairs of pairs for which
                         the determinant (ad - bc) is non-zero, i.e., those such
                         that [0, 0], [a, b], and [c, d] are not collinear.
        ḅı               Convert each pair [a, b] from base i (imaginary unit) to
                         integer, mapping it to ai + b.
             €           For each pair of complex numbers [p, q]: 
          ;I$              append their forward differences, yielding [p, q, p-q].
              A          Take the absolute value of each resulting complex number.
               Ṣ€        Sort each resulting array of side lengths.
                 Q       Unique; remove duplicates.
                  S€     Take the sum of each array, computing the perimeters.
                    <¹   Compare them with n.
                      S  Take the sum of the resulting Booleans.

Gelée ,  38  33 octets

-1 merci à Erik l'Outgolfer (inverser SP¬+÷/E$en utilisant SẠ>÷/E$et utiliser ÇÐfplutôt que ÇÐḟ) -1 merci à Mr. Xcoder (pas besoin d'aplatir avant le tri)
-2 merci à Mr. Xcoder ( S<¥Ðf³L-> S€<³S)
-1 voler un truc à une révision antérieure de la réponse de Dennis (ṗ2’Œc -> p`⁺’- cas plus redondants mais golfeur!)

SẠ>÷/E$
p`⁺’ÇÐfµ_/ṭ⁸²S€Ṣµ€Q½S€<³S

Un programme complet prenant un entier et imprimant le résultat.

Essayez-le en ligne!(trop lent pour terminer les cas de test 20+ en moins de 60 ans)

Comment?

SẠ>÷/E$ - Link 1, straightLineFromOrigin?: coordinates       i.e. [[a,b],[c,d]]
S       - sum                                                     [a+c,b+d]
 Ạ       - all? (0 if either of a+c or b+d are 0 otherwise 1)      all([a+c,b+d])
      $ - last two links as a monad:
   ÷/   -   reduce by division                                    [a÷c,b÷d]
     E  -   all equal?  (i.e. 1 if on a non-axial straight line)  a÷c==b÷d 
  >     - greater than? (i.e. 1 if not on any line, 0 otherwise)  all([a+c,b+d])>(a÷c==b÷d)

p`⁺’ÇÐḟµ_/ṭ⁸²S€Ṣµ€Q½S€<³S - Main link: integer, n
p`                        - Cartesian product of implicit range(n) with itself
  ⁺                       - repeat (Cartesian product of that result with itself)
   ’                      - decrement (vectorises)
                          -  - i.e. all non-negative lattice point pairs up to x,y=n-1
     Ðf                   - filter keep only if:
    Ç                     -   call last link (1) as a monad
       µ         µ€       - monadic chain for €ach:
        _/                -   reduce with subtraction i.e. [a-c,b-d]
           ⁸              -   chain's left argument, [[a,b],[c,d]]
          ṭ               -   tack                   [[a,b],[c,d],[c-a,d-b]]
            ²             -   square (vectorises)    [[a²,b²],[c²,d²],[(c-a)²,(d-b)²]]
             S€           -   sum €ach               [[a²+b²],[c²+d²],[(c-a)²+(d-b)²]]
                          -    - i.e. the squares of the triangle's edge lengths
               Ṣ          -   sort
                  Q       - de-duplicate (get one of each congruent set of triangles)
                   ½      - square root (vectorises)  - get sides from squares of sides
                    S€    - sum €ach
                       ³  - program's 3rd argument, n
                      <   - less than?
                        S -   sum (number of such triangles)
                          - implicit print

JavaScript (ES7), 157 octets

f=(n,i=n**4,o={})=>i--&&([p,P,q,Q]=[0,1,2,3].map(k=>i/n**k%n|0),!o[k=[a=(H=Math.hypot)(p,P),b=H(p-q,P-Q),c=H(q,Q)].sort()]&a+b+c<n&&(o[k]=P*q!=p*Q))+f(n,i,o)

Cas de test

Seules de petites valeurs peuvent être calculées avec la taille de pile par défaut de la plupart des moteurs JS.

f=(n,i=n**4,o={})=>i--&&([p,P,q,Q]=[0,1,2,3].map(k=>i/n**k%n|0),!o[k=[a=(H=Math.hypot)(p,P),b=H(p-q,P-Q),c=H(q,Q)].sort()]&a+b+c<n&&(o[k]=P*q!=p*Q))+f(n,i,o)

;[
  1,  // 0
  2,  // 0
  3,  // 0
  4,  // 1
  5,  // 3
  6,  // 5
  7,  // 11
  8,  // 18
  9   // 29
]
.forEach(n => console.log('a(' + n + ') = ' + f(n)))

Version non récursive, 165 octets

n=>[...Array(n**4)].reduce((x,_,i,o)=>x+=!o[[p,P,q,Q]=[0,1,2,3].map(k=>i/n**k%n|0),k=[a=(H=Math.hypot)(p,P),b=H(p-q,P-Q),c=H(q,Q)].sort()]&(o[k]=P*q!=p*Q)&a+b+c<n,0)

Cas de test

Cette version fonctionne également pour un (30) et un (40) , mais cela prendrait trop de temps pour l'extrait.

let f =

n=>[...Array(n**4)].reduce((x,_,i,o)=>x+=!o[[p,P,q,Q]=[0,1,2,3].map(k=>i/n**k%n|0),k=[a=(H=Math.hypot)(p,P),b=H(p-q,P-Q),c=H(q,Q)].sort()]&(o[k]=P*q!=p*Q)&a+b+c<n,0)

;[
  1,  // 0
  2,  // 0
  3,  // 0
  4,  // 1
  5,  // 3
  6,  // 5
  7,  // 11
  8,  // 18
  9,  // 29
  10, // 44
  12, // 94
  20  // 738
]
.forEach(n => console.log('a(' + n + ') = ' + f(n)))

Julia 0,6 , 135 octets

Itérer sur les points non d'origine possibles pour constituer le triangle, les représenter sous forme de nombres complexes, trier les longueurs carrées et les conserver dans un ensemble pour vérifier la congruence. Évite les points colinéaires en vérifiant que l'angle entre leurs nombres complexes n'est pas nul. Il renvoie ensuite la longueur de l'ensemble. Il est plus court d'utiliser directement les longueurs, mais vous obtenez la mauvaise réponse a(40). La solution est trop lente pour être exécutée en a(40)raison d'un avertissement de dépréciation, j'ai donc un lien vers une version plus rapide également.

n->(q=Set();for x=0:n,y=1:n,a=1:n,b=0:n
r=x+y*im
t=a+b*im
g=sort(abs2.([r,t,r-t]))
sum(√g)<n&&angle(r/t)>0&&push!(q,g)
end;length(q))

Essayez-le en ligne!

Version plus rapide et plus longue avec dépréciation évitée. Essayez-le en ligne! Utilise sqrt.(g)à la place de obsolète √gpour la racine carrée élément par élément.

Nettoyer , 227 ... 143 octets

import StdEnv
@n#l=[0.0..n]
=sum[1\\p<-removeDup[sort(map(sqrt o\[u,v]=u*u+v*v)[[a-i,b-j],[a,b],[i,j]])\\a<-l,b<-l,i<-l,j<-l|a*j<>i*b]|sum p<n]

Essayez-le en ligne!

Détecte les triangles congruents en comparant les trois valeurs qui s'additionnent pour faire le périmètre et les points colinéaires en vérifiant que les deux plus petites de ces valeurs ne s'additionnent pas à la troisième.

Voici une version qui utilise une approche plus rapide et plus gourmande en mémoire: essayez-la en ligne!