Подсчет орбит Фибоначчи

13

Если мы определим последовательность, подобную Фибоначчи, как f k (n) = (f k (n-1) + f k (n-2))% k , для некоторого целого числа k (где % - оператор по модулю), последовательность будет обязательно циклическим, потому что есть только k 2 различных значения для (f k (n-1), f k (n-2)) . Однако этот цикл обычно не включает все возможные пары значений, поэтому в зависимости от двух начальных значений f k (0) и f k (1) мы можем получить разные циклы. Например, для k = 2 у нас есть следующие четыре возможности, в зависимости от первых двух значений:

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

Из-за циклической природы последовательностей здесь действительно только две принципиально разные последовательности с орбитами (0) и (0, 1, 1) . Давайте посмотрим на к = 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, ...

Опять же, есть только две разные орбиты: (0) и (0, 1, 1, 2, 0, 2, 2, 1) .

Для более высоких k мы можем получить больше орбит, но они все равно попадут в сравнительно небольшое количество классов. Например, k = 4 дает четыре орбиты (0) , (0,1,1,2,3,1) , (0, 2, 2) , (0, 3, 3, 2, 1, 3) и k = 5 три орбиты (0) , (0, 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1) и (1, 3, 4, 2) .

Ваша задача в этой задаче - вычислить, сколько орбит последовательность генерирует для данного k . Это OEIS A015134 . Вот первые 100 значений (начиная с 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

Удостоверьтесь, чтобы проверить k = 11 , который является первым входом, который дает больше чем k орбит.

правила

Вам дано положительное целое число k, и вы должны вывести A015134 (k) .

Вы можете написать программу или функцию и использовать любой из стандартных методов получения ввода и предоставления вывода.

Вы можете использовать любой язык программирования , но учтите, что эти лазейки по умолчанию запрещены.

Это код-гольф , поэтому самый короткий действительный ответ - измеренный в байтах - выигрывает.

code-golf sequence number-theory combinatorics fibonacci Мартин Эндер
источник
3
Это достаточно близко к codegolf.stackexchange.com/q/26578/194, что я не буду закрывать его в одностороннем порядке, но я бы отдал 5-е голосование, чтобы закрыть его, как обман.
Питер Тейлор

Ответы:

3

Шелуха , 17 16 байт

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

Попробуйте онлайн!

объяснение

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.
Zgarb
источник
1

Wolfram Language (Mathematica) , 76 70 байт

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

Попробуйте онлайн!

Как это устроено

Построим граф, заданный по правилам, {{0,0}->{0,0}, {1,0}->{1,1}, ...}которые по двум элементам обобщенной последовательности Фибоначчи находят следующий по модулю n. EdgeCycleMatrix дает матрицу инцидентности от циклов до ребер в этом графе; мы хотим посчитать его строки.

(Существует ряд встроенных модулей, выполняющих аналогичную задачу, но ConnectedComponentsболее длинных, и для их работы FindCycleтребуется много дополнительных входных данных. Кроме того, EdgeCycleMatrixэто прямоугольный массив, не такой смешной, как у двух других, что помогает позже. )

Чтобы посчитать строки матрицы, мы берем факториал записей, чтобы превратить его в матрицу всех единиц, а затем берем трассировку. (Каждый цикл содержит по крайней мере одно ребро и, следовательно, столбцов, по крайней мере, столько же, сколько строк - поэтому здесь учитываются строки, а не столбцы.)

Миша лавров
источник
1

MATL , 38 36 байт

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

Попробуйте онлайн! Тайм-аут в онлайн-компиляторе для превышения ввода7.

объяснение

Код определяет орбиты в терминах комплексных чисел, где мнимая часть - это новый термин, а действительная часть - предыдущий член в последовательности Фибоначчи. Каждое комплексное значение кодирует состояние последовательности. А именно, учитывая a+jbследующее значение вычисляется как b+j(a+b).

Возможные начальные значения a+jbс a, bв [0, 1, ..., k-1]. Для каждого начального значения код повторяется k^2раз. На самом деле, чтобы сделать код короче, каждая итерация применяется ко всем накопленным таким образом значениям, и результаты дедуплицируются (что будет необходимо в конце концов). После последней итерации вектор дедуплицированных комплексных значений сортируется (по абсолютному значению, а затем по углу). Это дает «подпись» для каждой орбиты.

В конце программы подписи собираются в массив ячеек. Количество уникальных подписей является желаемым результатом.

: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
Луис Мендо
источник
1

Haskell , 196 191 байт

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

Попробуйте онлайн!

Это может быть улучшено. Особенно, если кто-то может найти способ избежатьisInfixOf и удалить импорт.

Основная идея состоит в том, чтобы сгенерировать список «состояний» (кортежей, содержащих два предыдущих значения), чтобы увидеть, когда он начинает цикл. Затем мы проверяем, отличается ли каждая орбита от своих предшественников (действительно работает наоборот, но это трудно выразить словами). Чтобы проверить, одинаковы ли орбиты, мы проверяем, одинакова ли длина и совпадает ли одна с другой. Например [0,2,2], [2,2,0]: длина обоих равно 3 , и [0,2,2,0,2,2]содержит [2,2,0]как непрерывную подпоследовательности. Я не уверен, что это надежно, но, похоже, работает.

РЕДАКТИРОВАТЬ: спасибо Laikoni за удаление 5 байтов! Я должен был прочитать больше этих советов.

user1472751
источник
1
Похоже, вы можете использовать этот совет, чтобы избежать length. Другой байт можно сохранить !с помощью |r<-p++[a]=r!b.
Лайкони
0

JavaScript (ES6), 337 335 байт

Извините за Ω (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}

Производительность ... Когда я вычислял A015134 (что-то выше k = 50), он превышал предел 60 с на 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)}`);
Развернуть фрагмент

Объяснение (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;
}
Сиеру Асакото
источник
0

JavaScript (ES6), 102 байта

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

Возвращает функцию, которая возвращает результат. Еще 3 байта мы можем сделать так, чтобы он возвращал результат напрямую:

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)

Оба имеют временную сложность O (n 2 ).

ETHproductions
источник
0

Python 2 , 214 байтов

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)

Попробуйте онлайн!

Это не очень эффективно, но это самое лучшее, что я мог сделать.

dylnan
источник