A078822 -id:A078822 - cp's OEIS frontend

A093641 Numbers of form 2^i * prime(j), i>=0, j>0, together with 1.

1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 16, 17, 19, 20, 22, 23, 24, 26, 28, 29, 31, 32, 34, 37, 38, 40, 41, 43, 44, 46, 47, 48, 52, 53, 56, 58, 59, 61, 62, 64, 67, 68, 71, 73, 74, 76, 79, 80, 82, 83, 86, 88, 89, 92, 94, 96, 97, 101, 103, 104, 106, 107, 109, 112

Offset: 1

Reinhard Zumkeller, Apr 07 2004

a(n) is either 1, prime, or of form 2a(m), m

1 and Heinz numbers of hook integer partitions. The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k). A hook is a partition of the form (n,1,1,...,1). - Gus Wiseman, Sep 15 2018

Numbers whose odd part is noncomposite. - Peter Munn, Aug 06 2020

			55 is not a member, as 5*11 is not of the form 2^i * prime.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

A093640(a(n)) = A000005(a(n)); A000040 and A000079 are subsequences.
A105440 is a subsequence, see also A105442. - Reinhard Zumkeller, Apr 09 2005
Cf. A078822, A007088.
Complement of A105441; A001221(a(n))<=2; A005087(a(n))<=1; A087436(a(n))<=1.
See also A105442.
Union of A038550 and A000079, see also A008578.
Cf. A082733, A153452, A296188, A296561, A300121, A304438, A305940, A317554.
Cf. A000265 (odd part), A008578 (noncomposite).

a093641 n = a093641_list !! (n-1)
a093641_list = filter ((<= 2) . a001227) [1..]
-- Reinhard Zumkeller, May 01 2012

hookQ[n_]:=MatchQ[DeleteCases[FactorInteger[n],{2,}],{}|{{,1}}];
Select[Range[100],hookQ] (* Gus Wiseman, Sep 15 2018 *)

upTo(lim)=my(v=List([1])); for(e=0, log(lim)\log(2), forprime(p=2, lim>>e, listput(v,p<Charles R Greathouse IV, Aug 21 2011

isok(m) = my(k=m/2^valuation(m,2)); (k == 1) || isprime(k); \\ Michel Marcus, Mar 16 2023

from sympy import primepi
def A093641(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return n-1+x-sum(primepi(x>>i) for i in range(x.bit_length()))
    return bisection(f,n,n) # Chai Wah Wu, Feb 02 2025

A001227(a(n)) <= 2. - Reinhard Zumkeller, May 01 2012

Number A(x) of a(n) not exceeding x equals 1 + pi(x) + pi(x/2) + pi(x/4) + ..., where pi(x) is the number of primes <= x. If x goes to infinity, A(x)~2*x/log(x) and a(n)~n*log(n)/2 (n-->infinity). - Vladimir Shevelev, Feb 06 2014

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

Original entry on oeis.org

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

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

A078823 Sum of distinct binary numbers contained as substrings in binary representation of n.

Original entry on oeis.org

0, 1, 3, 4, 7, 8, 12, 11, 15, 16, 18, 22, 28, 30, 33, 26, 31, 32, 34, 38, 42, 39, 50, 52, 60, 62, 66, 68, 77, 80, 78, 57, 63, 64, 66, 70, 70, 76, 82, 84, 90, 92, 81, 96, 110, 108, 118, 114, 124, 126, 130, 132, 142, 140, 144, 153, 165, 168, 174, 177, 182, 186, 171, 120

Offset: 0

Reinhard Zumkeller, Dec 08 2002

			n=10: sum of the A078822(10)=5 binary numbers: a(10) = '0'+'1'+'10'+'101'+'1010' = 0+1+2+5+10 = 18.

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

Cf. A078822, A078825, A007088, A144623, A144624.

a078823 = sum . a119709_row  -- Reinhard Zumkeller, Aug 14 2013

def a(n): return sum(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

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

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

Showing 1-10 of 29 results. Next

cp's OEIS Frontend

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

A144623 a(n) = A078822(n) - 1.

Views

Author

Keywords

Comments

Links

Programs

Haskell

Extensions

A093641 Numbers of form 2^i * prime(j), i>=0, j>0, together with 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Python

Formula

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

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

A078823 Sum of distinct binary numbers contained as substrings in binary representation of n.

Views

Author

Keywords

Examples

Links

Crossrefs