cp's OEIS Frontend

A344018 Table read by rows: T(n,k) (n >= 1, 1 <= k <= 2^n) is the number of cycles of length k which can be produced by a general n-stage feedback shift register.

%I A344018 #47 Apr 16 2025 10:57:02
%S A344018 2,1,2,1,2,1,2,1,2,3,2,3,4,2,2,1,2,3,6,7,8,12,14,17,14,13,12,20,32,16,
%T A344018 2,1,2,3,6,9,12,20,32,57,78,113,154,208,300,406,538,703,842,1085,1310,
%U A344018 1465,1544,1570,1968,2132,2000,2480,2176,2816,4096,2048
%N A344018 Table read by rows: T(n,k) (n >= 1, 1 <= k <= 2^n) is the number of cycles of length k which can be produced by a general n-stage feedback shift register.
%C A344018 T(n,k) is the number of cycles of length k in the directed binary de Bruijn graph of order n.
%H A344018 Pontus von Brömssen, <a href="/A344018/b344018.txt">Rows n = 1..6, flattened</a>
%H A344018 Peter R. Bryant and J. Christensen, <a href="https://doi.org/10.1016/0097-3165(83)90004-3">The enumeration of shift register sequences</a>, Journal of Combinatorial Theory, Series A, Vol. 35, No. 2 (1983), 154-172.
%H A344018 Oscar Cabrera, <a href="https://doi.org/10.31224/4431">Introducing loop compression for encoding de Bruijn sequences</a>, engrXiv (2025) Art. No. 4431. See p. 13.
%F A344018 From _Pontus von Brömssen_, Jun 28 2021: (Start)
%F A344018 T(n,k) = A001037(k) for n >= k-1.
%F A344018 T(k-2,k) = A001037(k) - A000010(k).
%F A344018 T(k-3,k) = A001037(k) - 2*A346018(k,2) + 2 for k >= 5.
%F A344018 T(n,2^n-1) = 2*T(n,2^n) = 2*A016031(n).
%F A344018 (See page 157 in the paper by Bryant and Christensen.)
%F A344018 (End)
%F A344018 From _Pontus von Brömssen_, Jul 01 2021: (Start)
%F A344018 Conjectures by Bryant and Christensen (1983):
%F A344018 Conjecture 1: T(k-4,k) = A001037(k) - 4*A346018(k,3) - 2*gcd(k,2) + 10 for k >= 8.
%F A344018 Conjecture 2: T(k-5,k) = A001037(k) - 8*A346018(k,4) - gcd(k,3) + 19 for k >= 11.
%F A344018 Conjecture 3: T(k-6,k) = A001037(k) - 16*A346018(k,5) - 4*gcd(k,2) - 2*gcd(k,3) + 48 for k >= 15. (End)
%F A344018 Sum_{k=1..m} T(n, k) = A062692(m) for 1 <= m <= n + 1. - _C.S. Elder_, Nov 07 2023
%e A344018 The first four rows of the triangle are
%e A344018 2, 1,
%e A344018 2, 1, 2, 1,
%e A344018 2, 1, 2, 3, 2, 3, 4, 2,
%e A344018 2, 1, 2, 3, 6, 7, 8, 12, 14, 17, 14, 13, 12, 20, 32, 16,
%e A344018 ...
%o A344018 (Python)
%o A344018 import networkx as nx
%o A344018 def deBruijn(n): return nx.MultiDiGraph(((0, 0), (0, 0))) if n==0 else nx.line_graph(deBruijn(n-1))
%o A344018 def A344018_row(n):
%o A344018   a=[0]*2**n
%o A344018   for c in nx.simple_cycles(deBruijn(n)):
%o A344018     a[len(c)-1]+=1
%o A344018   return a # _Pontus von Brömssen_, Jun 28 2021
%Y A344018 Cf. A000010, A001037, A016031, A346018.
%Y A344018 Row sums: A306522.
%K A344018 nonn,tabf
%O A344018 1,1
%A A344018 _N. J. A. Sloane_, Jun 21 2021
%E A344018 More terms from _Pontus von Brömssen_, Jun 28 2021