Triángulos enteros con perímetro menor que n

13

Definición

Un "triángulo entero" es uno con coordenadas enteras. Por ejemplo, el siguiente triángulo es un triángulo entero:

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

Tarea

El objetivo de este desafío es contar todos los triángulos enteros (hasta la congruencia) con un perímetro menor que n.

Entrada y salida

El argumento se dará como un entero, y la salida debe ser el número de triángulos con un perímetro estrictamente menor que el argumento.

Ejemplos

El triángulo entero más pequeño por perímetro es congruente con

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

Los siguientes más pequeños son:

(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

Casos de prueba:

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

Tengo coordenadas para cada uno de los triángulos en este Gist .

Advertencias

Observe que dos triángulos no congruentes pueden tener el mismo perímetro:

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

También tenga en cuenta que la desigualdad es estricta ; el triángulo pitagórico 3-4-5 debe contarse con un (13), no un (12).

Puntuación

Este es el el código más corto gana!

Peter Kagey
fuente
44
Felicitaciones por encontrar una secuencia fácil de describir que no está en OEIS.
AdmBorkBork
1
Tengo un borrador para una secuencia relacionada presentado a la OEIS.
Peter Kagey el
1
(0, 0), (0, 1), (1, 0) tiene un perímetro 2 + sqrt (2) ≈ 3.14
gggg
1
Sí, los triángulos degenerados como (0,0), (1,1), (2,2) no se cuentan.
Peter Kagey el
1
¿Puede la entrada ser un valor entero en un tipo de punto flotante, o tiene que ser también de un tipo integral?
Precioso

Respuestas:

7

Jalea , 28 27 25 23 bytes

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

Pruébalo en línea!

Cómo funciona

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.
Dennis
fuente
4

Jalea ,  38  33 bytes

-1 gracias a Erik the Outgolfer (invierte SP¬+÷/E$usando SẠ>÷/E$y usando en ÇÐflugar de ÇÐḟ) -1 gracias a Mr. Xcoder (no es necesario aplanar antes de la clasificación)
-2 gracias a Mr. Xcoder ( S<¥Ðf³L-> S€<³S)
-1 robando un truco una revisión anterior de la respuesta de Dennis ( ṗ2’Œc-> p`⁺’- ¡casos más redundantes pero más golfistas!)

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

Un programa completo que toma un número entero e imprime el resultado.

Pruébalo en línea! (demasiado lento para completar casos de prueba 20+ en menores de 60 años)

¿Cómo?

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
Jonathan Allan
fuente
Explicación correcciones: [(a+c)×(b+d)]-> (a+c)×(b+d), [c÷a,d÷b]-> [a÷c,b÷d], c÷a==d÷b-> a÷c==b÷d, " c÷a==d÷b-> " a÷c==b÷d. Función .
Erik the Outgolfer
Además, buen abuso de nan.
Erik the Outgolfer
Gracias. Desafortunadamente, todavía necesita los resultados SP¬y no abusa de la división por cero (supongo que podría ser explícito con un real o)
Jonathan Allan
1
En realidad, puedes reemplazar ¬+con <. (EDIT: no es necesario reemplazar Pcon , ya que sólo está utilizando coordenadas no negativos.)
Erik el Outgolfer
Eso no funciona ( 7vuelve, 21por ejemplo)
Jonathan Allan
3

JavaScript (ES7), 157 bytes

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)

Casos de prueba

Solo se pueden calcular valores pequeños con el tamaño de pila predeterminado de la mayoría de los motores JS.


Versión no recursiva, 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)

Casos de prueba

Esta versión también funciona para un (30) y un (40) , pero eso tomaría demasiado tiempo para el fragmento.

Arnauld
fuente
2

Julia 0.6 , 135 bytes

Itere sobre los posibles puntos que no son de origen para formar el triángulo, los representa como números complejos, clasifica las longitudes de los cuadrados y los mantiene en un conjunto para verificar la congruencia. Evita los puntos colineales al verificar que el ángulo entre sus números complejos no sea cero. Luego devuelve la longitud del conjunto. Es más corto usar las longitudes directamente, pero obtienes la respuesta incorrecta a(40). La solución es demasiado lenta para llegar a ejecutarse a(40)debido a una advertencia de desaprobación, por lo que también tengo un enlace a una versión más rápida.

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

Pruébalo en línea!

Versión más rápida y más larga con desuso evitado. Pruébalo en línea! Usos sqrt.(g)en lugar de obsoletos √gpara la raíz cuadrada de elementwise.

gggg
fuente
1

Limpio , 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]

Pruébalo en línea!

Detecta triángulos congruentes mediante la comparación de los tres valores que suman para hacer el perímetro, y los puntos colineales al verificar que los dos valores más pequeños no suman el tercero.

Aquí hay una versión que utiliza un enfoque más rápido y con más memoria: ¡ Pruébelo en línea!

Οurous
fuente
Si cambio a Start = @ 12.0No obtengo ningún resultado, ¿estoy haciendo algo mal?
gggg
1
prueba @gggg al contenido de su corazón ahora
Οurous