Si definimos una secuencia similar a Fibonacci como f _k (n) = (f _k (n-1) + f _k (n-2))% k , para algún entero k (donde % es el operador del módulo), la secuencia necesariamente será cíclico, porque solo hay k ² valores diferentes para (f _k (n-1), f _k (n-2)) . Sin embargo, este ciclo generalmente no incluye todos los pares de valores posibles, por lo que dependiendo de los dos valores iniciales f _k (0) y f _k (1) , podríamos obtener diferentes ciclos. Por ejemplo, para k = 2, tenemos las siguientes cuatro posibilidades, dependiendo de los dos primeros valores:

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

Debido a la naturaleza cíclica de las secuencias, aquí solo hay dos secuencias fundamentalmente diferentes, con las órbitas (0) y (0, 1, 1) . Veamos 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, ...

Nuevamente, solo hay dos órbitas diferentes: (0) y (0, 1, 1, 2, 0, 2, 2, 1) .

Para k más altos podríamos obtener más órbitas, pero aún caerán en un número comparativamente pequeño de clases. Por ejemplo k = 4 rendimientos los cuatro órbitas (0) , (0,1,1,2,3,1) , (0, 2, 2) , (0, 3, 3, 2, 1, 3) y k = 5 las tres órbitas (0) , (0, 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1) y (1, 3, 4, 2) .

Su tarea en este desafío es calcular cuántas órbitas genera la secuencia para una k dada . Este es OEIS A015134 . Aquí están los primeros 100 valores (a partir de 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

Asegúrese de verificar k = 11 , que es la primera entrada que produce más de k órbitas.

Reglas

Se le da un entero positivo k y debe generar A015134 (k) .

Puede escribir un programa o una función y utilizar cualquiera de los métodos estándar para recibir entradas y proporcionar salidas.

Puede usar cualquier lenguaje de programación , pero tenga en cuenta que estas lagunas están prohibidas de forma predeterminada.

Este es el código de golf , por lo que gana la respuesta válida más corta, medida en bytes .

Casco , 17 16 bytes

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

Pruébalo en línea!

Explicación

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 bytes

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

Pruébalo en línea

Wolfram Language (Mathematica) , 76 70 bytes

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

Pruébalo en línea!

Cómo funciona

Construimos el gráfico dado por las reglas {{0,0}->{0,0}, {1,0}->{1,1}, ...}que, dados dos elementos de una secuencia de Fibonacci generalizada, encuentran el siguiente módulo n. El EdgeCycleMatrixda la matriz de incidencia de ciclos a bordes en este gráfico; Queremos contar sus filas.

(Hay una serie de funciones integradas que realizan una tarea similar, pero ConnectedComponentses más larga y FindCyclenecesita muchas entradas adicionales para que funcione. Además, EdgeCycleMatrixes una matriz rectangular, no de forma divertida como las otras dos, que ayuda más adelante. )

Para contar las filas de la matriz, tomamos el factorial de las entradas para convertirlo en una matriz de todas, luego tomamos el rastro. (Cada ciclo contiene al menos un borde y, por lo tanto, hay al menos tantas columnas como filas, por lo que esto cuenta las filas y no las columnas).

MATL , 38 36 bytes

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

Pruébalo en línea! Se agota el tiempo de espera en el compilador en línea por exceder la entrada7.

Explicación

El código define las órbitas en términos de números complejos, donde la parte imaginaria es el nuevo término y la parte real es el término precedente en la secuencia de Fibonacci. Cada valor complejo codifica el estado de la secuencia. A saber, dado a+jbel siguiente valor se calcula como b+j(a+b).

Los posibles valores iniciales son a+jbcon a, bin [0, 1, ..., k-1]. Para cada valor inicial, el código itera k^2veces. En realidad, para acortar el código, cada iteración se aplica a todos los valores acumulados hasta el momento, y los resultados se deduplican (lo que sería necesario al final de todos modos). Después de la última iteración, el vector de valores complejos deduplicados se ordena (por valor absoluto, luego por ángulo). Esto le da una "firma" para cada órbita.

Al final del programa, las firmas se recopilan en una matriz de celdas. El número de firmas únicas es la salida deseada.

: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 , 196191 bytes

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

Pruébalo en línea!

Esto probablemente podría mejorarse. Particularmente si alguien puede encontrar una manera de evitar isInfixOfy eliminar la importación.

La idea básica es generar una lista de "estados" (tuplas que contienen los dos valores anteriores) para ver cuándo comienza a circular. Luego verificamos si cada órbita es diferente a sus predecesoras (realmente funciona al revés, pero es difícil de expresar con palabras). Para verificar si las órbitas son iguales, verificamos si la longitud es la misma y si una encaja en la otra concatenada consigo misma. Por ejemplo [0,2,2], [2,2,0]: longitud de ambos es 3 y [0,2,2,0,2,2]contiene [2,2,0]como una subsecuencia continua. No estoy seguro de si es infalible, pero parece funcionar.

EDITAR: gracias a Laikoni por despegar 5 bytes! Debería haber leído más de esos consejos.

JavaScript (ES6), 337 335 bytes

Perdón por el algoritmo de fuerza bruta Ω (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}

El rendimiento ... Cuando estaba calculando A015134 (algo más allá de k = 50) superó el límite de 60 s en 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)}`);

Explicación (sin 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) bytes

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

Pruébalo en línea

Jalea , 17 bytes

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

Pruébalo en línea!

JavaScript (ES6), 102 bytes

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

Devuelve una función que devuelve el resultado. Para 3 bytes más podemos hacer que devuelva el resultado directamente:

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)

Ambos tienen complejidad temporal O (n ² ).

Python 2 , 214 bytes

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)

Pruébalo en línea!

No es muy eficiente, pero es el más golfista que podría hacer.