Temukan Angka yang Hilang di Fibonacci Sequence Mod K

20

Terinspirasi oleh pertanyaan Math.SE ini .

Latar Belakang

The Fibonacci urutan (disebut F) adalah urutan, mulai 0, 1sehingga 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

  • Celah default dilarang .

  • I / O bawaan .

  • Program atau fungsi dapat diterima .

  • 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 , jadi jawaban tersingkat di setiap bahasa menang.

Uji Kasus

Buat kasus uji online!

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 ...

Terkait:

Menghitung Orbital Fibonacci

Temukan Periode Pisano

pizzapants184
sumber
Kotak pasir (dihapus).
pizzapants184

Jawaban:

6

Jelly , 9 8 byte

²RÆḞ%ḟ@Ḷ

Cobalah online!

Berdasarkan periode pisanop(n) <= 6n mulai A001175 . Juga, p(n) <= 6n <= n^2untuk n >= 6dan p(n) <= n^2untuk n < 6. Disimpan byte ini berkat Dennis.

mil
sumber
²harus bekerja ×6.
Dennis
6

Haskell , 70 byte

Beberapa jumlah byte disimpan berkat Buah Esolanging

8 byte disimpan berkat Laikoni

a=1:scanl(+)1a
f x=[u|u<-[2..x-1],and[mod b x/=u|(_,b)<-zip[1..x^2]a]]

Cobalah online!

Wisaya Gandum
sumber
@EsolangingFruit Ah terima kasih! Saya sendiri sampai pada kesimpulan yang sama.
Wheat Wizard
read$showberfungsi alih-alih fromIntegerdalam kasus ini dan menyimpan dua byte.
Laikoni
Menggunakan zip[1..x^2]untuk memotong menghemat lebih banyak byte: Cobalah online!
Laikoni
@Laikoni Butuh waktu beberapa saat tapi saya membuat perubahan. Terima kasih, itu ide yang bagus.
Wheat Wizard
5

Perl 6 ,  43 42 39  32 byte

{^$_ (-)(1,1,(*+*)%$_...->\a,\b{!a&&b==1})}

Menguji

{^$_∖(1,1,(*+*)%$_...->\a,\b{!a&&b==1})}

Menguji

{^$_∖(1,1,(*+*)%$_...{!$^a&&$^b==1})}

Menguji

{^$_∖(1,1,(*+*)%$_...!*&*==1)}

Menguji

Diperluas:

{  # bare block lambda with implicit parameter 「$_」

  ^$_               # Range upto and excluding the input

                   # set minus (U+2216)

  (                 # generate the Fibonacci sequence mod k

    1, 1,           # seed the sequece (can't be 0,1)

    ( * + * ) % $_  # add two values and modulus the input (lambda)

    ...             # keep doing that until

                    # it matches 0,1
    !*              #   negate the first param (1 when 0)
    &               #   and Junction
    *               #   second param
    == 1            #   both match 1

  )
}
Brad Gilbert b2gills
sumber
3

> <> , 48 byte

01\
?!\:&+{:}%:1$0p&$:
v0\~:1=?
>?!;1-::0g?!nao:

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:

01\    Input is already on the stack
...... Initialises the sequence with 1 and 0
...... Goes to the second line
......

......
..\:&+{:}% Gets the next number in the modded Fibonacci sequence while preserving the previous number
......
......

......
..........:1$0p&$: Puts a 1 at that cell number on the first line
.......
.......

......             If the number is a 0 go to the third line
?!\..............: Check if the next number is a 1, meaning we've reached the end of the sequence
v0\~:1=?           Go to the fourth line if so
>.....             Re-add the 0 and go back to the second line if not

......           While input:
......             Get the cell from the first line
......             If not 0: print the number
>?!;1-::0g?!nao:   Finally, print a newline and decrement the input
Jo King
sumber
3

MATL , 19 18 byte

0lbU:"yy+]vG\G:qX~

Cobalah online!

-1 byte terima kasih kepada Guiseppe.

  bU:"   ]         % Do K^2 (>6K) times.
0l    yy+          %  Fibbonaci
                X~ % Set exclusive difference between
          vG\      %  the fibonacci numbers mod K
             G:q   %  and 0...K-1
Sanchises
sumber
18 byte ; menata ulang memulihkan penggunaan Anda X~!
Giuseppe
@Giuseppe Terima kasih! Masih sangat lama ....
Sanchises
2

Sekam , 13 12 10 byte

Terima kasih @Zgarb untuk -2 byte!

-U2m%⁰İfŀ⁰

Mencetak daftar kosong jika semua bilangan bulat muncul, coba online!

Penjelasan

