Se definirmos uma sequência semelhante a Fibonacci como f _k (n) = (f _k (n-1) + f _k (n-2))% k , para algum número inteiro k (onde % é o operador de módulo), a sequência será necessariamente cíclico, porque existem apenas k ² valores diferentes para (f _k (n-1), f _k (n-2)) . No entanto, este ciclo geralmente não inclui todos os possíveis pares de valores, assim, dependendo dos dois valores a partir de f _k (0) e f _k (1) , podemos obter diferentes ciclos. Por exemplo, para k = 2, temos as quatro possibilidades a seguir, dependendo dos dois primeiros 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, ...

Devido à natureza cíclica das seqüências, existem realmente apenas duas seqüências fundamentalmente diferentes aqui, com as órbitas (0) e (0, 1, 1) . Vejamos 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, ...

Novamente, existem apenas duas órbitas diferentes: (0) e (0, 1, 1, 2, 0, 2, 2, 1) .

Para k mais alto, podemos obter mais órbitas, mas elas ainda se enquadram em um número comparativamente pequeno de classes. Por exemplo, k = 4 produz as quatro órbitas (0) , (0,1,1,2,3,1) , (0, 2, 2) , (0, 3, 3, 2, 1, 3) e k = 5 as três órbitas (0) , (0, 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1) e (1, 3, 4, 2) .

Sua tarefa neste desafio é calcular quantas órbitas a sequência gera para um determinado k . Este é o OEIS A015134 . Aqui estão os primeiros 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

Certifique-se de verificar k = 11 , que é a primeira entrada que gera mais de k órbitas.

Regras

Você recebe um número inteiro positivo k e deve gerar A015134 (k) .

Você pode escrever um programa ou uma função e usar qualquer um dos métodos padrão de recebimento de entrada e saída.

Você pode usar qualquer linguagem de programação , mas observe que essas brechas são proibidas por padrão.

Isso é código-golfe , então a resposta mais curta e válida - medida em bytes - vence.

Casca , 17 16 bytes

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

Experimente online!

Explicação

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

Experimente online

Wolfram Language (Mathematica) , 76 70 bytes

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

Experimente online!

Como funciona

Construímos o gráfico dado pelas regras {{0,0}->{0,0}, {1,0}->{1,1}, ...}que, dados dois elementos de uma seqüência generalizada de Fibonacci, encontram o próximo módulo n. O EdgeCycleMatrixfornece a matriz de incidência de ciclos para bordas neste gráfico; queremos contar suas linhas.

(Existem vários built-ins que executam uma tarefa semelhante, mas ConnectedComponentssão mais longos e FindCycleprecisam de muitas entradas extras para fazê-lo funcionar. Além disso, EdgeCycleMatrixexiste uma matriz retangular, sem formato engraçado como os outros dois, o que ajuda mais tarde. )

Para contar as linhas da matriz, pegamos o fatorial das entradas para transformá-lo em uma matriz de todas, e depois pegamos o rastreio. (Cada ciclo contém pelo menos uma aresta e, portanto, há pelo menos tantas colunas quanto linhas - portanto, isso conta as linhas e não as colunas.)

MATL , 38 36 bytes

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

Experimente online! Ele atinge o tempo limite no compilador online para exceder a entrada7.

Explicação

O código define órbitas em termos de números complexos, onde a parte imaginária é o novo termo e a parte real é o termo anterior na sequência de Fibonacci. Cada valor complexo codifica o estado da sequência. Ou seja, dado a+jbo próximo valor é calculado como b+j(a+b).

Os possíveis valores iniciais estão a+jbcom a, bem [0, 1, ..., k-1]. Para cada valor inicial, o código itera k^2vezes. Na verdade, para tornar o código mais curto, cada iteração é aplicada a todos os valores acumulados até o momento e os resultados são deduplicados (o que seria necessário no final). Após a última iteração, o vetor de valores complexos deduplicados é classificado (por valor absoluto e depois por ângulo). Isso fornece uma "assinatura" para cada órbita.

No final do programa, as assinaturas são coletadas em uma matriz de células. O número de assinaturas exclusivas é a saída desejada.

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

Experimente online!

Provavelmente isso poderia ser melhorado. Especialmente se alguém puder encontrar uma maneira de evitar isInfixOfe remover a importação.

A idéia básica é gerar uma lista de "estados" (tuplas contendo os dois valores anteriores) para ver quando começa a circular. Em seguida, verificamos se cada órbita é diferente dos seus antecessores (realmente funciona ao contrário, mas é difícil colocar em palavras). Para verificar se as órbitas são iguais, verificamos se o comprimento é o mesmo e se uma se encaixa na outra concatenada consigo mesma. Por exemplo [0,2,2], [2,2,0]: comprimento de ambos é 3 e [0,2,2,0,2,2]contém [2,2,0]como uma subsequência contínua. Não tenho certeza se é infalível, mas parece funcionar.

EDIT: obrigado a Laikoni por descolar 5 bytes! Eu deveria ter lido mais dessas dicas.

JavaScript (ES6), 337 335 bytes

Desculpe pelo algoritmo de força 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}

O desempenho ... Quando eu estava calculando A015134 (algo além de k = 50), excedia o limite de 60s no 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)}`);

Explicação (Ungolfed)

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}{

Experimente online

Gelatina , 17 bytes

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

Experimente online!

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

Retorna uma função que retorna o resultado. Para mais 3 bytes, podemos retornar o resultado diretamente:

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 possuem complexidade 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)

Experimente online!

Não é muito eficiente, mas é o golfe que eu poderia fazer.