A122953 -id:A122953 - cp's OEIS frontend

A292924 a(n) is the least k such that A122953(k) = n.

1, 2, 4, 6, 11, 12, 22, 24, 28, 44, 52, 56, 88, 92, 112, 116, 186, 184, 220, 232, 244, 368, 376, 440, 472, 488, 744, 752, 880, 888, 976, 984, 1504, 1512, 1780, 1776, 1912, 1968, 2008, 3024, 3048, 3552, 3568, 3824, 3952, 4016, 6064, 6096, 7112, 7136, 7648, 7664

Offset: 1

Rémy Sigrist, Mar 09 2018

All positive terms of A112510 belong to this sequence.
The first known odd terms are a(1) = 1, a(5) = 11 and a(77) = 61321.
The sequence is not strictly increasing; for example a(17) = 186 and a(18) = 184.
The binary plot of the first terms has interesting features (see Links section).

			The first occurrence of 6 in A122953 is A122953(12) = 6, hence a(6) = 12.

Rémy Sigrist, Table of n, a(n) for n = 1..288
Rémy Sigrist, Binary plot of the first 288 terms
Rémy Sigrist, C++ program for A292924

Cf. A112510, A122953.

A165416 Irregular array read by rows: The n-th row contains those distinct positive integers that each, when written in binary, occurs as a substring in binary n.

Original entry on oeis.org

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

Offset: 1

Leroy Quet, Sep 17 2009

This is sequence A119709 with the 0's removed.

The n-th row of this sequence contains A122953(n) terms.

			6 in binary is 110. The distinct positive integers that occur as substrings in n when they and n are written in binary are: 1 (1 in binary), 2 (10 in binary), 3 (11 in binary), and 6 (110 in binary). So row 6 is (1,2,3,6).

Reinhard Zumkeller, Rows n = 1..512 of table, flattened

Cf. A119709, A122953.
Cf. A030308.
Cf. A165153 (row products), A225243 (subsequence).

a165416 n k = a165416_tabf !! (n-1) !! (k-1)
a165416_row n = a165416_tabf !! (n-1)
a165416_tabf = map (dropWhile (== 0)) $ tail a119709_tabf
-- Reinhard Zumkeller, Aug 14 2013

Extended by Ray Chandler, Mar 13 2010

A213629 In binary representation: T(n,k) = number of (possibly overlapping) occurrences of k in n, triangle read by rows, 1<=k<=n.

Original entry on oeis.org

1, 1, 1, 2, 0, 1, 1, 1, 0, 1, 2, 1, 0, 0, 1, 2, 1, 1, 0, 0, 1, 3, 0, 2, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 2, 1, 0, 1, 0, 0, 0, 0, 1, 2, 2, 0, 0, 1, 0, 0, 0, 0, 1, 3, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 2, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 3, 1, 1, 0, 1, 1, 0, 0

Offset: 1

Reinhard Zumkeller, Jun 17 2012

The definition is based on the definition of pattern functions in the paper of Allouche and Shallit;
sum of n-th row = A029931(n);
T(n,1) = A000120(n);
T(n,2) = A033264(n) for n > 1;
T(n,3) = A014081(n) for n > 2;
T(n,4) = A056978(n) for n > 3;
T(n,5) = A056979(n) for n > 4;
T(n,6) = A056980(n) for n > 5;
T(n,7) = A014082(n) for n > 6;
T(n,k) = 0 for k with floor(n/2) < k < n;
T(n,n) = 1;
A122953(n) = Sum_{k=1..n} A057427(T(n,k));
A005811(n) = T(n,1) + T(n,2) - T(n,3);
A007302(n) = A000120(n) - sum (A213629(n,A136412(k))).

			The triangle begins:
.   1:                        1
.   2:                      1   1
.   3:                    2   0   1
.   4:                  1   1   0   1
.   5:                2   1   0   0   1
.   6:              2   1   1   0   0   1
.   7:            3   0   2   0   0   0   1
.   8:          1   1   0   1   0   0   0   1
.   9:        2   1   0   1   0   0   0   0   1
.  10:      2   2   0   0   1   0   0   0   0   1
.  11:    3   1   1   0   1   0   0   0   0   0   1
.  12:  2   1   1   1   0   1   0   0   0   0   0   1.

Reinhard Zumkeller, Rows n = 1..150 of triangle, flattened
J.-P. Allouche, J. Shallit, The Ring of k-regular Sequences II, Example 4, p. 12
Index entries for sequences related to binary expansion of n

Cf. A030308, A007088.

import Data.List (inits, tails, isPrefixOf)
a213629 n k = a213629_tabl !! (n-1) !! (k-1)
a213629_row n = a213629_tabl !! (n-1)
a213629_tabl = map f $ tail $ inits $ tail $ map reverse a030308_tabf where
   f xss = map (\xs ->
           sum $ map (fromEnum . (xs `isPrefixOf`)) $ tails $ last xss) xss

t[n_, k_] := (idn = IntegerDigits[n, 2]; idk = IntegerDigits[k, 2]; ln = Length[idn]; lk = Length[idk]; For[cnt = 0; i = 1, i <= ln - lk + 1, i++, If[idn[[i ;; i + lk - 1]] == idk, cnt++]]; cnt); Table[t[n, k], {n, 1, 14}, {k, 1, n}] // Flatten (* Jean-François Alcover, Oct 22 2012 *)

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

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

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

Rick L. Shepherd, Sep 09 2005

Substrings must be contiguous, they are treated as stand-alone binary representations and the reversal of substrings is not permitted.

			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.).

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

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

Cf. A078822, A122953, A156022, A156023, A156024, A156025. Equals A156022(n)+1 for n >= 2. [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):
    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

a(21) to 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

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

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

cp's OEIS Frontend

A292924 a(n) is the least k such that A122953(k) = n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A165416 Irregular array read by rows: The n-th row contains those distinct positive integers that each, when written in binary, occurs as a substring in binary n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Extensions

A213629 In binary representation: T(n,k) = number of (possibly overlapping) occurrences of k in n, triangle read by rows, 1<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

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

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

Views

Author

Keywords

Comments

Examples

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

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