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.
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, 2, 1, 2, 3, 6, 9, 12, 20, 32, 57, 78, 113, 154, 208, 300, 406, 538, 703, 842, 1085, 1310, 1465, 1544, 1570, 1968, 2132, 2000, 2480, 2176, 2816, 4096, 2048
Offset: 1
Examples
The first four rows of the triangle are 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, ...
Links
- Pontus von Brömssen, Rows n = 1..6, flattened
- Peter R. Bryant and J. Christensen, The enumeration of shift register sequences, Journal of Combinatorial Theory, Series A, Vol. 35, No. 2 (1983), 154-172.
- Oscar Cabrera, Introducing loop compression for encoding de Bruijn sequences, engrXiv (2025) Art. No. 4431. See p. 13.
Programs
-
Python
import networkx as nx def deBruijn(n): return nx.MultiDiGraph(((0, 0), (0, 0))) if n==0 else nx.line_graph(deBruijn(n-1)) def A344018_row(n): a=[0]*2**n for c in nx.simple_cycles(deBruijn(n)): a[len(c)-1]+=1 return a # Pontus von Brömssen, Jun 28 2021
Formula
From Pontus von Brömssen, Jun 28 2021: (Start)
T(n,k) = A001037(k) for n >= k-1.
T(n,2^n-1) = 2*T(n,2^n) = 2*A016031(n).
(See page 157 in the paper by Bryant and Christensen.)
(End)
From Pontus von Brömssen, Jul 01 2021: (Start)
Conjectures by Bryant and Christensen (1983):
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)
Sum_{k=1..m} T(n, k) = A062692(m) for 1 <= m <= n + 1. - C.S. Elder, Nov 07 2023
Extensions
More terms from Pontus von Brömssen, Jun 28 2021
Comments