Jeśli zdefiniujemy sekwencję podobną do Fibonacciego jako f _k (n) = (f _k (n-1) + f _k (n-2))% k , dla niektórych liczb całkowitych k (gdzie % jest operatorem modulo), sekwencja będzie koniecznie cykliczne, ponieważ istnieją tylko k ² różnych wartości dla (f _k (n-1), f _k (n-2)) . Jednak ten cykl zwykle nie obejmuje wszystkich możliwych par wartości, więc w zależności od dwóch początkowych wartości f _k (0) i f _k (1) , możemy uzyskać różne cykle. Na przykład dla k = 2, mamy następujące cztery możliwości, w zależności od dwóch pierwszych wartości:

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

Ze względu na cykliczną naturę sekwencji, tak naprawdę istnieją tutaj tylko dwie zasadniczo różne sekwencje, z orbitami (0) i (0, 1, 1) . Spójrzmy na 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, ...

Ponownie istnieją tylko dwie różne orbity: (0) i (0, 1, 1, 2, 0, 2, 2, 1) .

Dla wyższych k możemy uzyskać więcej orbit, ale nadal będą one należeć do stosunkowo niewielkiej liczby klas. Na przykład k = 4 daje cztery orbity (0) , (0,1,1,2,3,1) , (0, 2, 2) , (0, 3, 3, 2, 1, 3) i k = 5 trzy orbity (0) , (0, 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1) i (1, 3, 4, 2) .

Twoim zadaniem w tym wyzwaniu jest obliczenie, ile orbit generuje sekwencja dla danego k . To jest OEIS A015134 . Oto pierwsze 100 wartości (od 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

Pamiętaj, aby sprawdzić k = 11 , która jest pierwszym wejściem, który daje więcej niż k orbit.

Zasady

Otrzymałeś dodatnią liczbę całkowitą k i powinieneś wyprowadzić A015134 (k) .

Możesz napisać program lub funkcję i użyć dowolnej ze standardowych metod odbierania danych wejściowych i dostarczania danych wyjściowych.

Możesz używać dowolnego języka programowania , ale pamiętaj, że te luki są domyślnie zabronione.

To jest golf golfowy , więc wygrywa najkrótsza ważna odpowiedź - mierzona w bajtach .

Łuska , 17 16 bajtów

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

Wypróbuj online!

Wyjaśnienie

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 bajtów

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

Wypróbuj online

Wolfram Language (Mathematica) , 76 70 bajtów

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

Wypróbuj online!

Jak to działa

Konstruujemy wykres podany na podstawie reguł, {{0,0}->{0,0}, {1,0}->{1,1}, ...}które, biorąc pod uwagę dwa elementy uogólnionej sekwencji Fibonacciego, znajdują następny modulo n. EdgeCycleMatrixDaje matrycy przypadku z cykli do krawędzi w wykresie; chcemy policzyć jego rzędy.

(Istnieje wiele wbudowanych funkcji, które wykonują podobne zadanie, ale ConnectedComponentssą dłuższe i FindCyclewymagają wielu dodatkowych danych wejściowych, aby działało. Poza tym EdgeCycleMatrixjest prostokątna tablica, która nie ma zabawnego kształtu, jak pozostałe dwa, co pomaga później. )

Aby policzyć rzędy macierzy, bierzemy silnię wpisów, aby przekształcić ją w macierz wszystkich, a następnie pobieramy ślad. (Każdy cykl zawiera co najmniej jedną krawędź i dlatego jest co najmniej tyle kolumn, ile wierszy - więc liczy się to wiersze, a nie kolumny).

MATL , 38 36 bajtów

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

Wypróbuj online! Przekracza limit czasu w internetowym kompilatorze na przekroczenie danych wejściowych7.

Wyjaśnienie

Kod definiuje orbity w kategoriach liczb zespolonych, w których wyimaginowana część jest nowym terminem, a rzeczywista część jest poprzednim terminem w sekwencji Fibonacciego. Każda wartość zespolona koduje stan sekwencji. Mianowicie, biorąc a+jbpod uwagę następną wartość, jest obliczana jako b+j(a+b).

Dopuszczalne wartości wyjściowe są a+jbz a, bw [0, 1, ..., k-1]. Dla każdej wartości początkowej kod iteruje k^2czasy. W rzeczywistości, aby skrócić kod, każda iteracja jest stosowana do wszystkich dotychczas zgromadzonych wartości, a wyniki są deduplikowane (co i tak byłoby konieczne na końcu). Po ostatniej iteracji wektor deduplikowanych wartości zespolonych jest sortowany (według wartości bezwzględnej, a następnie według kąta). To daje „podpis” dla każdej orbity.

Pod koniec programu podpisy są gromadzone w tablicy komórkowej. Liczba unikatowych podpisów jest pożądanym wynikiem.

: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 bajtów

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

Wypróbuj online!

Można to prawdopodobnie poprawić. Zwłaszcza jeśli ktoś może znaleźć sposób na uniknięcie isInfixOfi usunięcie importu.

Podstawową ideą jest wygenerowanie listy „stanów” (krotek zawierających dwie poprzednie wartości), aby zobaczyć, kiedy zaczyna się cykl. Następnie sprawdzamy, czy każda orbita różni się od swoich poprzedników (naprawdę działa na odwrót, ale trudno to wyrazić słowami). Aby sprawdzić, czy orbity są takie same, sprawdzamy, czy długość jest taka sama i czy jedna pasuje do drugiej połączonej ze sobą. Na przykład [0,2,2], [2,2,0]: Długość obu oznacza 3 i [0,2,2,0,2,2]zawiera [2,2,0]jako ciągłą podciągu. Nie jestem pewien, czy jest niezawodny, ale wydaje się, że działa.

EDYCJA: dzięki Laikoni za zdjęcie 5 bajtów! Powinienem był przeczytać więcej tych wskazówek.

JavaScript (ES6), 337 335 bajtów

Przepraszam za algorytm brutalnej siły Ω (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}

Wydajność ... Kiedy obliczałem A015134 (coś więcej niż k = 50), przekroczyłem limit 60 s dla 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)}`);

Wyjaśnienie (nie golf)

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) bajtów

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

Wypróbuj online

Galaretka , 17 bajtów

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

Wypróbuj online!

JavaScript (ES6), 102 bajty

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

Zwraca funkcję, która zwraca wynik. W przypadku 3 kolejnych bajtów możemy zwrócić wynik bezpośrednio:

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)

Oba mają złożoność czasową O (n ² ).

Python 2 , 214 bajtów

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)

Wypróbuj online!

Nie jest zbyt wydajny, ale jest to najbardziej golfowy, jaki mogłem zrobić.