Tugas Anda adalah mengimplementasikan urutan integer A130826 :
a n adalah yang terkecil bilangan bulat positif sehingga sebuah n - n adalah seluruh kelipatan 3 dan dua kali jumlah pembagi dari (a n - n) / 3 memberikan n th istilah dalam perbedaan pertama urutan yang dihasilkan oleh Flavius Saringan Josephus.
Hilang belum? Sebenarnya ini cukup mudah.
The Flavius Josephus saringan mendefinisikan urutan integer sebagai berikut.
Mulailah dengan urutan bilangan bulat positif dan set k = 2 .
Hapus setiap k th integer urutan, dimulai dengan k th .
Bertambah k dan kembali ke langkah 2.
f n adalah n th bilangan bulat (1-diindeks) yang tidak pernah akan dihapus.
Jika - seperti biasa - σ 0 (k) menunjukkan jumlah pembagi positif dari bilangan bulat k , kita dapat mendefinisikan sebuah n sebagai terkecil positif bilangan bulat sehingga 2σ 0 ((a n - n) / 3) = f n + 1 - f n .
Tantangan
Menulis sebuah program atau fungsi yang mengambil bilangan bulat positif n sebagai masukan dan cetak atau mengembalikan sebuah n .
Aturan standar kode-golf berlaku. Semoga kode terpendek menang!
Contoh yang berhasil
Jika kita menghapus setiap elemen kedua dari bilangan bulat positif, kita dibiarkan
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 ...
Setelah menghapus setiap elemen ketiga dari sisanya, kita dapatkan
1 3 7 9 13 15 19 21 25 27 31 33 37 39 ...
Sekarang, menghapus setiap elemen keempat, lalu kelima, lalu keenam membuat kita
1 3 7 13 15 19 25 27 31 37 39 ...
1 3 7 13 19 25 27 31 39 ...
1 3 7 13 19 27 31 39 ...
1 3 7 13 19 27 39 ...
Baris terakhir menunjukkan istilah f 1 hingga f 7 .
Perbedaan elemen berturut-turut dari istilah-istilah ini adalah
2 4 6 6 8 12
Membagi perbedaan ke depan ini dengan 2 , kita dapatkan
1 2 3 3 4 6
Ini adalah jumlah pembagi target.
- 4 adalah bilangan bulat pertama k sehingga σ 0 ((k - 1) / 3) = 1 . Faktanya, σ 0 (1) = 1 .
- 8 adalah bilangan bulat pertama k sehingga σ 0 ((k - 2) / 3) = 2 . Bahkan, σ 0 (2) = 2 .
- 15 adalah bilangan bulat pertama k sehingga σ 0 ((k - 3) / 3) = 3 . Bahkan, σ 0 (4) = 3 .
- 16 adalah bilangan bulat pertama k sehingga σ 0 ((k - 4) / 3) = 3 . Bahkan, σ 0 (4) = 3 .
- 23 adalah bilangan bulat pertama k sehingga σ 0 ((k - 5) / 3) = 4 . Bahkan, σ 0 (6) = 4 .
- 42 adalah bilangan bulat pertama k sehingga σ 0 ((k - 6) / 3) = 6 . Bahkan, σ 0 (12) = 6 .
Uji kasus
n a(n)
1 4
2 8
3 15
4 16
5 23
6 42
7 55
8 200
9 81
10 46
11 119
12 192
13 205
14 196622
15 12303
16 88
17 449
18 558
19 127
20 1748
21 786453
22 58
23 2183
24 3096
25 1105
26 786458
27 12582939
28 568
29 2189
30 2730
sumber
Jawaban:
Jelly,
30292725 byteDisimpan 2 byte berkat @ Dennis memberitahukan saya tentang
Æd
, dan 2 byte lagi untuk menggabungkan dua rantai.Cobalah online!
Ini mungkin yang paling menyenangkan yang pernah saya alami dengan Jelly. Saya mulai dari baris kedua, yang menghitung f n dari n dengan menggunakan rumus pada Oei, dan cukup indah.
Penjelasan
sumber
Python 2 ,
121119118 byteRun time harus kira-kira O (16 n ) dengan penggunaan memori O (4 n ) . Mengganti
4**n
dengan5<<n
- yang saya pikir sudah cukup - akan meningkatkan ini secara dramatis, tapi saya tidak yakin itu bekerja untuk nilai n yang semena-mena .Cobalah online!
Perilaku asimptotik dan batas atas suatu n
Tentukan b n sebagai (a n - n) / 3 , yaitu bilangan bulat positif terkecil k sehingga σ 0 (k) = ½ (f n + 1 - f n ) .
Seperti yang tercantum pada halaman OEIS, f n ~ ¼πn 2 , jadi f n + 1 - f n ~ ¼π (n + 1) 2 - ¼πn 2 = ¼π (2n + 1) ~ ½πn .
Dengan cara ini, ½ (f n + 1 - f n ) ~ ¼πn . Jika angka aktual adalah p prima , bilangan bulat positif terkecil dengan pembagi p adalah 2 p-1 , jadi b n dapat diperkirakan dengan 2 c n , di mana c n ~ ~ n .
Oleh karena itu b n <4 n akan tahan untuk n cukup besar , dan mengingat bahwa 2 ¼π n <2 n << (2 n ) 2 = 4 n , saya yakin tidak ada contoh tandingan.
Bagaimana itu bekerja
Ini mengatur beberapa referensi untuk proses berulang kami.
n adalah input pengguna: bilangan bulat positif.
r adalah daftar [1, ..., 4 n - 1] .
s adalah salinan r .
Mengulangi daftar sekali dengan
r*1
membuat salinan yang dangkal, jadi memodifikasi s tidak akan mengubah r .d diinisialisasi sebagai tuple (s) .
Nilai pertama ini tidak penting. Semua yang lain akan memegang jumlah pembagi bilangan bulat positif.
Untuk setiap bilangan bulat k dari 1 hingga 4 n - 1 , kami melakukan hal berikut.
del s[k::k+1]
mengambil setiap (k + 1) th integer dalam s - dimulai dengan (k + 1) th - dan menghapus yang slice dari s .Ini adalah cara mudah menyimpan interval awal saringan Flavius Josephus dalam s . Ini akan menghitung lebih dari yang diperlukan n + 1 hal awal, tetapi menggunakan satu
for
loop untuk memperbarui kedua s dan d menyimpan beberapa byte.d+=sum(k%j<1for j in r)*2,
menghitung berapa banyak elemen r membagi k secara merata dan menambahkan 2σ 0 (k) menjadi d .Karena d diinisialisasi sebagai singleton tuple, 2σ 0 (k) disimpan pada indeks k .
Temuan ini indeks pertama f n + 1 - f n di d , yang merupakan terkecil k sehingga 2σ 0 (k) = f n + 1 - f n , maka menghitung sebuah n sebagai 3k + 1 dan mencetak hasilnya.
sumber
Java 8,
336,305,303,287,283279 byte57 byte dihapus berkat Kritixi Lithos
Golf
Tidak disatukan
sumber
int
lebih pendek daripada menggunakanjava.util.Scanner
. Tetapi bahkan jika Anda menggunakan Scanner, Anda dapat melakukanSystem.out.print(h(new java.util.Scanner().nextInt()))
dan menghapus baris sebelumnyaint h()
, Anda dapat mengubahnya keint v = (g(k,k)-g(k,k-1))/2,u = 0,t = 1;
. Anda dapat mengubah if-statement Anda (yang ada di dalam for-loop Anda) dariif(t%i==0)
menjadiif(t%i<1)
g
untuk kembali menggunakan operator ternary sepertireturn s==0?N+1:g(s-1,N+N/2)
-ishMathematica,
130116106103 byteatau
Akhirnya hampir identik dengan kode Jelly @ Pietu1998 ...
Penjelasan
Catch
apa pun yangThrow
-d (dilempar).Loop tak terbatas;
k
mulai dari1
dan menambah setiap iterasi.Tetapkan
f
:Temukan
{1, 2, ... , n}
. Balikkan itu.Fungsi yang menampilkan ceil (n1 / n2 + 1) * n2
Tetapkan
f
fungsi yang secara rekursif menerapkan fungsi di atas ke daftar dari dua langkah di atas, menggunakan setiap output sebagai input pertama dan setiap elemen daftar sebagai input kedua. "Output" awal (input pertama) adalah elemen pertama dari daftar.Periksa apakah dua kali jumlah pembagi
k
sama dengan f (n + 1) - f (n).Jika kondisinya
True
,Throw
nilaik
. Jika tidak, lanjutkan pengulangan.Lipat gandakan hasilnya dengan 3 dan tambahkan n.
Versi 130 byte
sumber
Perl 6 ,
154149136107 byteTidak Disatukan:
sumber
05AB1E ,
353439 byteTerlihat mengerikan, begitu juga kinerja runtime. Diperlukan beberapa detik untuk input yang menghasilkan nilai kecil. Jangan coba angka seperti 14; pada akhirnya akan menemukan hasilnya tetapi akan butuh waktu lama.
Penjelasan
Ini berfungsi sebagai 2 program yang disebut berurutan. Yang pertama menghitung F n + 1 - F n dan yang kedua menentukan sebuah n berdasarkan definisi, menggunakan pendekatan bruteforce.
F n + 1 - F n dievaluasi untuk setiap iterasi meskipun loop invarian. Itu membuat waktu kode tidak efisien, tetapi membuat kode lebih pendek.
Cobalah online!
sumber
žHL
) dan kemudian menyaring nilai-nilai yang tidak memenuhi batasan saringan. Saya pikir bagian pertama dari program ini harus sepenuhnya ditulis ulang dengan pendekatan yang sama sekali berbeda untuk membuatnya golf.given enough time and memory
, karena saya sudah melihat beberapa jawaban pada pertanyaan lain yang berjalan sangat lambat sehingga hampir tidak mungkin untuk mengatakan apakah mereka menghasilkan output yang tepat atau tidak. Untuk alasan ini saya menempatkan perhitungan saringan selain dari loop dan harganya 2 byte.