Pitagorasa potrójne składa się z trzech dodatnich liczb całkowitych a, b i c, tak, że ² + b ² = C ² . Taki potrójny jest powszechnie pisany (a, b, c), a dobrze znanym przykładem jest (3, 4, 5). Jeśli (a, b, c) jest potrójną pitagorejską, to tak samo jest (ka, kb, kc) dla dowolnej dodatniej liczby całkowitej k. Pierwotna Pitagorasa potrójna jest to, w którym A, B i C są względnie pierwsze .

Korzystając z tej wiedzy, możemy stworzyć sekwencję, łącząc ze sobą najmniejsze długości potrójnych elementów, przy czym następnym elementem w sekwencji jest przeciwprostokątna (największa liczba) najmniejszej prymagorejskiej potrójnej potrójnej zawierająca poprzedni element jako najmniejszą z jego długości.

Zacznij od najmniejszej pierwotnej potrójnej pitagorejskiej potrójnej (3, 4, 5). Sekwencja zaczyna się od 3, a przeciwprostokątna (następny element w sekwencji) to 5. Następnie znajdź najmniejszą prymitywną trójkę pitagorejską 5jako nogę, a otrzymasz (5, 12, 13). Tak więc sekwencja trwa 13.

Albo wypisuj sekwencję na zawsze, albo weź liczbę całkowitą ni wyślij pierwsze nelementy sekwencji, zero lub jeden indeksowany.

Musisz obsłużyć dane wyjściowe przynajmniej poprzez włącznie 28455997, ale jeśli nagle nagle zostanie przekroczony limit używanego typu danych, będzie musiał pracować dla tego nowego limitu. Nie można więc na stałe zakodować listy liczb.

3
5
13
85
157
12325
90733
2449525
28455997
295742792965
171480834409967437
656310093705697045
1616599508725767821225590944157
4461691012090851100342993272805
115366949386695884000892071602798585632943213
12002377162350258332845595301471273220420939451301220405

OEIS A239381

Podobne sekwencje (nie wysyłaj ich!):

• A018928
• A077034 (nieparzyste warunki)

Galaretka , 19 bajtów

o3ṄÆF*/€ŒPP€²+Ṛ$HṂß

Oszczędność bajtu dzięki @ Dennisowi poprzez refaktoryzację do nieskończonej sekwencji.

Nie bierze żadnych danych wejściowych i argumentów, a następnie generuje sekwencję nieskończenie, drukując każdy termin podczas ich obliczania. Ta metoda zwalnia, gdy liczby stają się większe, ponieważ zależy od faktoryzacji liczby pierwszej.

Wypróbuj online!

Oblicza to następny termin, obliczając faktoryzację mocy pierwotnej bieżącego terminu. Dla 12325 jest to {5 ² , 17, 29}. Istnieje wariant wzoru Euclida do obliczania trójek pitagorejskich { a , b , c },

gdzie m > n, a potrójna jest prymitywna iff m i n są pierwszymi.

W celu obliczenia następnego pierwiastkiem pierwotnym od 12325 online m i n , takich, że MN = 12325, a wybrać m , n , tak że GCD ( m , n ) = 1. Następnie generuje wszystkie pary m , n , tworząc wszystkie podzbiory {5 ² , 17, 29} i znalezienie produktu każdego z tych podzbiorów, które są {1, 25, 17, 29, 425, 725, 493, 12325}. Następnie podziel 12325 przez każdą wartość i parę, aby każda para miała m , n . Obliczyć wzór dla c przy użyciu każdej pary i przyjąć minimum, które wynosi 90733.

• Poprzednia metoda nie powiodła się do określenia następnego terminu po 228034970321525477033478437478475683098735674620405573717049066152557390539189785244849203205. Poprzednia metoda wybrała ostatnią wartość jako czynnik, gdy poprawnym wyborem była trzecia i ostatnia liczba pierwsza. Nowa metoda jest wolniejsza, ale zawsze będzie działać, ponieważ testuje wszystkie pary coprime w celu znalezienia minimalnej przeciwprostokątnej.

Wyjaśnienie

