Jika kita mendefinisikan Fibonacci seperti urutan sebagai f _k (n) = (f _k (n-1) + f _k (n-2))% k , untuk suatu bilangan bulat k (di mana % adalah operator Modulo), urutan akan selalu siklik, karena hanya ada k ² nilai yang berbeda untuk ( _fk (n-1), _fk (n-2)) . Namun, siklus ini biasanya tidak termasuk semua pasangan yang mungkin dari nilai-nilai, jadi tergantung pada dua nilai mulai f _k (0) dan f _k (1) , kita mungkin mendapatkan siklus yang berbeda. Misalnya, untuk k = 2, kami memiliki empat kemungkinan berikut, tergantung pada dua nilai pertama:

0, 0, 0, 0, 0, 0, 0, 0, 0, ...
0, 1, 1, 0, 1, 1, 0, 1, 1, ...
1, 0, 1, 1, 0, 1, 1, 0, 1, ...
1, 1, 0, 1, 1, 0, 1, 1, 0, ...

Karena sifat siklik dari urutan, sebenarnya hanya ada dua urutan yang berbeda secara fundamental di sini, dengan orbit (0) dan (0, 1, 1) . Mari kita lihat k = 3 :

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, ...
0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, ...
1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, ...
1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, ...
1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, ...
2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, ...
2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, ...
2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, ...

Sekali lagi, hanya ada dua orbit yang berbeda: (0) dan (0, 1, 1, 2, 0, 2, 2, 1) .

Untuk k yang lebih tinggi kita mungkin mendapatkan lebih banyak orbit, tetapi mereka masih akan jatuh ke dalam sejumlah kecil kelas yang sebanding. Misalnya k = 4 menghasilkan empat orbit (0) , (0,1,1,2,3,1) , (0, 2, 2) , (0, 3, 3, 2, 1, 3) dan k = 5 tiga orbit (0) , (0, 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 2, 4, 1) dan (1, 3, 4, 2) .

Tugas Anda dalam tantangan ini adalah untuk menghitung berapa banyak orbit yang dihasilkan oleh urutan untuk k . Ini adalah OEIS A015134 . Berikut adalah 100 nilai pertama (mulai dari k = 1 ):

1, 2, 2, 4, 3, 4, 4, 8, 5, 6, 14, 10, 7, 8, 12, 16, 9, 16, 22, 16,
29, 28, 12, 30, 13, 14, 14, 22, 63, 24, 34, 32, 39, 34, 30, 58, 19,
86, 32, 52, 43, 58, 22, 78, 39, 46, 70, 102, 25, 26, 42, 40, 27, 52,
160, 74, 63, 126, 62, 70, 63, 134, 104, 64, 57, 78, 34, 132, 101, 60,
74, 222, 37, 38, 62, 328, 89, 64, 82, 124, 41, 86, 42, 172, 75, 44,
184, 178, 181, 132, 82, 180, 99, 140, 104, 246, 49, 50, 114, 76

Pastikan untuk memeriksa k = 11 , yang merupakan input pertama yang menghasilkan lebih dari k orbit.

Aturan

Anda diberi bilangan bulat positif k dan harus menampilkan A015134 (k) .

Anda dapat menulis program atau fungsi dan menggunakan salah satu metode standar untuk menerima input dan memberikan output.

Anda dapat menggunakan bahasa pemrograman apa pun , tetapi perhatikan bahwa celah ini dilarang secara default.

Ini adalah kode-golf , sehingga jawaban terpendek yang valid - diukur dalam byte - menang.

Sekam , 17 16 byte

Lüȯ€U¡ȯ↔m%⁰∫π2ŀ⁰

Cobalah online!

Penjelasan

