A165416 -id:A165416 - cp's OEIS frontend

A122953 a(n) = number of distinct positive integers represented in binary which are substrings of binary expansion of n.

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

Offset: 1

Leroy Quet, Oct 25 2006

a(n) = A078822(n) if n is of the form 2^k - 1. Otherwise, a(n) = A078822(n) - 1.
First occurrence of k: 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, ... (See A292924 for the corresponding sequence. - Rémy Sigrist, Mar 09 2018)
Last occurrence of k: 2^k - 1.
a(n) = Sum_{k=1..n} A057427(A213629(n,k)). - Reinhard Zumkeller, Jun 17 2012
Length of n-th row in triangle A165416. - Reinhard Zumkeller, Jul 17 2015

			Binary 1 = 1, binary 2 = 10, binary 4 = 100 and binary 9 = 1001 are all substrings of binary 9 = 1001. So a(9) = 4.

Jeremy Gardiner, Table of n, a(n) for n = 1..2000

Cf. A078822, A292924.

Cf. A057427, A213629, A165416.

a122953 = length . a165416_row
-- Reinhard Zumkeller, Jul 17 2015, Jan 22 2012

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

f[n_] := Length@ Select[ Union[ FromDigits /@ Flatten[ Table[ Partition[ IntegerDigits[n, 2], i, 1], {i, Floor[ Log[2, n] + 1]}], 1]], # > 0 &]; Array[f, 90]

a(n) = my (v=0, s=0, x=Set()); while (n, my (r=n); while (r, if (r < 100 000, if (bittest(s,r), break, s+=2^r), if (setsearch(x,r), break, x=setunion(x, Set(r)))); v++; r \= 2); n -= 2^(#binary(n)-1)); v \\ Rémy Sigrist, Mar 08 2018

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

More terms from Robert G. Wilson v, Nov 01 2006

Keyword base added by Rémy Sigrist, Mar 08 2018

A078826 Number of distinct primes contained as binary substrings in binary representation of n.

Original entry on oeis.org

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

Offset: 0

Reinhard Zumkeller, Dec 08 2002

A143792(n) <= a(n) for n > 0. - Reinhard Zumkeller, Sep 08 2008

For n > 1: number of primes in n-th row of A165416, lengths in n-th row of A225243. - Reinhard Zumkeller, Jul 17 2015, Aug 14 2013

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

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

Cf. A004676, A035232, A078827, A078822, A007088, A001221.

Cf. A143792, A165416, A225243.

a078826 n | n <= 1 = 0
          | otherwise = length $ a225243_row n
-- Reinhard Zumkeller, Aug 14 2013

a[n_] := (bits = IntegerDigits[n, 2]; lg = Length[bits]; Reap[Do[If[PrimeQ[p = FromDigits[bits[[i ;; j]], 2]], Sow[p]], {i, 1, lg-1}, {j, i+1, lg}]][[2, 1]] // Union // Length); a[0] = a[1] = 0; Table[a[n], {n, 0, 104}] (* Jean-François Alcover, May 23 2013 *)

A119709 Table where n-th row (of A078822(n) terms) contains the distinct nonnegative integers which, when written in binary, are substrings of n written in binary.

Original entry on oeis.org

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

Offset: 0

Leroy Quet, Jun 10 2006

			12 in binary is 1100. Within this binary representation there is 0 (occurring twice), 1 (occurring twice), 10 (= 2 in decimal), 11 (= 3 in decimal), 100 (= 4 in decimal), 110 (= 6 in decimal) and 1100 (= 12 in decimal).
So row 12 = (0,1,2,3,4,6,12).

Reinhard Zumkeller, Rows n = 0..511 of table, flattened

Cf. A078822.

Cf. A030308, A165416.

import Data.List (isInfixOf)
a119709 n k = a119709_tabf !! n !! k
a119709_row n = map (foldr (\d v -> v * 2 + toInteger d) 0) $
   filter (`isInfixOf` (a030308_row n)) $ take (n + 1) a030308_tabf
a119709_tabf = map a119709_row [0..]
-- Reinhard Zumkeller, Aug 14 2013

Extended by Ray Chandler, Mar 13 2010

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.

A165418 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 1 <= k < n.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 2, 4, 4, 4, 5, 8, 8, 8, 4, 8, 8, 8, 9, 10, 8, 13, 12, 20, 20, 20, 21, 26, 26, 20, 8, 16, 16, 16, 17, 16, 18, 21, 20, 24, 24, 16, 22, 36, 34, 35, 28, 48, 48, 48, 49, 52, 48, 55, 56, 76, 76, 76, 78, 76, 76, 48, 16, 32, 32, 32, 33, 32, 34, 37, 36, 36, 32, 40, 42, 50, 52

Offset: 1

Leroy Quet, Sep 17 2009

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

a(2^n) = 2^(n-1), for all n >=1.

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

Rémy Sigrist, Table of n, a(n) for n = 1..8192
Rémy Sigrist, PARI program for A165418

A165416, A165417

Fold[Function[{a, n}, Append[a, With[{w = IntegerDigits[n, 2]}, Total@ Part[a, Select[Union@ Map[FromDigits[#, 2] &, Apply[Join, Array[Partition[w, #, 1] &, Length@ w]]], Nor[# == 0, # == n] &]]]]], {1}, Range[2, 77]] (* Michael De Vlieger, Dec 31 2017 *)

PARI
```
See Links section.
```

More terms from Sean A. Irvine, Nov 19 2009

A265008 Number of positive solutions to the equation A x B = C, where A, B and C are made from (contiguous) substrings of the binary representation of n.

Original entry on oeis.org

1, 3, 3, 6, 5, 9, 5, 10, 8, 9, 9, 18, 13, 15, 7, 15, 12, 12, 13, 18, 11, 17, 13, 30, 23, 21, 17, 30, 21, 21, 9, 21, 17, 16, 16, 18, 16, 21, 17, 30, 22, 15, 17, 32, 21, 25, 19, 45, 34, 33, 27, 36, 25, 25, 25, 50, 37, 33, 27, 42, 33, 27, 11, 28, 23, 21, 21, 22, 20, 24, 20, 30, 20, 24, 23, 33, 27, 29, 21, 45, 34, 30, 29, 30, 17, 29, 25, 52, 40, 33, 25, 46, 31

Offset: 1

Marko Riedel, Nov 29 2015

Here all three of A, B and C are positive; if A and B are distinct then the solutions A X B = C and B X A = C are regarded as distinct; while A x A is counted once. A substring may be used any number of times.

			When n=6 = (110)_2 we get the substrings 1=(1)_2, 2=(10)_2, 3=(11)_2 and 6=(110)_2 with the products 1*1=1, 1*2=2, 2*1=2, 1*3=3, 3*1=3, 1*6=6, 6*1=6, 2*3=6, 3*2=6 for a total of 9. When n=8 = (1000)_2 we get the substrings 1=(1)_2, 2=(10)_2, 4=(100)_2 and 8=(1000)_2 with the products 1*1=1, 1*2=2, 2*1=2, 1*4=4, 4*1=4, 1*8=1, 8*1=1, 2*2=4, 2*4=8, 4*2=8 for a total of 10.

Robert Israel, Table of n, a(n) for n = 1..10000
Marko Riedel, Maple code for the number of solutions to A x B = C using binary substrings of n.

Allowing A,B,C to be zero gives A265236.
See A265182, A265183 for decimal analogs.
Cf. A165416.

a265008 n = length [() | let cs = a165416_row n, c <- cs,
            let as = takeWhile (<= c) cs, a <- as, b <- as, a * b == c]
-- Reinhard Zumkeller, Dec 05 2015

F:= proc(n) local L,ss;
  L:= convert(n,base,2);
  ss:= {seq(seq(add(2^(i-j)*L[i],i=j..k), j=1..k),k=1..nops(L))} minus {0};
  numboccur(true,[seq(seq(member(a*b,ss),a=ss),b=ss)]);
end proc:
seq(F(n), n=1..100); # Robert Israel, Nov 30 2015

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

A356149 Irregular table T(n, k), n > 0, k = 1..A356148(n), read by rows; the n-th row contains, in ascending order, the distinct positive integers whose binary expansion appears as a substring in the binary expansion of n or its complement.

Original entry on oeis.org

1, 1, 2, 1, 3, 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 6, 1, 3, 7, 1, 2, 3, 4, 7, 8, 1, 2, 3, 4, 6, 9, 1, 2, 5, 10, 1, 2, 3, 4, 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, 3, 4, 7, 8, 15, 16, 1, 2, 3, 4, 6, 7, 8, 14, 17, 1, 2, 3, 4, 5, 6, 9, 13, 18

Offset: 1

Rémy Sigrist, Jul 28 2022

Leading 0's in binary expansions are ignored.

The n-th contains the n-th row of A165416.

			Table T(n, k) begins:
    1;
    1, 2;
    1, 3;
    1, 2, 3, 4;
    1, 2, 5;
    1, 2, 3, 6;
    1, 3, 7;
    1, 2, 3, 4, 7, 8;
    1, 2, 3, 4, 6, 9;
    1, 2, 5, 10;
    1, 2, 3, 4, 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, 3, 4, 7, 8, 15, 16;
    ...

Rémy Sigrist, Table of n, a(n) for n = 1..26775
Index entries for sequences related to binary expansion of n

Cf. A165416, A356148, A356150.

row(n) = { my (b=binary(n)); setbinop((i,j) -> my (s=fromdigits(b[i..j],2)); if (b[i], s, 2^(j-i+1)-1-s), [1..#b]) }

def row(n):
    N = n.bit_length()
    c, s = ((1<> i)
            s.add((mask&c) >> i)
    return sorted(s - {0})
print([t for r in range(19) for t in row(r)]) # Michael S. Branicky, Jul 28 2022

T(n, 1) = 1.

T(n, A356148(n)) = n.

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

A122953 a(n) = number of distinct positive integers represented in binary which are substrings of binary expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Extensions

A078826 Number of distinct primes contained as binary substrings in binary representation of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

A119709 Table where n-th row (of A078822(n) terms) contains the distinct nonnegative integers which, when written in binary, are substrings of n written in binary.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

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

A165418 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 1 <= k < n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A265008 Number of positive solutions to the equation A x B = C, where A, B and C are made from (contiguous) substrings of the binary representation of n.

Views

Author

Keywords

Comments

Examples

Links