-U2m%⁰İfŀ⁰  -- named argument ⁰, example with: 8
-           -- difference of
        ŀ⁰  -- | lowered range: [0,1,2,3,4,5,6,7]
            -- and
      İf    -- | Fibonacci sequence: [1,1,2,3,5,8,13,21,34,55,89,144,233,377…
   m%⁰      -- | map (modulo ⁰): [1,1,2,3,5,0,5,5,2,7,1,0,1,1…
 U2         -- | keep longest prefix until 2 adjacent elements repeats: [1,1,2,3,5,0,5,5,2,7,1,0,1]
            -- : [4,6]
ბიმო
sumber
Anda dapat menggunakan U2untuk mendapatkan awalan terpanjang di mana tidak ada pasangan yang berdekatan mengulangi.
Zgarb
2

Python 3 , 78 byte

def m(K):M=0,1;exec(K*6*'M+=sum(M[-2:])%max(K,2),;'+'print({*range(K)}-{*M})')

Cobalah online!

Mencetak satu set, jadi output untuk kasus uji kosong adalah set(), yang merupakan set kosong.

Erik the Outgolfer
sumber
@ovs maksudmu dengan Python 2, kan? tentu
Erik the Outgolfer
2

R, 92 86 byte

Terima kasih kepada @Giuseppe karena telah menghemat 6 byte!

function(k,n=!!0:2){while(any((z=tail(n,2))-n[1:2]))n=c(n,sum(z)%%k);setdiff(1:k-1,n)}

Cobalah online!

Implementasi yang cukup mudah ( versi sebelumnya , tetapi konsep yang sama):

function(k,
         K=1:k-1,      #Uses default arguments to preset variables for legibility 
         n=c(0,1,1)){  #(wouldn't change byte-count to put them in the body of the function)
    while(any((z=tail(n,2))!=n[1:2])) #Do as long as first 2 elements are not identical to last 2 elements
        n=c(n,sum(z)%%k) #Built the fibonacci mod k sequence
    K[!K%in%n] #Outputs integers < k if not in sequence.
}
plannapus
sumber
1
86 byte
Giuseppe
@Giuseppe ah setdiff, ide bagus!
plannapus
70 byte porting 1:k^2pendekatan yang digunakan orang lain
Giuseppe
2

Python 3, 173 152 143 131 byte

f=lambda n,m,a=0,b=1:a%m if n<=0else f(n-1,m,b,a+b)
p=lambda n,i=2,y={0}:y^{*range(n)}if f(i,n)==1>f(i-1,n)else p(n,i+1,y|{f(i,n)})

Terima 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.

Manish Kundu
sumber
Ini adalah bagian dari tajuk dan itu tidak wajib untuk dimasukkan dalam kode.
Manish Kundu
Oke, sudah selesai. @ovs Terima kasih sudah memberi tahu, saya tidak menyadarinya.
Manish Kundu
1
131 byte dengan membuat set dengan kurung keriting, bukan set()dan perbandingan dirantai.
Ovs
2

05AB1E , 10 byte

L<InLÅfI%K

Cobalah online!

-3 byte terima kasih kepada Emigna.

Tuan Xcoder
sumber
@Emigna Saya sudah lama mencari-cari built-in itu! Terima kasih!
Tn. Xcoder
2

Ruby , 47 byte

->n{a=b=1;[*1...n]-(1..n*n).map{a,b=b,a+b;a%n}}

Cobalah online!

Meskipun menggunakan beberapa logika yang sama, ini tidak didasarkan pada Jawaban GB .

Penjelasan:

->n{
  a=b=1;   # start sequence with 1,1
  [*1...n] # all the numbers from 1 to n-1 as an array
           # 0 is excluded as it should never be in the final answer 
  -  # set operation; get all items in the first set and not in the second
  (1..n*n).map{ # n squared times
    a,b=b,a+b;  # assign next fibonacci numbers 
    a%n         # return a fibonacci number mod n
  }    # Map to an array
}
MegaTom
sumber
2

Gangguan Umum, 106 byte

(lambda(k)(do((a 1 b)c(b 1(mod(+ a b)k)))((=(1- b)0 a)(dotimes(i k)(or(member i c)(print i))))(push a c)))

Cobalah online!

Renzo
sumber
1

Elixir , 148 144 byte

 fn x->Enum.to_list(1..x-1)--List.flatten Enum.take_while Stream.chunk(Stream.unfold({1,1},fn{p,n}->{rem(p,x),{n,p+n}}end),2),&Enum.sum(&1)!=1end

Cobalah 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:

Stream.unfold({1,1},fn{p,n}->{rem(p,x),{n,p+n}}end)

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}, output p mod xke aliran. Kemudian, atur akumulator ke{n,p+n} .

Sisanya:

fn x->                              Define a fxn f(x) that returns
  Enum.to_list(1..x-1)--            The numbers from 1..x-1 that are not in
  List.flatten                      The flattened list constructed by
    Enum.take_while                 Taking from mod-fib until
      Stream.chunk(                 A 2-size chunk
        Stream.unfold({1,1},fn{p,n}->{rem(p,x),{n,p+n}}end) (of mod fib)
        ,2)
      ,&Enum.sum(&1)!=1             sums to 1, representing [0,1] or [1,0]
end
Dave
sumber
1

SNOBOL4 (CSNOBOL4) , 153 byte

 k =input
 a =table()
 y =1
i z =remdr(x + y,k)
 a<z> =1
 x =y
 y =z
 i =lt(i,k * 6) i + 1 :s(i)
o output =eq(a<o>) lt(o,k) o
 o =lt(o,k) o + 1 :s(o)
end

Cobalah online!

Giuseppe
sumber
1

Ruby , 55 53 byte

->n{*a=0,b=1;(n*n).times{a<<(b+=a[-2])%n};[*1...n]-a}

Cobalah online!

GB
sumber
1

JavaScript (ES6), 84 byte

f=(n,a=0,b=1,q=[...Array(n).keys()])=>a*b+a-1?f(n,b,(a+b)%n,q,q[b]=0):q.filter(x=>x)
Produksi ETH
sumber
1

Python 3, 76 byte

def t(n,r=[1]):
 while n*n>len(r):r+=[sum(r[-2:])%n]
 return{*range(n)}-{*r}

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.

pengguna2699
sumber