A078822 -id:A078822 - cp's OEIS frontend

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

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

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

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

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

A091460 Greatest size of an arithmetic progression contained as substrings in binary representation of n.

Original entry on oeis.org

1, 1, 3, 2, 3, 3, 4, 2, 3, 3, 3, 4, 5, 4, 4, 2, 3, 3, 3, 5, 3, 3, 4, 4, 5, 5, 4, 4, 5, 4, 4, 2, 3, 3, 3, 5, 3, 3, 5, 5, 3, 3, 3, 4, 7, 4, 4, 4, 5, 5, 5, 5, 7, 4, 4, 4, 5, 5, 4, 4, 5, 4, 4, 2, 3, 3, 3, 5, 3, 3, 5, 5, 3, 3, 3, 6, 5, 7, 5, 5, 3, 3, 3, 6, 3, 3, 4, 4, 7, 7, 4, 4, 8, 4, 4, 4, 5, 5, 5, 5, 5, 7

Offset: 0

Reinhard Zumkeller, Jan 12 2004

a(n) <= A078822(n);

a(A091461(n))=n and a(m)<>n for m < A091461(n).

			n=28->'11100', {0+k*1: 0<=k<a(28)=5}: bbbb0 => bb1bb => bb10b => b11bb => bb100;
n=29->'11101', {1+k*2: 0<=k<a(29)=4}: bbbb1 => b11bb => bb101 => 111bb.

Cf. A078822, A007088.

A093640 Number of divisors of n whose binary representation is contained in that of n.

Original entry on oeis.org

1, 2, 2, 3, 2, 4, 2, 4, 2, 4, 2, 6, 2, 4, 3, 5, 2, 4, 2, 6, 2, 4, 2, 8, 2, 4, 3, 6, 2, 6, 2, 6, 2, 4, 2, 6, 2, 4, 3, 8, 2, 4, 2, 6, 4, 4, 2, 10, 2, 4, 3, 6, 2, 6, 4, 8, 3, 4, 2, 9, 2, 4, 4, 7, 2, 4, 2, 6, 2, 4, 2, 8, 2, 4, 4, 6, 2, 6, 2, 10, 2, 4, 2, 6, 3, 4, 3, 8, 2, 8, 3, 6, 3, 4, 3, 12, 2, 4, 3, 6, 2

Offset: 1

Reinhard Zumkeller, Apr 07 2004

			n = 18: divisors of 18: 1 = '1', 2 = '10', 3 = '11', 6 = '110', 9 = '1001' and 18 = '10010': four of them are binary substrings of '10010', therefore a(18) = 4.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Index entries for sequences related to binary expansion of n.

Cf. A000005, A078822, A007088, A093641, A093642.

import Data.List (isInfixOf)
a093640 n  = length [d | d <- [1..n], mod n d == 0,
                         show (a007088 d) `isInfixOf` show (a007088 n)]
-- Reinhard Zumkeller, Jan 22 2012

