Tugasnya adalah menghitung OEIS A005434 secepat mungkin.
Pertimbangkan S
panjang string biner n
. Mengindeks dari 1
, kita dapat menentukan apakah S[1..i+1]
cocok S[n-i..n]
untuk semua i
dalam urutan dari 0
ke n-1
. Sebagai contoh,
S = 01010
memberi
[Y, N, Y, N, Y].
Ini karena 0
cocok 0
, 01
tidak cocok 10
, 010
cocok 010
, 0101
tidak cocok 1010
dan akhirnya 01010
cocok dengan sendirinya.
Tentukan f(n)
jumlah array yang berbeda dari Y
s dan N
s yang didapat ketika iterasi semua 2^n
string bit S
panjang yang mungkin berbeda n
.
Pengamat akan memperhatikan bahwa pertanyaan ini adalah varian yang lebih sederhana dari pertanyaan saya yang lain baru-baru ini . Namun, saya berharap bahwa trik cerdas dapat membuat ini lebih cepat dan lebih mudah.
Tugas
Untuk meningkatkan n
mulai dari 1
, kode Anda harus ditampilkan n, f(n)
.
Contoh jawaban
Sebab n = 1..24
, jawaban yang benar adalah:
1, 2, 3, 4, 6, 8, 10, 13, 17, 21, 27, 30, 37, 47, 57, 62, 75, 87, 102, 116, 135, 155, 180, 194
Mencetak gol
Kode Anda harus iterate dari n = 1
memberi jawaban untuk masing-masing n
pada gilirannya. Saya akan mengatur waktu seluruh pelarian, membunuhnya setelah dua menit.
Skor Anda adalah yang tertinggi yang n
Anda dapatkan pada waktu itu.
Dalam kasus seri, jawaban pertama menang.
Di mana kode saya akan diuji?
Saya akan menjalankan kode Anda di bawah Virtualbox di VM tamu Lubuntu (pada host Windows 7 saya).
Laptop saya memiliki RAM 8GB dan CPU Intel i7 [email protected] GHz (Broadwell) dengan 2 core dan 4 thread. Set instruksi termasuk SSE4.2, AVX, AVX2, FMA3 dan TSX.
Entri terkemuka per bahasa
- n = 599 di Rust bu Anders Kaseorg.
- n = 30 dalam C oleh Grimy. Versi paralel mencapai 32 ketika dijalankan secara native di cygwin.
Jawaban:
Karat , n ≈ 660
Cobalah online!
Bagaimana itu bekerja
Ini adalah implementasi memoized dari predikat rekursif Ξ yang diberikan dalam Leo Guibas, "Periode dalam string" (1981). Fungsi
f(memo, n, p, s)
menemukan jumlah korelasi panjangn
dengan periode terkecilp
dan juga masing-masing periode dalam himpunans
.sumber
Hanya pencarian kasar sederhana, untuk memulai tantangan:
Kompilasi dengan
clang -fopenmp -Weverything -O3 -march=native
. Di mesin saya mencapai n = 34 dalam 2 menit.EDIT: menaburkan beberapa arahan OMP untuk paralelisme mudah.
sumber