Sebuah Pythagoras tiga terdiri dari tiga bilangan bulat positif a, b, dan c, seperti bahwa ² + b ² = c ² . Triple seperti itu umumnya ditulis (a, b, c), dan contoh yang terkenal adalah (3, 4, 5). Jika (a, b, c) adalah triple Pythagoras, maka demikian juga (ka, kb, kc) untuk setiap bilangan bulat positif k. Triple Pythagoras primitif adalah yang memiliki a, b dan c adalah koprime .

Dengan menggunakan pengetahuan ini, kita dapat membuat urutan dengan merantai bersama panjang setidaknya tiga kali lipat, di mana elemen berikutnya dalam urutan adalah hypotenuse (jumlah terbesar) dari triple Pythagoras primitif terkecil yang mengandung elemen sebelumnya sebagai yang terkecil dari panjangnya.

Mulailah dengan triple Pythagoras primitif terkecil (3, 4, 5). Urutan dimulai dengan 3, dan sisi miring (elemen berikutnya dalam urutan) adalah 5. Kemudian temukan triple Pythagoras primitif terkecil dengan 5kaki, dan Anda dapatkan (5, 12, 13). Jadi urutannya berlanjut 13.

Entah output urutan selamanya, atau mengambil input integer ndan output nelemen pertama dari urutan tersebut, baik nol atau satu diindeks.

Anda perlu mendukung output setidaknya melalui dan termasuk 28455997, tetapi jika batas tipe data yang Anda gunakan tiba-tiba dinaikkan, itu perlu bekerja untuk batas baru itu. Jadi Anda tidak bisa membuat kode dari daftar angka.

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

OEIS A239381

Urutan serupa (jangan tampilkan ini!):

• A018928
• A077034 (istilah aneh)

Jelly , 19 byte

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

Menyimpan satu byte berkat @ Dennis dengan refactoring ke urutan yang tak terbatas.

Tidak mengambil input dan argumen, kemudian mengeluarkan urutan tanpa batas dengan mencetak setiap istilah saat dihitung. Metode ini melambat karena jumlahnya menjadi lebih besar karena tergantung pada faktorisasi prima.

Cobalah online!

Ini menghitung istilah berikutnya dengan menghitung faktorisasi daya utama dari istilah saat ini. Untuk 12325, ini adalah {5 ² , 17, 29}. Ada varian rumus Euclid untuk menghitung tripel Pythagoras { a , b , c },

di mana m > n dan triple adalah iff primitif m dan n adalah coprime.

Untuk menghitung akar primitif berikutnya dari 12325, temukan m dan n sedemikian sehingga mn = 12325 dan pilih m , n sehingga gcd ( m , n ) = 1. Kemudian hasilkan semua pasangan m , n dengan membuat semua himpunan bagian dari {5 ² , 17, 29} dan menemukan produk dari masing-masing himpunan bagian yang adalah {1, 25, 17, 29, 425, 725, 493, 12325}. Kemudian bagi 12325 dengan masing-masing nilai dan pasangan sehingga setiap pasangan adalah m , n . Hitung rumus untuk c menggunakan setiap pasangan dan ambil minimum yaitu 90733.

• Metode sebelumnya gagal untuk menentukan istilah berikutnya setelah 228034970321525477033478437478475683098735674620405573717049066152557390539189785244849203205. Metode sebelumnya memilih nilai terakhir sebagai faktor ketika pilihan yang benar adalah prima ke-3 dan terakhir. Metode baru ini lebih lambat tetapi akan selalu berhasil karena menguji semua pasangan coprimes untuk menemukan sisi miring minimal.

Penjelasan

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 byte

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

Cobalah online!

Anda harus menunggu waktu tunggu program (1 menit) sebelum TIO mengeluarkan output. Dalam REPL SWI-Prolog ini mencetak segera setelah menemukan nilai.

Ini akan mencetak urutan selamanya.

Setelah beberapa menit menggunakan penerjemah offline SWI-Prolog, saya memperolehnya 90733setelah itu 12325. Saya menghentikannya setelah titik ini.

Ini bukan bruteforce lengkap karena menggunakan kendala untuk menemukan tripel pythagoras, meskipun jelas tidak dioptimalkan untuk kecepatan.

Penjelasan

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 byte

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

