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

Offset

1,1

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.

Links

Table of n, a(n) for n=1..31.

2008/9 British Mathematical Olympiad Round 2, Problem 4, Jan 29 2009.

Example

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.

Prog

(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

Crossrefs

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

Sequence in context: A205115 A334369 A093623 * A035556 A296086 A122044

Adjacent sequences: A156022 A156023 A156024 * A156026 A156027 A156028

Keyword

nonn,base,more

Author

Joseph Myers, Feb 01 2009

Status

approved