a[n_] := DivisorSum[n, 1 &, StringContainsQ @@ IntegerString[{n, #}, 2] &]; Array[a, 100] (* Amiram Eldar, Jul 16 2022 *)

from sympy import divisors
def a(n):
    s = bin(n)[2:]
    return sum(1 for d in divisors(n, generator=True) if bin(d)[2:] in s)
print([a(n) for n in range(1, 102)]) # Michael S. Branicky, Jul 11 2022

a(n) > 1 for n>1.
a(p) = 2 for primes p.
a(A093641(n)) = A000005(A093641(n)).
a(A093642(n)) < A000005(A093642(n)).

A141297 a(n) = number of distinct (nonempty) substrings in the binary representation of n.

Original entry on oeis.org

1, 3, 2, 5, 5, 5, 3, 7, 8, 7, 8, 8, 8, 7, 4, 9, 11, 11, 12, 11, 9, 11, 11, 11, 12, 11, 11, 11, 11, 9, 5, 11, 14, 15, 16, 14, 15, 16, 16, 15, 15, 11, 14, 16, 14, 15, 14, 14, 16, 16, 16, 16, 14, 14, 15, 15, 16, 15, 15, 14, 14, 11, 6, 13, 17, 19, 20, 19, 20, 21, 21, 19, 17, 19, 21, 20, 21

Offset: 1

Leroy Quet, Jun 24 2008

Substrings may start with a 0.
The terms were calculated by R. J. Mathar.
Also: "complexité par facteurs" of n written in base 2. [Alexandre Wajnberg, Aug 22 2011]

			The distinct substrings in binary representation (1010) of decimal 10 are 0,1,10,01,101,010,1010. So a(10) = 7.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Jean-Paul Delahaye, Le défi des faibles complexités, Pour la Science, 405 (2011), p. 82-87.

Cf. A078822, A141298, A141299, A141300, A122953.

a:= n-> (s-> nops({seq(seq(s[i..j], i=1..j),
    j=1..length(s))}))(""||(convert(n, binary))):
seq(a(n), n=1..84);  # Alois P. Heinz, Jan 20 2021

Table[With[{d = IntegerDigits[n, 2]}, Length@ Union@ Apply[Join, Table[Partition[d, k, 1], {k, Length@ d}]]], {n, 77}] (* Michael De Vlieger, Sep 22 2017 *)

def a(n):
  b = bin(n)[2:]
  m = len(b)
  return len(set(b[i:j] for i in range(m) for j in range(i+1, m+1)))
print([a(n) for n in range(1, 78)]) # Michael S. Branicky, Jan 20 2021

a(2^k - 1) = k - 1 for any k >= 0. - Rémy Sigrist, Jan 20 2021

A078833 Greatest prime contained as binary substring in binary representation of n>1, a(1)=1.

Original entry on oeis.org

1, 2, 3, 2, 5, 3, 7, 2, 2, 5, 11, 3, 13, 7, 7, 2, 17, 2, 19, 5, 5, 11, 23, 3, 3, 13, 13, 7, 29, 7, 31, 2, 2, 17, 17, 2, 37, 19, 19, 5, 41, 5, 43, 11, 13, 23, 47, 3, 17, 3, 19, 13, 53, 13, 23, 7, 7, 29, 59, 7, 61, 31, 31, 2, 2, 2, 67, 17, 17, 17, 71, 2, 73, 37, 37, 19, 19, 19, 79, 5, 17

Offset: 1

Reinhard Zumkeller, Dec 08 2002

a(n) = A039634(n) for n<=44, but a(45) = 13 <> 11 = A039634(45);
for n>1: a(n) = n iff n is prime.
a(n) = A225243(n, A078826(n)). - Reinhard Zumkeller, Aug 14 2013

			n=12 -> '1100' contains 2 binary substrings which are primes: '11' (11bb) and '10' (b11b); 3='11' is the greater one, therefore a(12)=3.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A078832, A078826, A078822, A007088, A006530.

a078833 = last . a225243_row  -- Reinhard Zumkeller, Aug 14 2013

A093642 Numbers not containing all divisors in their binary representation.

Original entry on oeis.org

9, 15, 18, 21, 25, 27, 30, 33, 35, 36, 39, 42, 45, 49, 50, 51, 54, 57, 60, 63, 65, 66, 69, 70, 72, 75, 77, 78, 81, 84, 85, 87, 90, 91, 93, 95, 98, 99, 100, 102, 105, 108, 110, 111, 114, 115, 117, 119, 120, 121, 123, 125, 126, 129, 130, 132, 133, 135, 138, 140, 141

Offset: 1

Reinhard Zumkeller, Apr 07 2004

			55 is not a member, as the binary representations of 5 ("101") and 11 ("1011") both appear in the binary representation of 55 ("110111").

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Complement of A123345.
Subsequence of A105441. - Reinhard Zumkeller, Apr 09 2005
Cf. A000005, A078822, A007088, A027750, A093640.

import Data.List (unfoldr, isInfixOf)
a093642 n = a093642_list !! (n-1)
a093642_list = filter
  (\x -> not $ all (`isInfixOf` b x) $ map b $ a027750_row x) [1..] where
  b = unfoldr (\x -> if x == 0 then Nothing else Just $ swap $ divMod x 2)
-- Reinhard Zumkeller, Oct 27 2012

q[n_] := !AllTrue[Divisors[n], StringContainsQ[IntegerString[n, 2], IntegerString[#, 2]] &]; Select[Range[150], q] (* Amiram Eldar, Jun 05 2022 *)

from sympy import divisors
def ok(n):
    b = bin(n)[2:]
    return not all(bin(d)[2:] in b for d in divisors(n, generator=True))
print([k for k in range(119) if ok(k)]) # Michael S. Branicky, Jun 05 2022

A093640(a(n)) < A000005(a(n)).

A078827 Number of primes contained as binary substrings in binary representation of n, counted with repetitions.

Original entry on oeis.org

0, 0, 1, 1, 1, 2, 2, 3, 1, 1, 3, 4, 2, 4, 4, 5, 1, 2, 2, 3, 3, 4, 5, 7, 2, 2, 5, 6, 4, 7, 6, 8, 1, 1, 3, 3, 2, 4, 4, 5, 3, 4, 5, 7, 5, 7, 8, 10, 2, 3, 3, 4, 5, 7, 7, 9, 4, 4, 8, 10, 6, 10, 9, 11, 1, 1, 2, 3, 3, 4, 4, 6, 2, 3, 5, 6, 4, 6, 6, 8, 3, 4, 5, 7, 5, 6, 8, 10, 5, 6, 8, 9, 8, 11, 11, 13, 2, 3, 4, 4, 3

Offset: 0

Reinhard Zumkeller, Dec 08 2002

			n=7 -> '111' contains 3 binary substrings which are primes: '11' (11b), '11' (b11) and '111' itself, therefore a(7)=2.

Cf. A078826, A078822, A007088, A001222, A078828.

cp's OEIS Frontend

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A156024 a(n) = n*(n+1)/2 - A156022(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

A091460 Greatest size of an arithmetic progression contained as substrings in binary representation of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A093640 Number of divisors of n whose binary representation is contained in that of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Python

Formula

A141297 a(n) = number of distinct (nonempty) substrings in the binary representation of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A078833 Greatest prime contained as binary substring in binary representation of n>1, a(1)=1.

Views

Author

Keywords

Comments

Examples

Links