Semua Tripel Pythagoras a²+b²=c²memuaskan a=r(m²-n²), b=2rmn, c=r(m²+n²)untuk beberapa bilangan bulat r,m,n. Kapan r=1dan m,nadalah coprime dengan tepat satu yang dapat dibagi 2, maka a,b,cmerupakan triple primitif, di mana a,b,csemua coprime berpasangan.

Dengan pemikiran ini, mengingat beberapa a, saya menggunakan algoritma brute-force untuk menghitung terkecil nseperti a²-n²persegi, yaitu m². Kemudian, csama dengan n²+m².

Python 3, 178 byte

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)

Ini pada dasarnya hanya algoritma brute force, dan karenanya sangat lambat. Dibutuhkan jumlah istilah untuk output sebagai input.

Saya tidak 100% yakin tentang kebenaran dari algoritma ini, program memeriksa untuk kaki lainnya hingga kaki pertama kuadrat, yang saya percaya sudah cukup, tetapi saya belum melakukan perhitungan.

Cobalah di repl.it! ( Sudah kedaluwarsa) (Tolong jangan coba-coba untuk nomor yang lebih besar dari 10, itu akan sangat lambat)

MATL , 27 byte

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

Ini menghasilkan istilah pertama dari urutan. Input berbasis 0.

Kode ini sangat tidak efisien. Kompiler online habis waktu untuk input yang lebih besar dari 5. Input 6mengambil satu setengah menit offline (dan menghasilkan yang benar 90733sebagai istilah ke-6).

Cobalah 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

Racket 106 byte

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

Tidak Disatukan:

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

Pengujian:

(f)

Output dari versi golf:

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

Output dari versi yang tidak dikoleksi:

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

(Kesalahan setelah ini di komputer saya)

Bahasa Wolfram (Mathematica) , 74 byte

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

Cobalah online!

Bahasa Wolfram (Mathematica) , 74 byte

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

Cobalah online!

PHP, 139 byte

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

Kode di atas rusak setelah 28455997 pada sistem 32-bit. Jika diperlukan angka yang lebih tinggi, itu menjadi 156 byte:

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 Bytes

-25 byte berkat mil Menggunakan n * n bukan Math.pow (n, 2)

-24 byte berkat mil Menggunakan untuk loop bukan sementara, mengubah tipe data, menghilangkan () karena urutan operasi

()->{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;}};

Menggunakan fakta itu

untuk setiap pasangan bilangan bulat m> n> 0. Karena itu, C sama dengan A plus 2 (N) ² . Fungsi di atas menemukan nilai N paling kecil yang memenuhi hubungan ini, sementara membuat elemen kedua dari tiga Pythagoras menjadi bilangan bulat dan lebih besar dari elemen pertama. Kemudian ia menetapkan nilai elemen pertama ke elemen ketiga dan mengulangi dengan elemen pertama yang diperbarui.

Tidak Disatukan:

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;
    }
}

Ide itu!

* Ideone tidak mencetak elemen yang diperlukan terakhir karena batasan waktu, namun seperti yang Anda lihat melalui logika program dan versi yang tidak diklik (yang mencetak 28455997 sebagai elemen ketiga dari triple Pythagoras sebelumnya daripada elemen pertama dari selanjutnya), nilainya, dengan batas waktu yang lebih tinggi, dicetak.

Python 3.5, 97 byte

Keluaran yang salah setelah 28455997, karena batas tipe data floating point. The sqrtFungsi tidak cukup baik, tetapi jika presisi itu ajaib meningkat, itu akan bekerja.

Cukup mudah dimengerti. Bertambah cdua bukannya satu memotong runtime menjadi dua, dan hanya angka ganjil yang perlu diperiksa, karena elemen selalu aneh.

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

Cobalah online

Program tidak dapat dijalankan di Ideone, karena Ideone menggunakan Python 3.4

Agar output tetap akurat lebih lama, saya harus menggunakan 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

Cobalah online

Agar tetap akurat tanpa batas waktu, saya dapat melakukan sesuatu yang mengerikan seperti ini (meningkatkan presisi yang dibutuhkan setiap iterasi tunggal :

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 byte

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

TIO

perpecahan serakah faktor prima menjadi faktor koprime

54 byte TIO

Pari / GP , 71 byte

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

Cobalah online!

APL (NARS), 169 karakter, 338 byte

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}

uji ok sampai 14 sebagai argumen 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
  ∧

ini di bawah ini akan menemukan semua pembagi argumennya ...

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

JavaScript (Node.js) , 101 byte

_=>{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}}

Cobalah online!

Saran untuk bermain golf dipersilakan