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
A112510
Least n-bit number whose binary representation's substrings represent the maximal number (A112509(n)) of distinct integers.
Original entry on oeis.org
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
Cf.
A112509 (corresponding maximum),
A112511 (greatest n-bit number for which this maximum occurs).
-
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
A112509
Maximum number of numbers represented by substrings of an n-bit number's binary representation.
Original entry on oeis.org
1, 3, 5, 7, 10, 13, 17, 22, 27, 33, 40, 47, 55, 64, 73, 83, 94, 106, 118, 131, 145, 160, 176, 192, 209, 227, 246, 265, 285, 306, 328, 351, 375, 399, 424, 450, 477, 504, 532, 561, 591, 622, 654, 687, 720, 754, 789, 825, 862, 899, 937, 977, 1017, 1058, 1100, 1143
Offset: 1
To see why a(4)=7 (and A112510(4)=12 and A112511(4)=14), consider all numbers whose binary representations require exactly 4 bits: 1000, 1001, 1010, 1011, 1100, 1101, 1110 and 1111. For each of these binary representations in turn, we find the nonnegative integers represented by all of its contiguous substrings. We count these distinct integer values (putting the count in {}s):
1000: any 0, either 00, or 000 -> 0, 1 -> 1, 10 -> 2, 100 -> 4, 1000 -> 8 {5};
1001: either 0, or 00 -> 0, either 1, 01, or 001 -> 1, 10 -> 2, 100 -> 4, 1001 -> 9 {5};
(For brevity, binary substrings are shown below only if they produce values not shown yet.)
1010: 0, 1, 2, 101 -> 5, 1010 -> 10 {5};
1011: 0, 1, 2, 11 -> 3, 5, 1011 -> 11 {6};
1100: 0, 1, 2, 3, 4, 110 -> 6, 1100 -> 12 {7};
1101: 0, 1, 2, 3, 5, 6, 1101 -> 13 {7};
1110: 0, 1, 2, 3, 6, 111 -> 7, 1110 -> 14 {7};
1111: 1, 3, 7, 1111 -> 15 {4}.
Because the maximum number of distinct integer values {in brackets} is 7, a(4)=7. The smallest 4-bit number for which 7 distinct values are found is 12, so A112510(4)=12. The largest 4-bit number for which 7 are found is 14, so A112511(4)=14. (For n=4 the count is a(n)=7 also for all values (only one, 13, here) between A112510(n) and A112511(n). This is not the case in general.).
Cf.
A112510 (least n-bit number for which this maximum occurs),
A112511 (greatest n-bit number for which this maximum occurs).
-
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):
return max(c("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
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
Cf.
A112509 (corresponding maximum),
A112510 (least n-bit number for which this maximum occurs).
-
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
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
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
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.
-
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
Showing 1-6 of 6 results.
Comments