Definition

Ein "ganzzahliges Dreieck" ist eines mit ganzzahligen Koordinaten. Das folgende Dreieck ist beispielsweise ein ganzzahliges Dreieck:

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

Aufgabe

Ziel dieser Herausforderung ist es, alle ganzzahligen Dreiecke (bis zur Kongruenz) mit einem Umfang von weniger als n zu zählen.

Ein- und Ausgang

Das Argument wird als Ganzzahl angegeben, und die Ausgabe sollte die Anzahl der Dreiecke sein, deren Umfang strikt kleiner ist als das Argument.

Beispiele

Das kleinste ganzzahlige Dreieck pro Umfang ist kongruent zu

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

Die nächstkleineren sind:

(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

Testfälle:

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

Ich habe Koordinaten für jedes der Dreiecke in diesem Gist .

Warnungen

Beachten Sie, dass zwei nicht kongruente Dreiecke denselben Umfang haben können:

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

Denken Sie auch daran, dass die Ungleichung streng ist ; Das 3-4-5-Pythagoras-Dreieck sollte mit einem (13) und nicht mit einem (12) gezählt werden.

Wertung

Das ist Code-Golf - der kürzeste Code gewinnt!

Jelly , 28 27 25 23 Bytes

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

Probieren Sie es online!

Wie es funktioniert

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.

Jelly ,  38  33 Bytes

-1 Dank an Erik den Outgolfer (invertiere SP¬+÷/E$durch Verwenden SẠ>÷/E$und Verwenden ÇÐfanstatt ÇÐḟ) -1 Dank an Mr. Xcoder (keine Notwendigkeit, vor dem Sortieren
zu reduzieren ) -2 Dank an Mr. Xcoder ( S<¥Ðf³L-> S€<³S)
-1 Stehlen eines Tricks von eine frühere Überarbeitung von Dennis 'Antwort ( ṗ2’Œc-> p`⁺’- überflüssigere Fälle, aber golferischer!)

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

Ein vollständiges Programm, das eine Ganzzahl aufnimmt und das Ergebnis druckt.

Probieren Sie es online! (zu langsam, um Testfälle über 20 in unter 60 Jahren abzuschließen)

Wie?

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 Byte

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)

Testfälle

Mit der Standardstapelgröße der meisten JS-Engines können nur kleine Werte berechnet werden.

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

Nicht rekursive Version, 165 Bytes

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)

Testfälle

Diese Version funktioniert auch für eine (30) und eine (40) , aber das würde für das Snippet zu viel Zeit in Anspruch nehmen.

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 Bytes

Durchlaufen Sie mögliche Nichtursprungspunkte, um das Dreieck zu bilden, stellen Sie sie als komplexe Zahlen dar, sortieren Sie die quadratischen Längen und halten Sie sie in einem Satz, um die Kongruenz zu überprüfen. Vermeidet kolineare Punkte, indem überprüft wird, ob der Winkel zwischen ihren komplexen Zahlen ungleich Null ist. Dann wird die Länge des Sets zurückgegeben. Es ist kürzer, die Längen direkt zu verwenden, aber Sie erhalten die falsche Antwort für a(40). Die Lösung ist zu langsam, um ausgeführt zu werden, a(40)da eine Warnung wegen Verfalls angezeigt wird. Daher habe ich auch einen Link zu einer schnelleren Version.

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

Probieren Sie es online!

Eine schnellere, längere Version mit Verfall wird vermieden. Probieren Sie es online! Verwendet sqrt.(g)anstelle von veraltet √gfür elementweise Quadratwurzel.

Sauber , 227 ... 143 Bytes

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]

Probieren Sie es online!

Erkennt kongruente Dreiecke durch Vergleichen der drei Werte, die den Umfang ergeben, und der kolinearen Punkte, indem überprüft wird, dass die beiden kleinsten dieser Werte nicht zur dritten addiert werden.

Hier ist eine Version, die einen schnelleren, speicherintensiveren Ansatz verwendet: Probieren Sie es online aus!