Definisi
- Dua bilangan bulat adalah koprime jika tidak berbagi pembagi umum positif selain
1
. a(1) = 1
a(2) = 2
a(n)
adalah bilangan bulat positif terkecil yang coprime kea(n-1)
dana(n-2)
dan belum muncul, untuk bilangan bulatn >= 3
.
Tugas
- Diberikan bilangan bulat positif
n
, keluaran / cetaka(n)
.
Contoh
a(11) = 6
karena6
coprime dengan dua pendahulu terakhir (yaitu,11
dan13
) dan6
belum pernah muncul sebelumnya.
Catatan
- Perhatikan bahwa urutannya tidak naik, artinya suatu elemen bisa lebih kecil dari pendahulunya.
Spesifikasi
- Anda harus menggunakan 1-diindeks.
Testcases
n a(n)
1 1
2 2
3 3
4 5
5 4
6 7
7 9
8 8
9 11
10 13
11 6
12 17
13 19
14 10
15 21
16 23
17 16
18 15
19 29
20 14
100 139
1000 1355
10000 13387
100000 133361
Mencetak gol
- Karena coprime berarti bahwa dua angka hanya berbagi satu pembagi (
1
), dan1
merupakan angka kecil, kode Anda harus sekecil mungkin dalam hal byte-count.
Referensi
- OEIS A084937
code-golf
sequence
number-theory
Biarawati Bocor
sumber
sumber
Jawaban:
Python 3.5,
160141126124121109 byteIni adalah implementasi sederhana dari definisi urutan. Saran bermain golf diterima.
Sunting: -17 bytes berkat Leaky Nun. -9 byte terima kasih kepada Peter Taylor. -6 byte berkat Sp3000 dan beralih ke Python 3.5.
Tidak melakukan pelanggaran:
sumber
import math
makag=math.gcd
harus lebih pendek daripada mendefinisikan Anda sendirig
. Untuk sebelum 3.5, Anda dapat melakukanfrom fractions import*
untukgcd
.c=3
di dalam loop, Anda hanya perlu melakukannya sekali. Menurut perhitungan saya, Anda menyimpan 3 karakter.r=[c]+r
daripada+=
, tetapi tiga indeks negatif menjadi positif. Dan kemudian ada penghematan 2-char lebih lanjut dari penulisan ulang sebagai lambda, meskipun itu perubahan yang cukup drastis:from fractions import*;F=lambda n,r=[2,1],c=3:n<2and r[1]or(c in r)+gcd(r[0]*r[1],c)<2and F(n-1,[c]+r)or F(n,r,c+1)
dan tidak perluprint
karena tidak lagi program penuh.MATL ,
2827 byteKode lambat, tetapi memberikan hasil yang benar.
Cobalah online! Atau verifikasi sepuluh kasus pertama .
Modifikasi kecil dari kode menghasilkan plot urutan:
Lihat sebagai seni ASCII , atau dengan output grafis dalam kompiler offline:
Penjelasan
sumber
C, 185 byte
sumber
Sebenarnya ,
383735333130 byteIni adalah implementasi sederhana dari definisi fungsi. Saran bermain golf diterima. Cobalah online!
Sunting: -3 bytes berkat Leaky Nun.
Tidak melakukan pelanggaran:
sumber
Haskell,
8173 byteContoh penggunaan:
((0:1:c[2,1])!!) 12
->17
.Buat daftar semua
a(n)
, mulai dengan0
memperbaiki indeks berbasis 1 dan1
dan diikuti olehc[2,1]
.c
mengambil kepala dari daftar argumen itul
diikuti oleh panggilan rekursif dengan kemudian nomor berikutnya yang cocok (co-prime, tidak terlihat sebelumnya) ditambahkan di depanl
. Pilihn
elemen ke-10 dari daftar ini.sumber
R, 141 byte
ungolfed
sumber
Mathematica,
9790 byteBerdasarkan
dugaan saya itua(n) < 2n
untuk semuan
.Untuk menjalankan lebih cepat, tambahkan
a@n=
setelah yang asli:=
sehingga fungsi tidak perlu menghitung ulang nilai sebelumnya .Disimpan 7 byte berkat Sherlock9 (jika
gcd(a,b)=1
kemudiangcd(ab,m) = gcd(a,m)*gcd(b,m)
)sumber
ABS(a(n)-n) < n
"n
.Pyth, 23 byte
Suite uji
Implementasi yang cukup mudah, tetapi dengan beberapa trik golf yang bagus.
sumber