o3ṄÆF*/€ŒPP€²+Ṛ$HṂß  Main link. Input: 0 if none, else an integer P
o3                   Logical OR with 3, returns P if non-zero else 3
  Ṅ                  Println and pass the value
   ÆF                Factor into [prime, exponent] pairs
     */€             Reduce each pair using exponentation to get the prime powers
        ŒP           Powerset of those
          P€         Product of each
            ²        Square each
               $     Monadic chain
             +         Add vectorized with
              Ṛ        the reverse
                H    Halve
                 Ṃ   Minimum
                  ß  Call recursively on this value

Brachylog , 36 bajtów

3{@wB:?>:^a+~^=C:B:?:{$pd}ac#d,C:1&}

Wypróbuj online!

Musisz poczekać na przekroczenie limitu czasu programu (1 minuta), zanim TIO opróżni wyjście. W REPL SWI-Prologa drukuje się, jak tylko znajdzie wartość.

Spowoduje to wydrukowanie sekwencji na zawsze.

Po kilku minutach na offline tłumacza SWI-Prolog uzyskałem 90733 po 12325. Po tym punkcie przestałem.

To nie jest pełna bruteforce, ponieważ wykorzystuje ograniczenia, aby znaleźć tróje pitagorejskie, chociaż oczywiście nie jest zoptymalizowana pod kątem prędkości.

Wyjaśnienie

3{                                 }    Call this predicate with 3 as Input
  @w                                    Write the Input followed by a line break
    B:?>                                B > Input
           +                            The sum...
        :^a                             ...of Input^2 with B^2...
            ~^                          ...must equal a number which is itself a square
              =C                        Assign a fitting value to that number and call it C
               C:B:?:{$pd}a             Get the lists of prime factors of C, B and Input
                                          without duplicates
                           c#d,         Concatenate into a single list; all values must be
                                          different
                               C:1&     Call recursively with C as Input

Perl, 73 bajty

for($_=3;$_<1e9;$_=$a**2+$b**2){$a++until($b=($_+$a**2)**.5)==($b|0);say}

Wszystkie trójki pitagorejskie a²+b²=c²spełniają a=r(m²-n²), b=2rmn, c=r(m²+n²)niektóre liczby całkowite r,m,n. Kiedy r=1i m,nsą chronione prawem autorskim, przy czym dokładnie jeden jest podzielny przez 2, to a,b,cjest prymitywny potrójny, gdzie a,b,cwszystkie są chronione parami.

Mając to na uwadze, biorąc pod uwagę niektóre a, używam algorytmu brutalnej siły, aby obliczyć najmniejszy ntaki, a²-n²czyli kwadrat m². Zatem cjest równy n²+m².

Python 3, 178 bajtów

from math import*
p,n=[3,5],int(input())
while len(p)<n:
 for i in range(p[-1],p[-1]**2):
  v=sqrt(i**2+p[-1]**2)
  if v==int(v)and gcd(i,p[-1])==1:
   p+=[int(v)];break
print(p)

Jest to w zasadzie algorytm brutalnej siły, a zatem jest bardzo wolny. Dane wyjściowe wymagają ilości terminów.

Nie jestem w 100% pewien co do poprawności tego algorytmu, program sprawdza drugą nogę do pierwszej nogi do kwadratu, co moim zdaniem jest wystarczające, ale nie zrobiłem matematyki.

Wypróbuj na repl.it! (Nieaktualne) (Nie próbuj tego przy liczbach większych niż 10, będzie to bardzo powolne)

MATL , 27 bajtów

Ii:"`I@Yyt1\~?3MZdZdq]}6MXI

To tworzy pierwsze warunki sekwencji. Dane wejściowe są oparte na 0.

Kod jest bardzo nieefektywny. Limit czasu kompilatora online dla danych wejściowych większych niż 5. Wejście 6trwało półtorej minuty offline (i dało prawidłowy 90733jako szósty termin).

Wypróbuj online!

I            % Push 3 (predefined value of clipboard I)
i            % Input n
:"           % For each (i.e. execute n times)
  `          %   Do...while
    I        %     Push clipboard I. This is the latest term of the sequence
    @        %     Push iteration index, starting at 1
    Yy       %     Hypotenuse of those two values
    t1\      %     Duplicate. Decimal part
    ~?       %     If it is zero: we may have found the next term. But we still
             %     need to test for co-primality
      3M     %       Push the two inputs of the latest call to the hypotenuse 
             %       function. The stack now contains the hypotenuse and the
             %       two legs
      ZdZd   %       Call GCD twice, to obtain the GCD of those three numbers
      q      %       Subtract 1. If the three numbers were co-prime this gives
             %       0, so the do...while loop will be exited (but the "finally" 
             %       part will be executed first). If they were not co-prime  
             %       this gives non-zero, so the do...while loop proceeds 
             %       with the next iteration
    ]        %     End if
             %     If the decimal part was non-zero: the duplicate of the 
             %     hypotenuse that is now on the top of the stack will be used
             %     as the (do...while) loop condition. Since it is non-zero, 
             %     the loop will proceed with the next iteration
  }          %   Finally (i.e. execute before exiting the do...while loop)
    6M       %     Push the second input to the hypotenuse function, which is
             %     the new term of the sequence
    XI       %     Copy this new term into clipboard I
             %   Implicitly end do...while
             % Implicitly end for each
             % Implicitly display the stack, containing the sequence terms

Rakieta 106 bajtów

(let p((h 3))(println h)(let p2((i 1))(define g(sqrt(+(* h h)(* i i))))(if(integer? g)(p g)(p2(add1 i)))))

Nie golfowany:

(define (f)
  (let loop ((h 3))
    (let loop2 ((i 1))
      (define g (sqrt (+(* h h) (* i i))))
      (if (not(integer? g))
          (loop2 (add1 i))
          (begin (printf "~a ~a ~a~n" h i g)
                 (loop g))))))

Testowanie:

(f)

Wyjście wersji golfowej:

3
5
13
85
157
12325
12461
106285
276341
339709
10363909
17238541

Wyjście wersji bez golfa:

3 4 5
5 12 13
13 84 85
85 132 157
157 12324 12325
12325 1836 12461
12461 105552 106285
106285 255084 276341
276341 197580 339709
339709 10358340 10363909
10363909 13775220 17238541

(Błąd po tym na moim komputerze)

Wolfram Language (Mathematica) , 74 bajty

Nest[c/.#&@@Solve[{#^2+b^2==c^2,#<b<c&&GCD[b,c]==1},{b,c},Integers]&,3,#]&

Wypróbuj online!

Wolfram Language (Mathematica) , 74 bajty

Nest[#&@@Cases[Divisors@#,d_/;GCD[d,#/d]<2&&d^2>#:>(d^2+(#/d)^2)/2]&,3,#]&

Wypróbuj online!

PHP, 139 bajtów

for($k=3;$i=$k,print("$k\n");)for($j=$i+1;($k=sqrt($m=$i*$i+$j*$j))>(int)$k||gmp_intval(gmp_gcd(gmp_gcd((int)$i,(int)$j),(int)$k))>1;$j++);

Powyższy kod ulega awarii po 28455997 w systemach 32-bitowych. Jeśli potrzebne są wyższe liczby, staje się 156 bajtów:

for($k=3;$i=$k,print("$k\n");)for($j=$i+1;!gmp_perfect_square($m=bcadd(bcpow($i,2),bcpow($j,2)))||gmp_intval(gmp_gcd(gmp_gcd($i,$j),$k=bcsqrt($m)))>1;$j++);

Java 8, 133 bajtów

-25 bajtów dzięki milom milom Używając n * n zamiast Math.pow (n, 2)

-24 bajty dzięki mile Używanie pętli zamiast zamiast, zmiana typu danych, eliminacja () z powodu kolejności operacji

()->{long b=3,c,n;for(;;){for(n=1;;n++){c=b+2*n*n;double d=Math.sqrt(c*c-b*b);if(d==(int)d&b<d){System.out.println(b);break;}}b=c;}};

Wykorzystuje fakt, że

dla dowolnej pary liczb całkowitych m> n> 0. Dlatego C jest równe A plus 2 (N) ² . Funkcja powyżej znajduje najmniejszą wartość N, która spełnia tę relację, jednocześnie czyniąc drugi element pitagorejskiego potrójnym liczbą całkowitą i większą niż pierwszy element. Następnie ustawia wartość pierwszego elementu na trzeci element i powtarza się ze zaktualizowanym pierwszym elementem.

Nie golfowany:

void printPythagoreanTriples() {
    long firstElement = 3, thirdElement, n;
    while (true) {
        for (n = 1; ; n++) {
            thirdElement = firstElement + (2 * n * n);
            double secondElement = Math.sqrt(thirdElement * thirdElement - firstElement * firstElement);
            if (secondElement == (int) secondElement && firstElement < secondElement) {
                System.out.println("Found Pythagorean Triple [" +
                        firstElement + ", " +
                        secondElement + ", " +
                        thirdElement + "]");
                break;
            }
        }
        firstElement = thirdElement;
    }
}

Ideone to!

* Ideone nie drukuje ostatniego wymaganego elementu ze względu na ograniczenia czasowe, jak jednak można zobaczyć poprzez logikę programu i wersji bez golfa (która drukuje 28455997 jako trzeci element poprzedniej potrójnej pitagorejskiej zamiast pierwszego elementu następny), wartości są drukowane z wyższym limitem czasowym.

Python 3.5, 97 bajtów

Niepoprawny wynik po 28455997ze względu na ograniczenia typu danych zmiennoprzecinkowych. sqrtFunkcja nie jest wystarczająco dobre, ale jeśli zwiększona precyzja została magicznie, że to działa.

Całkiem prosty do zrozumienia. Zwiększenie co dwa zamiast jednego powoduje skrócenie czasu wykonywania o połowę, a mimo to należy sprawdzać tylko liczby nieparzyste, ponieważ elementy są zawsze nieparzyste.

import math
c=a=3
while 1:
	c+=2;b=(c*c-a*a)**.5;i=int(b)
	if math.gcd(a,i)<2<a<b==i:print(a);a=c

Wypróbuj online

Programu nie można uruchomić w Ideone, ponieważ Ideone używa Python 3.4

Aby dane wyjściowe pozostały dłużej dokładne, musiałbym użyć decimal:

import math
from decimal import*
c=a=3
while 1:
	c+=2;b=Decimal(c*c-a*a).sqrt();i=int(b)
	if i==b>a>2>math.gcd(a,i):print(a);a=c

Wypróbuj online

Aby zachować dokładność w nieskończoność, mogłem zrobić coś tak okropnego (zwiększenie precyzji wymaganej przy każdej iteracji :

import math
from decimal import*
c=a=3
while 1:
	c+=2;b=Decimal(c*c-a*a).sqrt();i=int(b);getcontext().prec+=1
	if i==b>a>2>math.gcd(a,i):print(a);a=c

J , 54 47 bajtów

-:@+/@:*:@((*/:~)/)@,.&1@x:@(^/)@(2&p:)^:(<12)3

TIO

chciwy podział czynników głównych na czynniki chroniące prawa autorskie

stare 54 bajty TIO

Pari / GP , 71 bajtów

n->a=3;for(i=1,n,a=[d^2+e^2|d<-divisors(a),gcd(d,e=a/d)<2&&d>e][1]/2);a

Wypróbuj online!

APL (NARS), 169 znaków, 338 bajtów

h←{{(m n)←⍵⋄(mm nn)←⍵*2⋄(2÷⍨nn+mm),(2÷⍨nn-mm),m×n}a⊃⍨b⍳⌊/b←{⍵[2]}¨a←a/⍨{(≤/⍵)∧1=∨/⍵}¨a←(w÷a),¨a←∪×/¨{k←≢b←1,π⍵⋄∪{b[⍵]}¨↑∪/101 1‼k k}w←⍵}⋄p←{⍺=1:⍵⋄⍵,(⍺-1)∇↑h ⍵}⋄q←{⍵p 3x}

testuj ok do 14 jako argument q:

  q 1
3 
  q 2
3 5 
  q 10
3 5 13 85 157 12325 90733 2449525 28455997 295742792965 
  q 12
3 5 13 85 157 12325 90733 2449525 28455997 295742792965 171480834409967437 656310093705697045 
  q 13
3 5 13 85 157 12325 90733 2449525 28455997 295742792965 171480834409967437 656310093705697045 
  1616599508725767821225590944157 
  q 14
NONCE ERROR
  q 14
  ∧

poniżej znajdują się wszystkie dzielniki jego argumentu ...

∪×/¨{k←≢b←1,π⍵⋄∪{b[⍵]}¨↑∪/101 1‼k k}

JavaScript (Node.js) , 101 bajtów

_=>{for(var a=3,b,c;;){for(c=1;;c++)if(b=a+2*c*c,d=Math.sqrt(b*b-a*a),d==+d&a<d){alert(a);break}a=b}}

Wypróbuj online!

Sugestie dotyczące gry w golfa są mile widziane