Si nous définissons une séquence de type Fibonacci comme f _k (n) = (f _k (n-1) + f _k (n-2))% k , pour un entier k (où % est l'opérateur modulo), la séquence sera nécessairement cyclique, car il n'y a que k ² valeurs différentes pour (f _k (n-1), f _k (n-2)) . Cependant, ce cycle n'inclut généralement pas toutes les paires de valeurs possibles, donc en fonction des deux valeurs de départ f _k (0) et f _k (1) , nous pouvons obtenir des cycles différents. Par exemple, pour k = 2 , nous avons les quatre possibilités suivantes, en fonction des deux premières valeurs:

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

En raison de la nature cyclique des séquences, il n'y a vraiment que deux séquences fondamentalement différentes ici, avec les orbites (0) et (0, 1, 1) . Regardons 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, ...

Encore une fois, il n'y a que deux orbites différentes: (0) et (0, 1, 1, 2, 0, 2, 2, 1) .

Pour des k plus élevés, nous pourrions obtenir plus d'orbites, mais elles tomberont toujours dans un nombre relativement petit de classes. Par exemple, k = 4 donne les quatre orbites (0) , (0,1,1,2,3,1) , (0, 2, 2) , (0, 3, 3, 2, 1, 3) et k = 5 les trois orbites (0) , (0, 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1) et (1, 3, 4, 2) .

Votre tâche dans ce défi est de calculer le nombre d'orbites générées par la séquence pour un k . Il s'agit d' OEIS A015134 . Voici les 100 premières valeurs (à 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

Assurez-vous de vérifier k = 11 , qui est la première entrée qui produit plus de k orbites.

Règles

On vous donne un entier positif k et vous devriez sortir A015134 (k) .

Vous pouvez écrire un programme ou une fonction et utiliser l'une des méthodes standard de réception d'entrée et de sortie.

Vous pouvez utiliser n'importe quel langage de programmation , mais notez que ces failles sont interdites par défaut.

Il s'agit de code-golf , donc la réponse valide la plus courte - mesurée en octets - l'emporte.

Husk , 17 16 octets

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

Essayez-le en ligne!

Explication

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 octets

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

Essayez-le en ligne

Wolfram Language (Mathematica) , 76 70 octets

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

Essayez-le en ligne!

Comment ça fonctionne

Nous construisons le graphe donné par les règles {{0,0}->{0,0}, {1,0}->{1,1}, ...}qui, étant donné deux éléments d'une séquence de Fibonacci généralisée, trouvent le suivant modulon . leEdgeCycleMatrix donne la matrice d'incidence des cycles aux bords dans ce graphique; nous voulons compter ses lignes.

(Il existe un certain nombre de fonctions intégrées qui effectuent une tâche similaire, mais ConnectedComponentssont plus longues et FindCyclenécessitent de nombreuses entrées supplémentaires pour le faire fonctionner.EdgeCycleMatrix . )

Pour compter les lignes de la matrice, nous prenons la factorielle des entrées pour la transformer en une matrice de toutes celles-ci, puis prenons la trace. (Chaque cycle contient au moins un bord et donc il y a au moins autant de colonnes que de lignes - donc cela compte les lignes et non les colonnes.)

MATL , 38 36 octets

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

Essayez-le en ligne! Il expire dans le compilateur en ligne pour le dépassement d'entrée7.

Explication

Le code définit les orbites en termes de nombres complexes, où la partie imaginaire est le nouveau terme et la partie réelle est le terme précédent dans la séquence de Fibonacci. Chaque valeur complexe code l' état de la séquence. À savoir, étant donné que a+jbla valeur suivante est calculée comme b+j(a+b).

Les valeurs de départ possibles sont a+jbavec a, ben [0, 1, ..., k-1]. Pour chaque valeur de départ, le code réitère les k^2temps. En fait, pour raccourcir le code, chaque itération est appliquée à tous les valeurs accumulées jusqu'à présent, et les résultats sont dédoublonnés (ce qui serait nécessaire à la fin de toute façon). Après la dernière itération, le vecteur de valeurs complexes dédupliquées est trié (par valeur absolue, puis par angle). Cela donne une "signature" pour chaque orbite.

À la fin du programme, les signatures sont collectées dans un tableau de cellules. Le nombre de signatures uniques est la sortie souhaitée.

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

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

Essayez-le en ligne!

Cela pourrait probablement être amélioré. Surtout si quelqu'un peut trouver un moyen d'éviter isInfixOfet de supprimer l'importation.

L'idée de base est de générer une liste "d'états" (tuples contenant les deux valeurs précédentes) pour voir quand il commence à faire un cycle. Ensuite, nous vérifions si chaque orbite est différente de ses prédécesseurs (fonctionne vraiment dans l'autre sens mais c'est difficile à mettre en mots). Pour vérifier si les orbites sont les mêmes, nous vérifions si la longueur est la même et si l'une s'inscrit dans l'autre concaténée avec elle-même. Par exemple [0,2,2], [2,2,0]: longueur des deux est 3 et [0,2,2,0,2,2]contient en [2,2,0]tant que séquence continue. Je ne sais pas si c'est infaillible mais cela semble fonctionner.

EDIT: merci à Laikoni pour avoir décollé 5 octets! J'aurais dû lire plus de ces conseils.

JavaScript (ES6), 337 335 octets

Désolé pour l'algorithme de force brute Ω (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}

Les performances ... Lorsque je calculais A015134 (quelque chose au-delà de k = 50), il dépassait la limite des 60 sur 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)}`);

Explication (non golfée)

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) octets

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

Essayez-le en ligne

Gelée , 17 octets

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

Essayez-le en ligne!

JavaScript (ES6), 102 octets

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

Renvoie une fonction qui renvoie le résultat. Pour 3 octets supplémentaires, nous pouvons lui faire retourner le résultat directement:

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)

Les deux ont une complexité temporelle O (n ² ).

Python 2 , 214 octets

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)

Essayez-le en ligne!

Ce n'est pas très efficace mais c'est le plus golfique que je puisse faire.