A112509 -id:A112509 - cp's OEIS frontend

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

Rick L. Shepherd, Sep 09 2005

See A112509 for a full explanation and example.

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

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]

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

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

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

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

Original entry on oeis.org

1, 2, 6, 14, 29, 61, 123, 244, 500, 1004, 2009, 4057, 8121, 16243, 32627, 65267, 130535, 261066, 523210, 1046474, 2092954, 4185909, 8371816, 16760424, 33521256, 67042536, 134085073, 268302801, 536607185, 1073214417, 2146428840, 4292857688, 8585715377, 17175649969

Offset: 1

Rick L. Shepherd, Sep 09 2005

See A112509 for a full explanation and example.

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

Cf. A112509 (corresponding maximum), A112510 (least n-bit number for which this maximum occurs).

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

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):
    m, argm = -1, None
    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

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

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

A156023 a(n) = n*(n+1)/2 - A112509(n).

Original entry on oeis.org

0, 0, 1, 3, 5, 8, 11, 14, 18, 22, 26, 31, 36, 41, 47, 53, 59, 65, 72, 79, 86, 93, 100, 108, 116, 124, 132, 141, 150, 159, 168, 177, 186, 196, 206, 216, 226, 237, 248, 259, 270, 281, 292, 303, 315, 327, 339, 351, 363, 376, 389, 401, 414, 427, 440, 453, 467, 481

Offset: 1

Joseph Myers, Feb 01 2009

n(n+1)/2 is the total number of nonempty substrings of an n-bit binary number; A112509 is the maximum number of substrings representing distinct integers.

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

Cf. A000217, A078822, A112509, A112510, A112511, A122953, A156022, A156024, A156025. Equals A156024(n)-1 for n >= 2.

c_1 + o(1) <= a(n)/n^1.5 <= c_2 + o(1) for some positive constants c_1 and c_2; it seems likely a(n)/n^1.5 tends to some positive constant limit.

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

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

Original entry on oeis.org

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

Joseph Myers, Feb 01 2009

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.

			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.

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

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

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

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

A156022 Maximum number of positive numbers represented by substrings of an n-bit number's binary representation.

Original entry on oeis.org

1, 2, 4, 6, 9, 12, 16, 21, 26, 32, 39, 46, 54, 63, 72, 82, 93, 105, 117, 130, 144, 159, 175, 191, 208, 226, 245, 264, 284, 305, 327, 350, 374, 398, 423, 449, 476, 503, 531, 560, 590, 621, 653, 686, 719, 753, 788, 824, 861, 898, 936, 976, 1016, 1057, 1099, 1142

Offset: 1

Joseph Myers, Feb 01 2009

Equivalently, maximum number of distinct substrings starting with a "1" digit.

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

Cf. A078822, A112509, A112510, A112511, A122953, A156023, A156024, A156025.

Equals A112509(n)-1 for n >= 2.

from itertools import product
def s(w):
    return set(w[i:j+1] for i in range(len(w)) if w[i] != "0" for j in range(i, len(w)))
def a(n):
    return max(len(s("1"+"".join(b))) for b in product("01", repeat=n-1))
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Jan 13 2023

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

A156024 a(n) = n*(n+1)/2 - A156022(n).

Original entry on oeis.org

0, 1, 2, 4, 6, 9, 12, 15, 19, 23, 27, 32, 37, 42, 48, 54, 60, 66, 73, 80, 87, 94, 101, 109, 117, 125, 133, 142, 151, 160, 169, 178, 187, 197, 207, 217, 227, 238, 249, 260, 271, 282, 293, 304, 316, 328, 340, 352, 364, 377, 390, 402, 415, 428, 441, 454, 468, 482

Offset: 1

Joseph Myers, Feb 01 2009

n(n+1)/2 is the total number of nonempty substrings of an n-bit binary number; A156022 is the maximum number of substrings representing distinct positive integers.

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

Cf. A000217, A078822, A112509, A112510, A112511, A122953, A156022, A156023, A156025.

Equals A156023(n)+1 for n >= 2.

c_1 + o(1) <= a(n)/n^1.5 <= c_2 + o(1) for some positive constants c_1 and c_2; it seems likely a(n)/n^1.5 tends to some positive constant limit.

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Extensions

A156023 a(n) = n*(n+1)/2 - A112509(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Extensions

A156022 Maximum number of positive numbers represented by substrings of an n-bit number's binary representation.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Extensions

A156024 a(n) = n*(n+1)/2 - A156022(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions