pengantar
A229037 memiliki plot yang cukup menarik (setidaknya untuk beberapa istilah pertama):
Ada dugaan, bahwa memang mungkin memiliki semacam properti fraktal.
Bagaimana urutan ini dibangun?
Tentukan a(1) = 1, a(2) = 1
maka untuk setiap n>2
menemukan positif minimal bilangan bulat a(n)
sehingga untuk setiap urutan 3 jangka aritmatika n,n+k,n+2k
indeks, nilai-nilai yang sesuai urutan a(n),a(n+k),a(n+2k)
adalah tidak urutan aritmatika.
Tantangan
Diberikan bilangan bulat positif n
sebagai input, output n
istilah pertama a(1), ... , a(n)
dari urutan ini. (Dengan pemformatan yang masuk akal. Karakter / string terkemuka / pelatihan tidak relevan.)
Ada cuplikan untuk membuat urutan ini, tetapi saya pikir pendekatan lain mungkin lebih cocok untuk golf / lebih cocok untuk bahasa tertentu.
Beri tahu kami cara kerja program Anda. Jika Anda menemukan suatu persilangan suatu algoritma yang sangat efisien, Anda mungkin ingin menyebutkannya juga, karena akan memungkinkan untuk memplot lebih banyak istilah dari urutan dalam waktu yang lebih singkat.
Beberapa kasus uji pertama:
1, 1, 2, 1, 1, 2, 2, 4, 4, 1, 1, 2, 1, 1, 2, 2, 4, 4, 2, 4, 4, 5, 5, 8, 5, 5, 9, 1, 1, 2, 1, 1, 2, 2, 4, 4, 1, 1, 2, 1, 1, 2, 2, 4, 4, 2, 4, 4, 5, 5, 8, 5, 5, 9, 9, 4, 4, 5, 5, 10, 5, 5, 10, 2, 10, 13, 11, 10, 8, 11, 13, 10, 12, 10, 10, 12, 10, 11, 14, 20, 13
Lebih banyak testcases:
a(100) = 4
a(500) = 5
a(1000) = 55
a(5000) = 15
a(10000) = 585
Semua persyaratan hingga n=100000
tersedia di sini: https://oeis.org/A229037/b229037.txt
Terima kasih @ MartinBüttner atas bantuan dan dorongannya.
Jawaban:
Python 2, 95 byte
Trik utamanya adalah dalam menghasilkan angka-angka yang harus dihindari oleh nilai baru. Menjaga urutan terbalik sejauh ini
l
, mari kita lihat elemen apa yang mungkin membentuk perkembangan aritmatika tiga istilah dengan nilai yang akan kita tambahkan.Angka-angka lainnya adalah anggota berpasangan
l
dan setiap elemen kedual
, jadizip(l,l[1::2])
. Jika pasangan ini(b,c)
maka perkembangan aritmatika(a,b,c)
terjadi untuka=2*b-c
. Setelah membuat seta
untuk menghindari, kode mengambil minimum dari komplemen, mencetaknya, dan menambahkannya ke daftar. (Sebenarnya, perhitungan dilakukan dengan angka yang berkurang 1, dan dicetak 1 lebih tinggi, untukrange(n)
dijadikan sebagai calon dari seluruh dunia.)sumber
Mathematica, 95 byte
Tentu saja bukan pendekatan golf, tetapi ini sebenarnya cukup efisien, dibandingkan dengan algoritma yang saya coba dari halaman OEIS.
Berbeda dengan memeriksa semua nilai terlarang untuk setiap s (n) ketika kami sampai di sana saya menggunakan pendekatan berbasis saringan. Ketika kami menemukan nilai baru s (n), kami segera memeriksa nilai mana yang melarang ini untuk m> n . Kemudian kita hanya menyelesaikan s (n +1) dengan mencari nilai pertama yang tidak dilarang.
Ini dapat dibuat lebih efisien dengan mengubah persyaratan
--i>0
menjadi2n-#<=--i>0
. Dalam hal ini, kami menghindari memeriksa nilai terlarang untuk n lebih besar dari input.Untuk versi yang lebih mudah dibaca, saya mulai dengan kode ini, yang menyimpan hasil hingga
max
dalam suatu fungsif
, dan kemudian memutarnya ke fungsi murni satu-baris di atas:sumber
Haskell,
90,89,84, 83 byteMungkin bisa bermain golf lebih banyak, tetapi ini masih merupakan upaya
pertama yanglayak :Tidak Disatukan:
Ini adalah implementasi sederhana yang mengembalikan '0' untuk di luar batas. Kemudian, untuk setiap nilai yang mungkin, ia memeriksa bahwa untuk semua k <= n dan dalam batas, [x, a (xk), a (x-2k)] bukan urutan aritmatika.
Kompleksitas waktu terikat atas (menggunakan fakta dari halaman OEIS bahwa a (n) <= (n + 1) / 2:
Saya tidak yakin seberapa bagus ikatan ini karena menghitung nilai 1k pertama 't' dan menggunakan model linier pada log dari nilai yang diberikan appx. O (22 ^ n), dengan p-value <10 ^ (- 1291), jika itu penting.
Pada tingkat implementasi, kompilasi dengan '-O2', butuh ~ 35 menit untuk menghitung 20 nilai pertama.
sumber
Brachylog ,
3331 byteCobalah online!
Dalam hal itu penting: Golf 2-byte dimungkinkan berkat fitur yang saya minta setelah mengerjakan tantangan ini.
Penjelasan
Kami menghasilkan urutan berulang sebagai daftar dalam urutan terbalik, misalnya
[2,2,1,1,2,1,1]
, dan membalikkannya di akhir.Ada beberapa predikat bersarang di sini. Mari kita lihat mereka dari dalam ke luar. Yang pertama
ġh₃hᵐs₂ᶠ-ᵐ=
,, mengambil kandidat berikutnyaa(n),a(n-1),...,a(0)
dan menentukan apakaha(n),a(n-k),a(n-2k)
urutan aritmatika untuk beberapak
.Misalnya dengan masukan dari
[1,2,1,1,2,1,1]
:Predikat berikutnya ke luar,,
~b.hℕ₁≜∧.¬{...}∧
memasukkana(n-1),a(n-2),...,a(0)
urutan dan output urutan berikutnya yang lebih besara(n),a(n-1),a(n-2),...,a(0)
.Terakhir, predikat utama
;Ė{...}ⁱ⁽↔
mengambil nomor input dan output yang banyak termsinya.sumber
Ruby , 71 byte
Cobalah online!
Menghasilkan semua nilai terlarang, kemudian mengambil pelengkap array itu di (1..n) dan mengambil nilai pertama dari hasilnya. Itu berarti saya menganggap itu
a[n] <= n
untuk semua n, yang mudah dibuktikan menggunakan induksi (jika n / 2 istilah pertama semuanya kurang dari n / 2, maka tidak mungkin ada perkembangan aritmatika yang mengarah ke n).Trik sintaksis di sini juga agak menarik:
*a
digunakan untuk menginisialisasi array argumen tambahan (yang akan diabaikan jika kita melewatkannya), dan kemudiana.fill
mengubah array argumen dan secara implisit mengembalikannya.sumber
a[s-o]
dana[s-2*o]
, Anda dapat menggunakana[s-=1]
dana[s-o]
APL (Dyalog Extended) , 37 byte SBCS
Terima kasih banyak kepada Adám atas bantuannya dalam menulis dan bermain golf jawaban ini di The APL Orchard , tempat yang bagus untuk belajar bahasa APL. Cobalah online!
Edit: -6 byte terima kasih kepada Adám
Penjelasan
APL (Dyalog Unicode) ,
433938 byte SBCSBerikut ini adalah solusi yang lebih cepat tetapi kurang golf yang dapat dihitung
⍺(10000)
dalam beberapa detik.Cobalah online!
sumber
MATLAB,
156147 byteSaya akhirnya bisa bermain golf ini sedikit:
Tidak Disatukan:
Input dibaca dari STDIN, dan pencetakan dilakukan secara otomatis dengan
ans=
dan barang ditambahkan. Saya berharap ini memenuhi syarat sebagai output "masuk akal".Ini juga merupakan solusi berbasis saringan: variabel
s(i,:)
terus melacak dari nilai-nilai urut yang dilarang untuka(i)
. Thetry-catch
blok diperlukan untuk mengobati kasus kosong (berarti nol penuh)s
matriks: dalam hal ini nilai terendah1
sudah diperbolehkan.Namun, kebutuhan memori (atau runtime?) Menjadi sangat berantakan di atas
N=2000
. Jadi, inilah solusi yang tidak bersaing dan lebih efisien:Dalam implementasi ini,
s
matriks kembali berisi nilai-nilai terlarang, tetapi dengan cara yang tertata dengan baik, tanpa nol blok (yang ada dalam versi yang bersaing). Vektor indeksi
melacak jumlah vektor terlarang dis
. Pada awalnya sel akan bagus untuk melacak informasi yang disimpans
, tetapi itu akan lambat, dan kami tidak dapat mengindeks banyak dari mereka pada saat yang sama.Salah satu fitur buruk MATLAB adalah walaupun Anda dapat mengatakan
M(1,end+1)=3;
dan secara otomatis memperluas matriks, Anda tidak dapat melakukan hal yang sama dengan pengindeksan linear. Agak masuk akal (bagaimana MATLAB harus tahu ukuran array yang dihasilkan, dalam kerangka yang seharusnya menafsirkan indeks linier?), Tetapi masih mengejutkan saya. Ini adalah alasan untuk baris berlebihans(N,max(i(j))) = 0;
: ini akan memperluass
matriks untuk kita kapan pun diperlukan. Tebakan ukuran awalN*0.07+20
berasal dari kecocokan linear dengan beberapa elemen pertama.Untuk menguji runtime, saya juga memeriksa versi kode yang sedikit dimodifikasi, di mana saya menginisialisasi
s
matriks untuk memiliki ukuranN/2
. Untuk1e5
elemen pertama ini tampaknya merupakan perkiraan yang sangat murah hati, jadi saya menghapus langkah ekspansi yangs
disebutkan dalam paragraf sebelumnya. Ini bersama-sama menyiratkan bahwa kode akan lebih cepat, tetapi juga kurang kuat di sangat tinggiN
(karena saya tidak tahu bagaimana seri ini terlihat di sana).Jadi, inilah beberapa runtime, membandingkan
Saya mengukur ini pada R2012b, mengambil yang terbaik dari 5 berjalan di dalam definisi fungsi bernama dengan
tic/toc
.N=100
:0.011342 s
0.015218 s
0.015076 s
N=500
:0.101647 s
0.085277 s
0.081606 s
N=1000
:0.641910 s
0.187911 s
0.183565 s
N=2000
:5.010327 s
0.452892 s
0.430547 s
N=5000
:2.021213 s
1.572958 s
N=10000
:6.248483 s
5.812838 s
Tampaknya
v3
versi ini signifikan, tetapi tidak terlalu cepat. Saya tidak tahu apakah elemen ketidakpastian (untuk sangat besarN
) bernilai peningkatan minor dalam runtime.sumber
M=1;M(end+1)=2;
berfungsi dengan baik untuk saya?M=rand(2); M(end+1)=2
saja :)Jelly ,
2419 byteIni adalah jawaban Jelly pertamaku dalam beberapa saat. Senang bisa kembali.
Ini adalah port jawaban APL saya yang merupakan adaptasi dari banyak algoritma yang digunakan di sini. Perbedaan utama adalah ini diindeks 0.
Sunting: -5 byte terima kasih kepada Jonathan Allan.
Cobalah online!
Penjelasan
sumber
ḟ
akan melakukan sertaœ-
menghemat byte“”
dengan1
menampilkan representasi Jelly daftar dari program penuh, menyimpan satu lagi.Œœị@2
dapat bermain golf untukḊm2
menghemat dua.L‘R
mungkin golf untukŻJ
menyimpannya.ES6, 114 byte
Mengembalikan larik elemen n pertama dari urutan, sehingga indeksnya adalah 1 dari versi tanpa tanda di bawah ini. Saya menggunakan pendekatan saringan. Versi ini melambat setelah sekitar n = 2000; versi sebelumnya menghindari pembacaan awal array yang berarti tidak memperlambat sampai sekitar n = 2500. Versi yang lebih lama menggunakan array saringan sebagai daftar nilai terlarang daripada array boolean yang nilai-nilainya dilarang; ini bisa mencapai n = 5000 tanpa berkeringat. Versi asli saya mencoba menggunakan bitmask tetapi ternyata tidak membantu (dan juga terlalu panjang pada 198 byte).
Versi yang tidak terlalu lambat ungolfed:
sumber