Lüȯ€U¡ȯ↔m%⁰∫π2ŀ⁰  Implicit input, say n=4.
              ŀ⁰  Lowered range: [0,1,2,3]
            π2    Cartesian second power: [[0,0],[0,1],[1,0],[0,2]..
 üȯ                Deduplicate with respect to this function:
   €U¡ȯ↔m%⁰∫       Arguments are two pairs, say a=[0,2], b=[1,1]
     ¡ȯ            Iterate on a:
           ∫       Cumulative sum,
        m%⁰        take modulo n of each,
       ↔           then reverse: [[0,2],[2,0],[2,2],[0,2],[2,0]..
    U              Cut at first repeated element: [[0,2],[2,0],[2,2]]
   €               Is b in this list? No, so they are distinct in ü.
L                 Number of remaining pairs.

Bash, 172 , 119 , 113 , 91 byte

n=$1;for((k=0;k<n*n;++k)){((H[k]||++c));for((;!H[k];k=(k/n+k)%n*n+k/n)){ H[k]=1;};};echo $c

Cobalah online

Bahasa Wolfram (Mathematica) , 76 70 byte

Tr[EdgeCycleMatrix[#->{#[[2]],Tr@#~Mod~n}&/@Tuples[Range[n=#]-1,2]]!]&

Cobalah online!

Bagaimana itu bekerja

Kami membuat grafik yang diberikan oleh aturan {{0,0}->{0,0}, {1,0}->{1,1}, ...}yang, mengingat dua elemen dari urutan Fibonacci umum, temukan modulo berikutnya n. The EdgeCycleMatrixmemberi matriks kejadian dari siklus ke tepi dalam grafik ini; kami ingin menghitung barisnya.

(Ada sejumlah built-in yang melakukan tugas serupa, tetapi ConnectedComponentslebih lama, dan FindCyclemembutuhkan banyak input tambahan untuk membuatnya bekerja. Selain itu, EdgeCycleMatrixadalah array persegi panjang, tidak berbentuk lucu seperti dua lainnya, yang membantu nanti. )

Untuk menghitung baris matriks, kita mengambil faktorial dari entri untuk mengubahnya menjadi matriks semua yang ada, lalu mengambil jejaknya. (Setiap siklus mengandung setidaknya satu sisi dan oleh karena itu ada setidaknya kolom sebanyak baris - jadi ini menghitung baris dan bukan kolom.)

MATL , 38 36 byte

:qt!J*+le"@GU:"t&Zjwy+G\J*+hu]S]Xhun

Cobalah online! Ini habis dalam kompiler online untuk input melebihi7 .

Penjelasan

Kode mendefinisikan orbit dalam bilangan kompleks, di mana bagian imajiner adalah istilah baru dan bagian nyata adalah istilah sebelumnya dalam urutan Fibonacci. Setiap nilai kompleks mengkodekan status urutan. Yaitu, mengingat a+jbnilai selanjutnya dihitung sebagai b+j(a+b).

Nilai awal yang mungkin adalah a+jbdengan a, bdi [0, 1, ..., k-1]. Untuk setiap nilai awal, kode ini berulang k^2kali. Sebenarnya, untuk membuat kode lebih pendek, setiap iterasi diterapkan semua nilai yang terakumulasi sejauh ini, dan hasilnya didupuplikasi (yang akan diperlukan pada akhirnya). Setelah iterasi terakhir, vektor dari nilai kompleks yang didupuplikasi diurutkan (berdasarkan nilai absolut, kemudian dengan sudut). Ini memberikan "tanda tangan" untuk setiap orbit.

Di akhir program, tanda tangan dikumpulkan ke dalam array sel. Jumlah tanda tangan unik adalah output yang diinginkan.

:q          % Implicit input: k. Push row vector [0, 1, ..., k-1]
t!          % Duplicate, transpose: gives column vector [0; 1; ...; k-1]
J*+         % Multiply by 1j, add with broadcast. Gives a k × k matrix of
            % values a+jb with a, b in [0, 1, ..., k-1]
le          % Linearize into a row vector
"           % For each c in that vector
  @         %   Push c
  GU:"      %   Do the following k^2 times
    t&Zj    %     Duplicate and split into real and imaginary parts: a, b
    wy+     %     Swap, duplicate, from below, add: transforms a, b into
            %     b, a+b. This is the basic step in the Fibonacci sequence
            %     In subsequent iterations a and b may be vectors instead
            %     of numbers, as they include all values obtained so far
    G\      %     Modulo k, element-wise
    J*+     %     Times 1j, add. Gives the next complex number for each of
            %     the complex numbers so far
    hu      %     Append to values so far and deduplicate. This may extend
            %     the vector of complex numbers
  ]         %   End
  S         %   Sort
]           % End
Xh          % Collect entire stack into a cell array
u           % Deduplicate
n           % Number of entries. Implicit display

Haskell , 196 191 byte

