cp's OEIS Frontend

A345530 Triangle T(n,k) read by rows of the number of n-bit words with maximum overlap k.

%I A345530 #19 Aug 11 2025 07:28:08
%S A345530 2,2,2,4,2,2,6,6,2,2,12,10,6,2,2,20,22,12,6,2,2,40,38,28,12,6,2,2,74,
%T A345530 82,48,30,12,6,2,2,148,154,106,52,30,12,6,2,2,284,318,198,118,54,30,
%U A345530 12,6,2,2,568,614,414,222,124,54,30,12,6,2,2
%N A345530 Triangle T(n,k) read by rows of the number of n-bit words with maximum overlap k.
%C A345530 Here an overlap means some initial part of the binary word matches exactly the end part of the word. More precisely if B = b_1,b_2,...,b_n is the word, and k is the largest value for which b_i=b_n-k+i for 1 <= i <= k, k < n, then B is said to have a maximum overlap of k. The smallest possible overlap is 0 and largest possible overlap is n-1.
%C A345530 The trivial overlap n=k is ignored.
%C A345530 All terms are even, because a word and its bitwise complement have the same maximum overlap.
%H A345530 Sean A. Irvine, <a href="/A345530/b345530.txt">Rows n=1..38 flattened</a>
%H A345530 H. Harborth, <a href="https://gdz.sub.uni-goettingen.de/id/PPN243919689_0271">Endliche 0-1-Folgen mit gleichen Teilblöcken</a>, J. für Reine Angewandte Math. 271 (1974), 139-154.
%H A345530 Sean A. Irvine, <a href="https://github.com/archmageirvine/joeis/blob/master/src/irvine/oeis/a345/A345530.java">Java program</a> (github)
%F A345530 Sum_{k=0..n-1} T(n,k) = 2^k.
%F A345530 T(n,0) = A003000(n).
%F A345530 T(n,1) = A019310(n).
%F A345530 T(n,2) = A019311(n).
%e A345530 For n=3, the maximum overlaps are as follows:
%e A345530   000 2,
%e A345530   001 0,
%e A345530   010 1,
%e A345530   011 0,
%e A345530   100 0,
%e A345530   101 1,
%e A345530   110 0,
%e A345530   111 2;
%e A345530 thus row 3 of the triangle is 4, 2, 2 (4 with overlap 0, 2 with overlap 1, 2 with overlap 2).
%e A345530 The triangle begins:
%e A345530    2;
%e A345530    2,  2;
%e A345530    4,  2, 2;
%e A345530    6,  6, 2, 2;
%e A345530   12, 10, 6, 2, 2;
%e A345530   20, 22, 12, 6, 2, 2;
%e A345530   ...
%o A345530 (Python)
%o A345530 def maxoverlap(n):
%o A345530     b = bin(n)[2:]
%o A345530     for k in range(len(b)-1, -1, -1):
%o A345530         if b.startswith(b[-k:]): return k
%o A345530 def T(n, k): return 2*sum(maxoverlap(i) == k for i in range(2**(n-1), 2**n))
%o A345530 print([T(n, k) for n in range(1, 12) for k in range(n)]) # _Michael S. Branicky_, Jun 24 2021
%o A345530 (Python) # faster version, using maxoverlap above
%o A345530 from collections import Counter
%o A345530 def row(n):
%o A345530     c = Counter(maxoverlap(i) for i in range(2**(n-1), 2**n))
%o A345530     return [2*c[k] for k in range(n)]
%o A345530 def table(r): return [i for n in range(1, r+1) for i in row(n)]
%o A345530 print(table(11)) # _Michael S. Branicky_, Jun 24 2021
%Y A345530 Cf. A003000, A019310, A019311, A345710.
%K A345530 nonn,tabl
%O A345530 1,1
%A A345530 _Sean A. Irvine_, Jun 20 2021