A119709 -id:A119709 - cp's OEIS frontend

A078822 Number of distinct binary numbers contained as substrings in the binary representation of n.

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

Offset: 0

Reinhard Zumkeller, Dec 08 2002

For n>0: 0A070939(n)+1, 0A070939(n). - Reinhard Zumkeller, Mar 07 2008

Row lengths in triangle A119709. - Reinhard Zumkeller, Aug 14 2013

			n=10 -> '1010' contains 5 different binary numbers: '0' (b0bb or bbb0), '1' (1bbb or bb1b), '10' (10bb or bb10), '101' (101b) and '1010' itself, therefore a(10)=5.

Alois P. Heinz, Table of n, a(n) for n = 0..16384 (first 1001 terms from Reinhard Zumkeller)

Cf. A078823, A078826, A078824, A007088, A141297, A144623, A144624.

a078822 = length . a119709_row
import Numeric (showIntAtBase)
-- Reinhard Zumkeller, Aug 13 2013, Sep 14 2011

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

a[n_] := (id = IntegerDigits[n, 2]; nd = Length[id]; Length[ Union[ Flatten[ Table[ id[[j ;; k]], {j, 1, nd}, {k, j, nd}], 1] //. {0, b__} :> {b}]]); Table[ a[n], {n, 0, 85}] (* Jean-François Alcover, Dec 01 2011 *)

a(n) = {if (n==0, 1, vb = binary(n); vf = []; for (i=1, #vb, for (j=1, #vb - i + 1, pvb = vector(j, k, vb[i+k-1]); f = subst(Pol(pvb), x, 2); vf = Set(concat(vf, f)); ); ); #vf); } \\ Michel Marcus, May 08 2016; corrected Jun 13 2022

def a(n): return 1 if n == 0 else len(set(((((2<>i for i in range(n.bit_length()) for l in range(n.bit_length()-i)))
print([a(n) for n in range(64)]) # Michael S. Branicky, Jul 28 2022

For k>0: a(2^k-2) = 2*(k-1)+1, a(2^k-1) = k, a(2^k) = k+2;
for k>1: a(2^k+1) = k+2;
for k>0: a(2^k-1) = A078824(2^k-1), a(2^k) = A078824(2^k).

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

A056744 a(n) is the smallest number which when written in binary contains as substrings the binary expansions of 1..n.

Original entry on oeis.org

1, 2, 6, 12, 44, 44, 92, 184, 1208, 1256, 4792, 4792, 9912, 9912, 19832, 39664, 563952, 576464, 4496112, 4499184, 17996528, 17997488, 143972080, 143972080, 145057520, 145070832, 294967024, 294967024, 589944560, 589944560, 1179889136, 2359778272, 71079255008

Offset: 1

Fred J. Schalekamp, Aug 15 2000

From Davis Smith, May 09 2021: (Start)
For n > 2, a(n) cannot be a power of 2.
If A007088(n) (the binary expansion of n) contains a string of k zeros, then it contains A007088(2^m), where 0 <= m <= k, as a substring. Similarly, if A007088(n) contains a string of k ones, then it contains A007088(2^m - 1), where 1 <= m <= k. Strings of zeros and ones are the most compact way to have powers of 2 and powers of 2 minus 1 (respectively) as substrings in a binary expansion. This means that A007088(a(n)) will contain a string of A000523(n) ones and a string of A000523(n) zeros. The binary expansion of a(2^k - 1) will contain a string of k ones and a string of k - 1 zeros.
Conjecture: a(n) == 0 (mod A053644(n)), i.e., A007088(a(n)) ends with the longest string of zeros. It follows from this that a(2^k) = 2*a(2^k - 1). A conjecture related to this is that a(2^k - 1) = 2*a(2^k - 2) + 2^(k - 1), i.e., A007088(a(2^k - 1)) ends with the longest string of ones followed by the longest string of zeros. Ending with the longest string of ones followed by the longest string of zeros is not true for all A007088(a(n)), as some have a hiccup before starting their string of zeros, e.g., a(10), a(18), a(22), and a(34).
Conjecture: a(2^k + 1) = 2^(k + floor(log_2(a(2^k)))) + a(2^k), i.e., concatenate the binary expansion of 2^(k - 1) to the front of the binary expansion of a(2^k) in order to get the binary expansion of a(2^k + 1).
(End)
All terms belong to A261467. - Rémy Sigrist, May 11 2021
From Jon E. Schoenfield, Jun 03 2021: (Start)
Conjecture: the binary expansion of a(n) contains exactly ceiling(n/2) 1's iff 2^m - 7 <= n <= 2^m + 6 for some integer m >= 3. (See Links.)
Conjecture: for n > 1, the binary expansion of a(n) begins with that of 2^floor(log_2(n-1)) + 1.(End)
From Davis Smith, Jun 05 2021: (Start)
For a proof that a(n) == 2^floor(log_2(n)) (mod 2^(floor(log_2(n)) + 1)), see my second link (not the b-file). This also proves the conjecture from May 09 2021 which states that it is congruent to 0 (mod A053644(n)). A proof for the related conjecture would likely rely on an explanation of values of n such that a(n) is not congruent to (2^floor(log_2(n)) - 1)*2^floor(log_2(n)) (mod 2^(2*floor(log_2(n)))), i.e. the values of n such that A007088(a(n)) does not end with a string of floor(log_2(n)) ones followed immediately by a string of floor(log_2(n)) zeros. A proof for Jon E. Schoenfield's second conjecture on Jun 03 2021 would satisfy my more restricted second conjecture and it may follow necessarily from my proof, assuming that A007088(a(n)) must begin with either A007088(2^floor(log_2(n - 1)) + 1) or A007088(2^floor(log_2(n))). (End)

			a(6)=44 because 101100 (44 in base 2) is the smallest number that contains 1, 10, 11, 100, 101 and 110 (1 through 6 in base 2).
Terms begin as follows (see Links for a longer table):
.
                a(n)
      =========================
   n  decimal      binary
  --  -------  ----------------
   1        1                 1
   2        2                10
   3        6               110
   4       12              1100
   5       44            101100
   6       44            101100
   7       92           1011100
   8      184          10111000
   9     1208       10010111000
  10     1256       10011101000
  11     4792     1001010111000
  12     4792     1001010111000
  13     9912    10011010111000
  14     9912    10011010111000
  15    19832   100110101111000
  16    39664  1001101011110000

Davis Smith, Table of n, a(n) for n = 1..64
David A. Corneth, substrings of a(33) and a(36) listed.
Jon E. Schoenfield, Conjecture on the number of 1's in the binary expansion of a(n).
Jon E. Schoenfield, Lower bounds on the numbers of 1-bits and 0-bits in a(n), a tabular method for deducing the order in which substrings occur in the binary expansion of a(n), and an approach for accounting for duplicate substrings when a(n) has more than ceiling(n/2) 1-bits, illustrated with a proof of the exact value of a(49).
Jon E. Schoenfield, Values for n = 1..64 in binary and decimal.
Davis Smith, Proof that A056744(n) == 2^floor(log_2(n)) (mod 2^(floor(log_2(n))+1)).

Cf. A000523, A035239, A007088, A053644, A053645, A078822, A119709 (binary substrings), A144016, A261467.

A056744_vec(n)={
    my(
        L=List([1]),x=L[#L],Z=n+#L,B=binary(x),
        A=setbinop((y,z)->fromdigits(B[y..z],2),[1..#B])
    );
    while(#Lfromdigits(B[y..z],2),[1..#B]));listput(L,x));Vec(L)
} \\ Davis Smith, May 09 2021

A144016(a(n)) >= n. - Rémy Sigrist, May 11 2021

More terms from Naohiro Nomoto, Jul 20 2001
a(25)-a(31) from Ray Chandler, Nov 06 2008
a(32) from Davis Smith, May 10 2021
a(33) from Jon E. Schoenfield, May 11 2021

A225243 Irregular triangle read by rows, where row n contains the distinct primes that are contained in the binary representation of n as substrings; first row = [1] by convention.

Original entry on oeis.org

1, 2, 3, 2, 2, 5, 2, 3, 3, 7, 2, 2, 2, 5, 2, 3, 5, 11, 2, 3, 2, 3, 5, 13, 2, 3, 7, 3, 7, 2, 2, 17, 2, 2, 3, 19, 2, 5, 2, 5, 2, 3, 5, 11, 2, 3, 5, 7, 11, 23, 2, 3, 2, 3, 2, 3, 5, 13, 2, 3, 5, 11, 13, 2, 3, 7, 2, 3, 5, 7, 13, 29, 2, 3, 7, 3, 7, 31, 2, 2, 2, 17

Offset: 1

Reinhard Zumkeller, Aug 14 2013

Row n = primes in row n of tables A165416 or A119709.

			.   n   T(n,*)              |  in binary
.  ---  --------------------|-------------------------------------------
.   1:  1                   |  00001:  .
.   2:  2                   |  00100:  ___10
.   3:  3                   |  00011:  ___11
.   4:  2                   |  00100:  __10_
.   5:  2  5                |  00101:  ___10 _11__
.   6:  2  3                |  00110:  ___10 __11_
.   7:  3  7                |  00111:  __11_ __111
.   8:  2                   |  01000:  _10__
.   9:  2                   |  01001:  _10__
.  10:  2  5                |  01010:  _10__ _101_
.  11:  2  3  5 11          |  01011:  _10__ ___11 _101_ 01011
.  12:  2  3                |  01100:  ___10 _11__
.  13:  2  3  5 13          |  01101:  __10_ _11__ __101 01101
.  14:  2  3  7             |  01110:  ___10 _11__ _111_
.  15:  3  7                |  01111:  _11__ _111_
.  16:  2                   |  10000:  10___
.  17:  2 17                |  10001:  10___ 10001
.  18:  2                   |  10010:  10___
.  19:  2  3 19             |  10011:  10___ ___11 10011
.  20:  2  5                |  10100:  10___ 101__
.  21:  2  5                |  10101:  10___ 101__
.  22:  2  3  5 11          |  10110:  10___ __11_ 101__ 10110
.  23:  2  3  5  7 11 23    |  10111:  10___ __11_ 101__ __111 1011_ 10111
.  24:  2  3                |  11000:  _10__ 11___
.  25:  2  3                |  11001:  _10__ 11___ .

Reinhard Zumkeller, Rows n = 1..1024 of table, flattened
Michael De Vlieger, Plot of pi(p) such that T(n,k) = p for n = 1..4096.

Cf. A078826 (row lengths), A078832 (left edge), A078833 (right edge), A004676, A007088.

a225243 n k = a225243_tabf !! (n-1) !! (k-1)
a225243_row n = a225243_tabf !! (n-1)
a225243_tabf = [1] : map (filter ((== 1) . a010051')) (tail a165416_tabf)

Array[Union@ Select[FromDigits[#, 2] & /@ Rest@ Subsequences@ IntegerDigits[#, 2], PrimeQ] &, 34] /. {} -> {1} // Flatten (* Michael De Vlieger, Jan 26 2022 *)

from sympy import isprime
from itertools import count, islice
def primess(n):
    b = bin(n)[2:]
    ss = (int(b[i:j], 2) for i in range(len(b)) for j in range(i+2, len(b)+1))
    return sorted(set(k for k in ss if isprime(k)))
def agen():
    yield 1
    for n in count(2):
        yield from primess(n)
print(list(islice(agen(), 82))) # Michael S. Branicky, Jan 26 2022

A301983 Irregular triangle read by rows T(n, k), n >= 1 and 1 <= k <= A301977(n): T(n, k) is the k-th positive number whose binary digits appear in order but not necessarily as consecutive digits in the binary representation of n.

Original entry on oeis.org

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

Offset: 1

Rémy Sigrist, Mar 30 2018

This sequence has similarities with A119709 and A165416; there we consider consecutive digits, here not.

			Triangle begins:
   1:    [1]
   2:    [1, 2]
   3:    [1, 3]
   4:    [1, 2, 4]
   5:    [1, 2, 3, 5]
   6:    [1, 2, 3, 6]
   7:    [1, 3, 7]
   8:    [1, 2, 4, 8]
   9:    [1, 2, 3, 4, 5, 9]
  10:    [1, 2, 3, 4, 5, 6, 10]
  11:    [1, 2, 3, 5, 7, 11]
  12:    [1, 2, 3, 4, 6, 12]
  13:    [1, 2, 3, 5, 6, 7, 13]
  14:    [1, 2, 3, 6, 7, 14]
  15:    [1, 3, 7, 15]
  16:    [1, 2, 4, 8, 16]

Cf. A119709, A165416, A301977 (row length).

b:= proc(n) option remember; `if`(n=0, {0},
      map(x-> [x, 2*x+r][], b(iquo(n, 2, 'r'))))
    end:
T:= n-> sort([(b(n) minus {0})[]])[]:
seq(T(n), n=1..20);  # Alois P. Heinz, Jan 26 2022

T(n,k) = my (b=binary(n), s=Set(1)); for (i=2, #b, s = setunion(s, Set(apply(v -> 2*v+b[i], s)))); return (s[k])

T(n, 1) = 1.
T(n, A301977(n)) = n.
T(2^n, k) = 2^(k-1) for any n > 0 and k = 1..n+1.
T(2^n - 1, k) = 2^k - 1 for any n > 0 and k = 1..n.

A265236 Number of solutions to the equation A x B = C, where A, B and C are nonnegative numbers appearing as (contiguous) substrings of the binary representation of n.

Original entry on oeis.org

1, 1, 8, 3, 13, 12, 18, 5, 19, 17, 18, 20, 31, 26, 28, 7, 26, 23, 23, 26, 31, 22, 32, 28, 47, 40, 38, 34, 49, 40, 38, 9, 34, 30, 29, 31, 31, 31, 38, 34, 47, 39, 28, 34, 53, 40, 46, 38, 66, 55, 54, 48, 59, 46, 46, 48, 75, 62, 58, 52, 67, 58, 48, 11, 43, 38

Offset: 0

Reinhard Zumkeller, Dec 06 2015

nonn

A, B and C are allowed to be zero, in contrast to A265008;
a(A000225(n)) = A265008(A000225(n));
a(A062289(n)) != A265008(A062289(n)).

			.  n | A007088 | A119709     |  a |
. ---+---------+-------------+----+-------------------------------------
.  2 |      10 | [0,1,2]     |  8 = #{(0,0,0), (0,1,0), (0,2,0), (1,0,0),
.    |         |             |        (2,0,0), (1,1,1), (1,2,2), (2,1,2)}
.  3 |      11 | [1,3]       |  3 = #{(1,1,1), (1,3,3), (3,1,3)}
.  4 |     100 | [0,1,2,4]   | 13 = #{(0,0,0), (0,1,0), (0,2,0), (0,4,0),
.    |         |             |         (1,0,0), (2,0,0), (4,0,0), (1,1,1),
.    |         |             |         (1,2,2), (2,1,2), (1,4,4), (2,2,4),
.    |         |             |         (4,1,4)}
.  5 |     101 | [0,1,2,5]   | 12 = #{(0,0,0), (0,1,0), (0,2,0), (0,5,0),
.    |         |             |         (1,0,0), (2,0,0), (5,0,0), (1,1,1),
.    |         |             |         (1,2,2), (2,1,2), (1,5,5), (5,1,5)}
.  6 |     110 | [0,1,2,3,6] | 18 = #{(0,0,0), (0,1,0), (0,2,0), (0,3,0),
.    |         |             |         (0,6,0), (1,0,0), (2,0,0), (3,0,0),
.    |         |             |         (6,0,0), (1,1,1), (1,2,2), (2,1,2),
.    |         |             |         (1,3,3), (3,1,3), (1,6,6), (2,3,6),
.    |         |             |         (3,2,6), (6,1,6)}
.  7 |     111 | [1,3,7]     |≈ 5 = #{(1,1,1), (1,3,3), (3,1,3), (1,7,7),
.    |         |             |         (7,1,7)} .

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

Cf. A007088, A119709, A265008, A265183 (decimal case), A000225, A062289, A043545, A078822.

a265236 n = length [() | let cs = a119709_row n, a <- cs, b <- cs, c <- cs,
                         a * b == c || c == 0 && a * b == 0]

For n > 0: a(n) = A265008(n) + A043545(n) * (2*A078822(n) - 1).

Suggested by N. J. A. Sloane.

A165153 a(n) = the product of all distinct positive (nonzero) integers that, when written in binary, occur as substrings in the binary representation of n.

Original entry on oeis.org

1, 2, 3, 8, 10, 36, 21, 64, 72, 100, 330, 1728, 2340, 3528, 315, 1024, 1088, 1296, 4104, 8000, 2100, 43560, 53130, 331776, 388800, 608400, 694980, 4741632, 6650280, 1587600, 9765, 32768, 33792, 36992, 114240, 46656, 239760, 935712, 1120392

Offset: 1

Leroy Quet, Sep 05 2009

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

Cf. A119709, A078823.

Cf. A165416.

a165153 = product . a165416_row  -- Reinhard Zumkeller, Aug 14 2013

a(n) = product(A165416(n,k): k=1..A078822(n)-1). - Reinhard Zumkeller, Aug 14 2013

More terms from Sean A. Irvine, Nov 12 2009

A165417 a(0) = a(1) = 1. For n >=2, a(n) = sum a(k), where k is over the distinct values of the substrings in binary n, and where 0 <= k < n.

Original entry on oeis.org

1, 1, 2, 1, 4, 4, 5, 2, 8, 8, 8, 9, 14, 14, 12, 4, 16, 16, 16, 17, 20, 16, 23, 20, 36, 36, 36, 37, 42, 42, 28, 8, 32, 32, 32, 33, 32, 36, 39, 36, 48, 48, 32, 42, 64, 60, 57, 44, 88, 88, 88, 89, 96, 88, 97, 96, 128, 128, 128, 130, 116, 116, 64, 16, 64, 64, 64, 65, 64, 68, 71, 68, 72

Offset: 0

Leroy Quet, Sep 17 2009

The distinct nonnegative values of the substrings of binary n is row n of table A119709.

a(2^n) = 2^n, for all n.

			9 in binary is 1001. The distinct nonnegative integers that occur as substrings in binary 9 are 0, 1, 2 (10 in binary), 4 (100 in binary), and 9 (1001 in binary). So a(9) = a(0)+a(1)+a(2)+a(4) = 1 + 1 + 2 + 4 = 8.

Cf. A119709, A165418.

Extended by Ray Chandler, Mar 13 2010

A165419 Each a(n) is chosen so that n = sum a(k), for all n >= 0, where k is over the distinct nonnegative values of the substrings in binary n.

Original entry on oeis.org

0, 1, 1, 2, 2, 3, 2, 4, 4, 5, 5, 4, 4, 4, 4, 8, 8, 9, 9, 8, 8, 11, 9, 8, 8, 8, 8, 10, 8, 8, 8, 16, 16, 17, 17, 16, 18, 16, 17, 16, 16, 16, 21, 16, 16, 19, 17, 16, 16, 16, 16, 18, 16, 16, 18, 16, 16, 16, 16, 16, 16, 16, 16, 32, 32, 33, 33, 32, 34, 32, 33, 32, 32, 37, 32, 32, 34, 32, 33

Offset: 0

Leroy Quet, Sep 17 2009

We could have instead taken k over the distinct positive values of the substrings in binary n, and get the same sequence, since a(0)=0.

The distinct nonnegative values of the substrings of binary n is row n of table A119709. The distinct positive values of the substrings of binary n is row n of table A165416.

			9 in binary is 1001. The distinct nonnegative integers that occur as substrings in binary 9 are 0, 1, 2 (10 in binary), 4 (100 in binary), and 9 (1001 in binary). And 9 = a(0) + a(1) + a(2) + a(4) + a(9) = 0 + 1 + 1 + 2 + 5.

Cf. A119709, A165416.

Extended by Ray Chandler, Mar 13 2010

cp's OEIS Frontend

A078822 Number of distinct binary numbers contained as substrings in the binary representation of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

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

A056744 a(n) is the smallest number which when written in binary contains as substrings the binary expansions of 1..n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A225243 Irregular triangle read by rows, where row n contains the distinct primes that are contained in the binary representation of n as substrings; first row = [1] by convention.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Python

A301983 Irregular triangle read by rows T(n, k), n >= 1 and 1 <= k <= A301977(n): T(n, k) is the k-th positive number whose binary digits appear in order but not necessarily as consecutive digits in the binary representation of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

A265236 Number of solutions to the equation A x B = C, where A, B and C are nonnegative numbers appearing as (contiguous) substrings of the binary representation of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Formula

Extensions

A165153 a(n) = the product of all distinct positive (nonzero) integers that, when written in binary, occur as substrings in the binary representation of n.

Views

Author

Keywords

Links