Hari ini kita akan melihat urutan a , terkait dengan fungsi Collatz f :
Kami menyebutnya urutan bentuk z, f (z), f (f (z)), ... suatu urutan Collatz .
Angka pertama dalam urutan kami , a (1) , adalah 0 . Di bawah aplikasi berulang f , ia jatuh ke dalam siklus 0 → 0 →…
Angka terkecil yang belum kita lihat adalah 1, menghasilkan (2) = 1 . Di bawah penerapan berulang f , ia jatuh ke dalam siklus 1 → 4 → 2 → 1 →…
Sekarang kita telah melihat angka 2 dalam siklus di atas, sehingga angka terkecil berikutnya adalah a (3) = 3 , termasuk dalam siklus 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 → 4 → 2 → 1 → ...
Dalam semua siklus di atas kita telah melihat 4 dan 5 sudah, jadi angka selanjutnya adalah (4) = 6 .
Sekarang Anda harus mendapatkan ide. a (n) adalah angka terkecil yang bukan bagian dari urutan Collatz untuk semua (1), ..., a (n - 1) .
Tulis program atau fungsi yang, dengan bilangan bulat positif n , mengembalikan a (n) . Kode terpendek dalam byte menang.
Testcases:
1 -> 0
2 -> 1
3 -> 3
4 -> 6
5 -> 7
6 -> 9
7 -> 12
8 -> 15
9 -> 18
10 -> 19
50 -> 114
(Ini adalah urutan OEIS A061641 .)
sumber
n
berbasiskan 0?a(n+1) = a(n) odd: 3*a(n)+1, or a(n) even: a(n)/2
a
tidak berbasis 0, saya tidak mengerti mengapa Anda tampaknya "berbicara berbasis 0" di sini:a(n) is the smallest number that was not part of any Collatz sequences for all a(0), …, a(n − 1).
Jawaban:
Jelly ,
2019 byteCobalah online! atau verifikasi semua kasus uji .
Bagaimana itu bekerja
Setelah n iterasi, nilai a (n + 1) akan berada di awal array. Karena kita menggabungkan array baru dengan salinan yang lama, ini berarti bahwa (n) akan berada di akhir.
sumber
Haskell,
9392 byteContoh penggunaan:
([y|y<-[-1..],all(/=y)$c=<<[0..y-1]]!!) 10
->19
.c x
adalah siklus Collatzx
dengan sedikit kecuranganx == 1
. Fungsi utama loop melalui semua bilangan bulat dan membuat orang-orang yang tidakc x
untukx
di[0..y-1]
. Cukup banyak implementasi langsung dari definisi tersebut. Karena operator indeks Haskell!!
berbasis 0, saya mulai-1
untuk menambahkan nomor (jika tidak berguna) untuk memperbaiki indeks.sumber
MATL ,
4640 byteCobalah online!
Penjelasan
Kode memiliki
for
loop luar yang menghasilkann
urutan Collatz, satu di setiap iterasi. Setiap urutan dihasilkan olehdo...while
loop dalam yang menghitung nilai baru dan menyimpannya dalam vektor urutan hingga1
atau0
diperoleh. Ketika kita selesai dengan urutan, vektor dibalik dan digabungkan ke vektor global yang berisi nilai-nilai dari semua urutan sebelumnya. Vektor ini dapat berisi nilai berulang. Pembalikan vektor urutan memastikan bahwa pada akhir loop luar hasil yang diinginkan (nilai awal dari urutan terakhir) akan berada di akhir vektor global.Kode semu :
Kode yang dikomentari :
sumber
Brachylog ,
7067656362 byteCobalah online!
sumber
Python 2,
9796 byteMengambil keuntungan dari kenyataan bahwa semua kelipatan 3 adalah murni. Uji di Ideone .
Bagaimana itu bekerja
Pada baris pertama,
r,=s={-1}
set s = {-1} (set) dan r = -1 .Selanjutnya kita membaca integer dari STDIN, ulangi string tertentu yang berkali-kali, kemudian jalankan. Ini sama dengan kode Python berikut.
Dalam setiap iterasi, kita mulai dengan mencari anggota terkecil dari {r + 1, r + 2, r + 3} yang bukan milik s . Dalam iterasi pertama, ini menginisialisasi r sebagai 0 .
Dalam semua proses selanjutnya, s mungkin (dan akan) berisi beberapa r + 1 , r + 2 dan r + 3 , tetapi tidak semuanya, karena semua kelipatan 3 adalah murni. Untuk memverifikasi pernyataan ini, perhatikan bahwa tidak ada kelipatan m dari 3 dalam bentuk 3k +1 . Yang menjadikan 2m sebagai satu-satunya pra-gambar yang mungkin, yang juga merupakan kelipatan dari 3 . Dengan demikian, m tidak dapat muncul dalam urutan Collatz dari angka apa pun yang kurang dari m , dan karenanya murni.
Setelah mengidentifikasi r dan menginisialisasi n , kita menerapkan fungsi Collatz dengan
n=(n/2,3*n+1)[n%2]
menambahkan setiap nilai menengah n ke set s dengans|={n}
. Setelah kita menemukan angka n yang sudah dalam s ,{n}-s
akan menghasilkan set kosong, dan iterasi berhenti.Nilai terakhir r adalah elemen urutan yang diinginkan.
sumber
Pyth , 32 byte
Suite uji.
sumber
Java, 148 byte
Ide itu! (Peringatan: kompleksitas eksponensial karena nol optimasi.)
Mengubahnya dari satu
do...while
loop kefor
loop akan menjadi golfier, tetapi saya mengalami kesulitan melakukannya.Saran bermain golf disambut seperti biasa.
sumber
for(b=1,i=1;i<n;i++)
kefor(b=1,i=0;++i<n;)
. Btw, saya mengerti mengapa ideone Anda kehilangan test case untuk 50, tetapi mengapa juga melewatkan 10? Itu bisa menanganinya tanpa masalah.int a(int n){if(n<2)return 0;int f=a(n-1),b=0,i,c;for(;b<1;){f++;for(b=1,i=1;i<n;i++)for(c=i==2?4:a(i);c>1;c=c%2>0?c*3+1:c/2)b=c==f?0:b;}return f;}
Perl6, 96
Berdasarkan jawaban Perl 5 . Sedikit lebih lama sejak sintaks Perl6 kurang memaafkan daripada sintaksis Perl5, tapi saya akan puas dengan ini untuk saat ini.
sumber
PHP,
233124 byte+4 untuk fungsi:
sumber
Perl 5 - 74 byte
Ini adalah solusi yang cukup mudah. Itu berulang kali menerapkan fungsi Collatz ke variabel
$a
dan menyimpan dalam array@c
bahwa nilainya telah terlihat, kemudian setelah mencapai 0 atau 1 itu bertambah$a
sampai itu angka yang belum terlihat. Ini diulangi beberapa kali sama dengan input minus 2, dan akhirnya nilai$a
yang dikeluarkan.sumber
Mathematica, 134 byte
Format yang lebih mudah dibaca:
sumber