OFFSET
1,2
COMMENTS
Substrings must be contiguous, they are treated as stand-alone binary representations and the reversal of substrings is not permitted.
From Benjamin Clare, Apr 13 2026: (Start)
Best known values for 81 <= n <= 200 have been computed using a combination of structured search and independent probabilistic methods (unconstrained and constrained Metropolis Hastings MCMC). The methods recover the previously known values in the known range and agree across multiple runs in the extended range. The resulting values also continue structural patterns observed in the known terms. These values should be regarded as best known values supported by strong computational evidence rather than proven exact values, and are provided separately as an auxiliary data file. (End)
LINKS
Martin Fuller, Table of n, a(n) for n = 1..80
2008/9 British Mathematical Olympiad Round 2, Problem 4, Jan 29 2009.
Benjamin Clare, Full computational study with code, data, and paper
Benjamin Clare, Best known values
FORMULA
a(n) = A156022(n)+1 for n >= 2. - Joseph Myers, Feb 01 2009
EXAMPLE
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.).
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):
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
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Rick L. Shepherd, Sep 09 2005
EXTENSIONS
a(21)-a(31) from Joseph Myers, Feb 01 2009
a(32) onward from Martin Fuller, Jul 24 2025
STATUS
approved
