A156025 Number of n-bit numbers whose binary representation's substrings represent the maximal number (A112509(n)) of distinct integers.

2, 1, 1, 3, 2, 6, 5, 1, 4, 5, 2, 8, 10, 4, 16, 22, 12, 2, 10, 19, 17, 7, 1, 5, 9, 7, 2, 11, 24, 28, 20, 9, 2, 10, 18, 14, 4, 26, 68, 94, 78, 44, 18, 4, 22, 46, 46, 22, 4, 29, 104, 4, 20, 36, 28, 8, 52, 140, 202, 168, 80, 20, 2, 14, 40, 60, 50, 22, 4, 152, 23, 2

Offset: 1

Author

Joseph Myers, Feb 01 2009

Keywords

• nonn
• base

Comments

If only positive integer substrings are counted (see A156022), the first two terms become 1,2 (the n-bit numbers in question being 1, 10, 11 in binary) and all subsequent terms are unchanged.

Examples

			The n-bit numbers in question are, in binary, for n <= 8: 0 1; 10; 110; 1100 1101 1110, 11100 11101; 111000 111001 111010 111011 111100 111101; 1110100 1111000 1111001 1111010 1111011; 11110100.
		

Links

• Martin Fuller, Table of n, a(n) for n = 1..80
• 2008/9 British Mathematical Olympiad Round 2, Problem 4, Jan 29 2009.

Crossrefs

Cf. A078822, A112509 (corresponding maximum), A112510 (least such number), A112511 (greatest such number), A122953, A156022, A156023, A156024.

Programs

Python

from itertools import product
def c(w):
    return len(set(w[i:j+1] for i in range(len(w)) if w[i] != "0" for j in range(i,len(w)))) + int("0" in w)
def a(n):
    if n == 1: return 2
    m, argm, cardm = -1, None, 0
    for b in product("01", repeat=n-1):
        v = c("1"+"".join(b))
        if v == m: argm, cardm = int("1"+"".join(b), 2), cardm + 1
        elif v > m: m, argm, cardm = v, int("1"+"".join(b), 2), 1
    return cardm
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Jan 13 2023

Extensions

a(32) onwards from Martin Fuller, Jul 24 2025