Terinspirasi oleh pertanyaan Math.SE ini .
Latar Belakang
The Fibonacci urutan (disebut F
) adalah urutan, mulai 0, 1
sehingga setiap nomor ( F(n)
) (setelah dua yang pertama) adalah jumlah dari dua sebelum ( F(n) = F(n-1) + F(n-2)
).
Fibonacci Sequence mod K (disebut M
) adalah urutan angka Fibonacci mod K ( M(n) = F(n) % K
).
Dapat ditunjukkan bahwa Fibonacci Sequence mod K adalah cyclic untuk semua K, karena setiap nilai ditentukan oleh pasangan sebelumnya, dan hanya ada K 2 kemungkinan pasangan bilangan bulat non-negatif, keduanya kurang dari K. Karena Fibonacci sequence mod K adalah siklik setelah pasangan istilah berulang yang pertama, angka yang tidak muncul dalam Fibonacci Sequence mod K sebelum pasangan istilah berulang yang pertama tidak akan pernah muncul.
Untuk K = 4
0 1 1 2 3 1 0 1 ...
Untuk K = 8
0 1 1 2 3 5 0 5 5 2 7 1 0 1 ...
Perhatikan bahwa untuk K = 8, 4 dan 6 tidak muncul sebelum diulang 0 1
, jadi 4 dan 6 tidak akan pernah muncul dalam Fibonacci Sequence mod 8.
Tantangan
Mengingat bilangan bulat K benar-benar lebih besar dari 0, output semua bilangan bulat non-negatif kurang dari K yang tidak muncul dalam Fibonacci Sequence mod K.
Aturan
Anda dapat berasumsi bahwa K akan cocok dengan tipe integer asli Anda ( sesuai alasan ).
Jika ada angka non-negatif kurang dari K yang tidak muncul dalam Fibonacci Sequence mod K, program / fungsi Anda harus menampilkan semua angka tersebut dengan cara yang masuk akal.
Jika tidak ada bilangan bulat non-negatif kurang dari K yang tidak muncul dalam Fibonacci Sequence mod K, program / fungsi Anda dapat menunjukkan ini dengan mengembalikan daftar kosong, tidak mencetak apa-apa, menghasilkan kesalahan, dll.
Urutan tidak masalah.
Ini kode-golf , jadi jawaban tersingkat di setiap bahasa menang.
Uji Kasus
Kasus Uji Tidak Kosong
8 [4, 6]
11 [4, 6, 7, 9]
12 [6]
13 [4, 6, 7, 9]
16 [4, 6, 10, 12, 14]
17 [6, 7, 10, 11]
18 [4, 6, 7, 9, 11, 12, 14]
19 [4, 6, 7, 9, 10, 12, 14]
21 [4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 17, 19]
22 [4, 6, 7, 9, 15, 17, 18, 20]
23 [4, 7, 16, 19]
24 [4, 6, 9, 11, 12, 14, 15, 18, 19, 20, 22]
26 [4, 6, 7, 9, 17, 19, 20, 22]
28 [10, 12, 14, 16, 18, 19, 23]
29 [4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 27]
31 [4, 6, 9, 12, 14, 15, 17, 18, 19, 22, 25, 29]
32 [4, 6, 10, 12, 14, 18, 20, 22, 26, 28, 30]
33 [4, 6, 7, 9, 15, 17, 18, 20, 24, 26, 27, 28, 29, 31]
34 [4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 27, 28, 30]
36 [4, 6, 7, 9, 10, 11, 12, 14, 16, 18, 20, 22, 23, 24, 25, 26, 27, 29, 30, 31, 32]
37 [9, 10, 14, 17, 20, 23, 27, 28]
38 [4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 31, 32, 33, 36]
39 [4, 6, 7, 9, 15, 17, 19, 20, 22, 24, 30, 32, 33, 35]
...
200 [4, 6, 12, 14, 20, 22, 28, 30, 36, 38, 44, 46, 52, 54, 60, 62, 68, 70, 76, 78, 84, 86, 92, 94, 100, 102, 108, 110, 116, 118, 124, 126, 132, 134, 140, 142, 148, 150, 156, 158, 164, 166, 172, 174, 180, 182, 188, 190, 196, 198]
...
300 [6, 18, 30, 42, 54, 66, 78, 90, 102, 114, 126, 138, 150, 162, 174, 186, 198, 210, 222, 234, 246, 258, 270, 282, 294]
...
400 [4, 6, 10, 12, 14, 20, 22, 26, 28, 30, 36, 38, 42, 44, 46, 52, 54, 58, 60, 62, 68, 70, 74, 76, 78, 84, 86, 90, 92, 94, 100, 102, 106, 108, 110, 116, 118, 122, 124, 126, 132, 134, 138, 140, 142, 148, 150, 154, 156, 158, 164, 166, 170, 172, 174, 180, 182, 186, 188, 190, 196, 198, 202, 204, 206, 212, 214, 218, 220, 222, 228, 230, 234, 236, 238, 244, 246, 250, 252, 254, 260, 262, 266, 268, 270, 276, 278, 282, 284, 286, 292, 294, 298, 300, 302, 308, 310, 314, 316, 318, 324, 326, 330, 332, 334, 340, 342, 346, 348, 350, 356, 358, 362, 364, 366, 372, 374, 378, 380, 382, 388, 390, 394, 396, 398]
...
Kasus Uji Kosong (tidak ada output, kesalahan, daftar kosong, dll. Adalah output yang dapat diterima)
1, 2, 3, 4, 5, 6, 7, 9, 10, 14, 15, 20, 25, 27, 30, 35 ... 100 ...
Jawaban:
Jelly ,
98 byteCobalah online!
Berdasarkan periode pisano
p(n) <= 6n
mulai A001175 . Juga,p(n) <= 6n <= n^2
untukn >= 6
danp(n) <= n^2
untukn < 6
. Disimpan byte ini berkat Dennis.sumber
²
harus bekerja×6
.Haskell , 70 byte
Beberapa jumlah byte disimpan berkat Buah Esolanging
8 byte disimpan berkat Laikoni
Cobalah online!
sumber
read$show
berfungsi alih-alihfromInteger
dalam kasus ini dan menyimpan dua byte.zip[1..x^2]
untuk memotong menghemat lebih banyak byte: Cobalah online!Perl 6 ,
43 42 3932 byteMenguji
Menguji
Menguji
Menguji
Diperluas:
sumber
> <> , 48 byte
Cobalah online!
Mengambil input melalui flag -v.
Mencetak banyak baris baru berlebih, tetapi menyelesaikan pekerjaan. Ini pada dasarnya menggunakan baris pertama untuk menyimpan set angka yang telah muncul sejauh ini dalam urutan.
Bagaimana itu bekerja:
sumber
Python 2 , 69 byte
Cobalah online!
sumber
MATL ,
1918 byteCobalah online!
-1 byte terima kasih kepada Guiseppe.
sumber
X~
!Python 3 , 91 byte
Cobalah online!
sumber
Sekam ,
13 1210 byteTerima kasih @Zgarb untuk -2 byte!
Mencetak daftar kosong jika semua bilangan bulat muncul, coba online!
Penjelasan
sumber
U2
untuk mendapatkan awalan terpanjang di mana tidak ada pasangan yang berdekatan mengulangi.Python 3 , 78 byte
Cobalah online!
Mencetak satu set, jadi output untuk kasus uji kosong adalah
set()
, yang merupakan set kosong.sumber
R,
9286 byteTerima kasih kepada @Giuseppe karena telah menghemat 6 byte!
Cobalah online!
Implementasi yang cukup mudah ( versi sebelumnya , tetapi konsep yang sama):
sumber
setdiff
, ide bagus!1:k^2
pendekatan yang digunakan orang lainPython 3,
173152143131 byteTerima kasih khusus kepada @ovs.
Cobalah secara Online
Bagaimana cara kerjanya?
Fungsi pertama mengambil dua parameter m dan n, dan mengembalikan nomor Fibonacci mod m. Fungsi kedua loop melalui angka-angka Fibonacci mod k dan memeriksa apakah 0 dan 1 diulang. Ini menyimpan angka dalam daftar dan membandingkannya dengan daftar yang berisi angka 1-n. Nomor duplikat dihapus dan nomor yang tersisa dikembalikan.
sumber
set()
dan perbandingan dirantai.05AB1E , 10 byte
Cobalah online!
-3 byte terima kasih kepada Emigna.
sumber
Ruby , 47 byte
Cobalah online!
Meskipun menggunakan beberapa logika yang sama, ini tidak didasarkan pada Jawaban GB .
Penjelasan:
sumber
Gangguan Umum, 106 byte
Cobalah online!
sumber
Pari / GP , 55 byte
Cobalah online!
sumber
Elixir ,
148144 byteCobalah online!
Bukan jawaban yang sangat kompetitif, tetapi sangat menyenangkan untuk bermain golf! Elixir adalah bahasa yang cukup mudah dibaca, tetapi penjelasan untuk kekacauan karakter di tengah berikut.
Penjelasan ini ada dalam dua bagian, mod-fibonacci dan operasi di atasnya
Mod-fib:
Ini mengembalikan aliran mod fibonacci yang tak terbatas
x
. Itu dimulai dengan akumulator{1,1}
, dan menerapkan operasi tak terhingga berikut: akumulator yang diberikan{p,n}
, outputp mod x
ke aliran. Kemudian, atur akumulator ke{n,p+n}
.Sisanya:
sumber
SNOBOL4 (CSNOBOL4) , 153 byte
Cobalah online!
sumber
Ruby ,
5553 byteCobalah online!
sumber
JavaScript (ES6), 84 byte
sumber
Python 3, 76 byte
Ini hanya melihat siklus terpanjang yang mungkin dari angka Fibonnaci (n ^ 2), dan membuat daftar semua angka yang terjadi pada waktu itu. Untuk menyederhanakan logika angka disimpan modulo n.
sumber