Определение

«Целочисленный треугольник» - это целочисленный треугольник. Например, следующий треугольник является целочисленным треугольником:

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

задача

Цель этой задачи - подсчитать все целочисленные треугольники (с точностью до конгруэнтности) с периметром меньше n.

Вход и выход

Аргумент будет задан как целое число, а на выходе должно быть количество треугольников с периметром, строго меньшим, чем аргумент.

Примеры

Наименьший целочисленный треугольник по периметру совпадает с

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

Следующие самые маленькие:

(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

Тестовые случаи:

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

У меня есть координаты для каждого из треугольников в этом Гисте .

Предупреждения

Обратите внимание, что два неконгруэнтных треугольника могут иметь одинаковый периметр:

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

Также имейте в виду, что неравенство строго ; 3-4-5 пифагорейский треугольник следует считать как (13), а не (12).

счет

Это код-гольф - выигрывает самый короткий код!

Желе , 28 27 25 23 байта

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

Попробуйте онлайн!

Как это устроено

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.

Желе ,  38  33 байта

-1 благодаря Erik the Outgolfer (инвертировать SP¬+÷/E$с помощью SẠ>÷/E$и использовать, ÇÐfа не ÇÐḟ) -1 благодаря Mr. Xcoder (нет необходимости выравнивать перед сортировкой)
-2 благодаря Mr. Xcoder ( S<¥Ðf³L-> S€<³S)
-1 украл трюк у более ранний пересмотр ответа Денниса ( ṗ2’Œc-> p`⁺’- более избыточные случаи, но игра в гольф!)

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

Полная программа, принимающая целое число и печатающая результат.

Попробуйте онлайн! (слишком медленно, чтобы завершить контрольные примеры 20+ в возрасте до 60 лет)

Как?

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 байт

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)

Контрольные примеры

Только небольшие значения могут быть вычислены с размером стека по умолчанию большинства механизмов 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)))

Нерекурсивная версия, 165 байт

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)

Контрольные примеры

Эта версия также работает для (30) и (40) , но это займет слишком много времени для фрагмента.

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

Юлия 0.6 , 135 байтов

Выполните итерацию по возможным точкам, не являющимся источником, чтобы составить треугольник, представить их как комплексные числа, отсортировать квадратные длины и сохранить их в наборе для проверки на соответствие. Избегайте коллинеарных точек, проверяя, что угол между их комплексными числами не равен нулю. Затем он возвращает длину набора. Короче использовать длины напрямую, но вы получите неправильный ответ a(40). Решение слишком медленное, чтобы запустить его a(40)из-за предупреждения об устаревании, поэтому у меня есть ссылка и на более быструю версию.

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

Попробуйте онлайн!

Более быстрая, более длинная версия с устаревшим избеганием. Попробуйте онлайн! Используется sqrt.(g)вместо устаревших √gдля поэлементного квадратного корня.

Чисто , 227 ... 143 байта

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]

Попробуйте онлайн!

Обнаруживает конгруэнтные треугольники, сравнивая три значения, которые составляют сумму периметра, и коллинеарные точки, проверяя, что два наименьших таких значения не суммируют с третьим.

Вот версия, которая использует более быстрый и более требовательный к памяти подход: попробуйте онлайн!