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

0, 2, 6, 12, 28, 56, 116, 244, 488, 984, 2008, 4016, 8048, 16240, 32480, 64968, 129992, 261064, 522128, 1044264, 2088552, 4177512, 8371816, 16743632, 33487312, 66976208, 134085072, 268170144, 536340304, 1072680624, 2145361584, 4290748080, 8585715376, 17171430752

Offset: 1

Author

Rick L. Shepherd, Sep 09 2005

Keywords

• base
• nonn

Comments

See A112509 for a full explanation and example.

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. A112509 (corresponding maximum), A112511 (greatest n-bit number for which this maximum occurs).

A078822, A122953, A156022, A156023, A156024, A156025. [From Joseph Myers, Feb 01 2009]

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 0
    m = -1
    for b in product("01", repeat=n-1):
        v = c("1"+"".join(b))
        if v > m:
            m, argm = v, int("1"+"".join(b), 2)
    return argm
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Jan 13 2023

Extensions

a(21)-a(31) from Joseph Myers, Feb 01 2009

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