import Data.List
o(a:b)=1+o[x|x<-b,not$(0<$a)==(0<$x)&&isInfixOf a(x++x)]
o _=0
k#(a,b)=(b,mod(a+b)k)
p!(a:b)|elem a p=fst<$>p|r<-p++[a]=r!b
f k=o[[]!iterate(k#)(a,b)|a<-[0..k-1],b<-[0..k-1]]

Cobalah online!

Ini mungkin bisa diperbaiki. Terutama jika seseorang dapat menemukan cara untuk menghindari isInfixOfdan menghapus impor.

Ide dasarnya adalah membuat daftar "keadaan" (tupel yang berisi dua nilai sebelumnya) untuk melihat kapan mulai berputar. Kemudian kami memeriksa apakah setiap orbit berbeda dengan pendahulunya (benar-benar bekerja sebaliknya tetapi sulit untuk dikatakan). Untuk memeriksa apakah orbitnya sama, kami memeriksa apakah panjangnya sama dan apakah yang satu cocok dengan yang lain. Sebagai contoh [0,2,2], [2,2,0]: panjang baik adalah 3 dan [0,2,2,0,2,2]mengandung [2,2,0]sebagai subsequence terus menerus. Saya tidak yakin apakah itu sangat mudah tetapi tampaknya berhasil.

EDIT: terima kasih kepada Laikoni untuk melepas 5 byte! Saya harus membaca lebih banyak tips itu.

JavaScript (ES6), 337 335 byte

Maaf untuk algoritma brute-force Ω (k ^ 3).

(k,x=o=0,u=[],s=(q,w,v,j=d=0)=>{while(j++<v)d|=q.reduce((a,b,i)=>a&=b==w[(i+j)%v],1);return d})=>{for(;x<k;x++)for(y=0;y<k;y++){l=2;r=[x,y];do{r.push((c=(d=r[(l+=2)-3])+r[l-4])%k,(c+d)%k)}while(!(t=r.slice(0,h=l/2)).reduce((a,b,i)=>a&=b==r[i+h],1));if(!u.reduce((q,z)=>q|=(t.length-(a=z.length)?0:s(t,z,a)),0)){o++;u.push(t)}}return o}

Kinerja ... Ketika saya menghitung A015134 (sesuatu di luar k = 50) melebihi 60an pada TIO.

var g=(k,x=o=0,u=[],s=(q,w,v,j=d=0)=>{while(j++<v)d|=q.reduce((a,b,i)=>a&=b==w[(i+j)%v],1);return d})=>{for(;x<k;x++)for(y=0;y<k;y++){l=2;r=[x,y];do{r.push((c=(d=r[(l+=2)-3])+r[l-4])%k,(c+d)%k)}while(!(t=r.slice(0,h=l/2)).reduce((a,b,i)=>a&=b==r[i+h],1));if(!u.reduce((q,z)=>q|=(t.length-(a=z.length)?0:s(t,z,a)),0)){o++;u.push(t)}}return o}

for (var ix = 1; ix <= 15; ix++)
 console.log(`A015134(${ix}) = ${g(ix)}`);

Penjelasan (Tidak Disatukan)

function CheckIfSameOrbit(Array_1, Array_2, Length) { // Checks if the orbits are equal
  var d = false, j = 0;                               // Assume both have same length
  while (j < v) {                                     // Checks for different startings
    j++;                                                
    d |= Array_1.reduce(function(Acc, Item, Index) {  // Element-by-element comparison
      Acc &= Item == w[(Index + j) % v], 1);                     
    });                                               // Return true if any starting
  }                                                   // point makes two orbits identical
}

function A015134(k) {                                 // Main Program
  var o = 0, u = [];                                    
  for (var x = 0; x < k; x++) {                       // Checks different pairs of (x, y)
    for (var y = 0; y < k; y++) {
      var l = 2, r = [x, y], h = 1, t;
      do {                                            // Find until a complete orbit is
        l += 2;                                       // found (except for (0, 0) case)
        h = l / 2;
        var d = r[l - 3], c = r[l - 3] + r[l - 4];
        r.push(c % k, (c + d) % k);
        t = r.slice(0, h);
      }                                                 
      while (!t.reduce(function(Acc, Item, Index) {   // Which is, if 2 identical copies
        Acc &= Item == r[Index + h];                  // of the orbit are calculated
      }, 1));

      if (!u.reduce(function(Acc, Item) {             // If the orbit is a new one
        var a = Item.length;
        Acc |= (t.length - a ? 0 : s(t, Item, a));
      }, 0)) {
        o++;                                          // Increment the counter, and
        u.push(t);                                    // record it to the list
      }
    }
  }
  return o;                                           // Ultimately return the counter;
}

Perl 5, 80 + 1 (-p) byte

$n=$_;map{$a[$_]||++$\;$a[$_]++until$a[$_=0|($_/$n+$_)%$n*$n+$_/$n]}0..$n**2-1}{

Cobalah online

Jelly , 17 byte

Ṛ+\%³
Ḷṗ2ÇÐĿ€Ṣ€QL

Cobalah online!

JavaScript (ES6), 102 byte

k=>F=(a=0,b=0,C=0,q)=>q?F[q=[a,b%=k]]?0:1|F(b,a+b,C,F[q]=1):b<k?F(a,b+1,C+F(a,b,C,1)):++a<k?F(a,0,C):C

Mengembalikan fungsi yang mengembalikan hasilnya. Untuk 3 byte lebih, kita dapat mengembalikan hasilnya secara langsung:

k=>(F=(a,b,C,q)=>q?F[q=[a,b%=k]]?0:1|F(b,a+b,C,F[q]=1):b<k?F(a,b+1,C+F(a,b,C,1)):++a<k?F(a,0,C):C)(0,0,0)

Keduanya memiliki kompleksitas waktu O (n ² ).

Python 2 , 214 byte

def h(k):
 R=[]
 for p in[[i/k,i%k,(i/k+i%k)%k]for i in range(k*k)]:
	while p[:2]!=p[-2:]:
		p.append(sum(p[-2:])%k)
	p=p[:-2]
	if not any([p==x[i:]+x[:i]for i in range(len(p))for x in R]):R.append(p)
 print len(R)

Cobalah online!

Ini tidak terlalu efisien tetapi golf yang bisa saya lakukan.