A144016 -id:A144016 - cp's OEIS frontend

A261461 a(n) is the smallest nonzero number that is not a substring of n in its binary representation.

1, 2, 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

Offset: 0

Reinhard Zumkeller, Aug 30 2015

A261018(n) = a(A260273(n)).
Is a(n) = A091460(n) for n>1? - R. J. Mathar, Sep 02 2015. The lowest counterexample occurs at a(121) = 5 < 6 = A091460(121). - Álvar Ibeas, Sep 08 2020
a(A062289(n))=A261922(A062289(n)); a(A126646(n))!=A261922(A126646(n)). - Reinhard Zumkeller, Sep 17 2015

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
David Consiglio, Jr., Python Program

Cf. A007088, A030308, A260273, A261018; record values and where they occur: A261466, A261467.
See A261922 for a variant.
Cf. A062289, A144016, A261922, A126646.

import Data.List (isInfixOf)
a261461 x = f $ tail a030308_tabf where
   f (cs:css) = if isInfixOf cs (a030308_row x)
                   then f css else foldr (\d v -> 2 * v + d) 0 cs

fQ[m_, n_] := Block[{g}, g[x_] := ToString@ FromDigits@ IntegerDigits[x, 2]; StringContainsQ[g@ n, g@ m]]; Table[k = 1; While[fQ[k, n] && k < n, k++]; k, {n, 85}] (* Michael De Vlieger, Sep 21 2015 *)

from itertools import count
def a(n):
    b, k = bin(n)[2:], 1
    return next(k for k in count(1) if bin(k)[2:] not in b)
print([a(n) for n in range(86)]) # Michael S. Branicky, Feb 26 2023

a(n) = A144016(n) + 1 for any n > 0. - Rémy Sigrist, Mar 10 2018

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

A300654 a(n) is the greatest k such that, for i = 1..k, the binary representation of i appears as a substring in the binary representation of 1/n (ignoring the radix point and adding trailing zeros if necessary in case of a terminating expansion).

Original entry on oeis.org

2, 2, 2, 2, 4, 2, 2, 2, 4, 4, 8, 2, 9, 2, 2, 2, 4, 4, 16, 4, 4, 8, 6, 2, 8, 9, 11, 2, 20, 2, 2, 2, 4, 4, 8, 4, 32, 16, 6, 4, 4, 4, 8, 8, 6, 6, 12, 2, 12, 8, 2, 9, 33, 11, 10, 2, 8, 20, 37, 2, 41, 2, 2, 2, 4, 4, 64, 4, 14, 8, 14, 4, 4, 32, 11, 16, 17, 6, 22, 4

Offset: 1

Rémy Sigrist, Mar 10 2018

Equivalently, a(n) is the greatest k such that A300653(n, k) = k.

This sequence has similarities with A144016: here we consider the binary expansion of 1/n, there the binary expansion of n.

			For n = 19:
- the binary expansion of 1/19 is 0.0000(110101111001010000) (with repeating digits in parentheses),
- the first occurrence of the binary representation of k for k = 1..16 is:
  k   bin(k)  bin(1/19) with bin(k) in parentheses
  --  ------  ------------------------------------
   1      1   0.0000(1)101...
   2     10   0.00001(10)101...
   3     11   0.0000(11)010...
   4    100   0.000011010111(100)101...
   5    101   0.00001(101)011...
   6    110   0.0000(110)101...
   7    111   0.000011010(111)100...
   8   1000   0.00001101011110010(1000)011...
   9   1001   0.000011010111(1001)010...
  10   1010   0.00001(1010)111...
  11   1011   0.0000110(1011)110...
  12   1100   0.00001101011(1100)101...
  13   1101   0.0000(1101)011...
  14   1110   0.0000110101(1110)010...
  15   1111   0.000011010(1111)001...
  16  10000   0.00001101011110010(10000)110...
- the binary representation of 17 (10001) is missing,
- hence a(19) = 16.

Rémy Sigrist, PARI program for A300654

Cf. A144016, A300653, A300630.

PARI
```
See Links section.
```

a(2*n) = a(n).

a(n) = 2 iff n belongs to A300630.

A373553 For any number m, let m* be the bi-infinite string obtained by repetition of the binary expansion of m; a(n) is the largest positive integer k such that the binary expansions of all positive integers <= k are found within n*.

Original entry on oeis.org

1, 2, 1, 2, 3, 3, 1, 2, 4, 2, 3, 4, 3, 3, 1, 2, 4, 2, 4, 2, 3, 3, 3, 4, 4, 3, 3, 4, 3, 3, 1, 2, 4, 2, 4, 2, 6, 6, 4, 2, 6, 2, 3, 6, 3, 3, 3, 4, 4, 6, 4, 6, 3, 3, 3, 4, 4, 3, 3, 4, 3, 3, 1, 2, 4, 2, 4, 2, 6, 6, 4, 2, 4, 2, 7, 4, 6, 7, 4, 2, 6, 2, 7, 2, 3, 3, 3

Offset: 1

Rémy Sigrist, Jun 09 2024

			For n = 9: the binary expansion of 9 is "1001", 9* looks like "...10011001..." and contains the binary expansions of 1, 2, 3 and 4, but not of 5, so a(9) = 4.

Rémy Sigrist, PARI program
Index entries for sequences related to binary expansion of n

Cf. A144016, A373399.

PARI
```
\\ See Links section.
```

def a(n):
    mstar = bin(n)[2:]*2
    knot = next(k for k in range(2, n+2) if bin(k)[2:] not in mstar)
    return knot - 1
print([a(n) for n in range(1, 88)]) # Michael S. Branicky, Jun 14 2024

a(n) >= A144016(n).

a(2^k - 1) = 1 for any k > 0.

A344184 Lexicographically earliest sequence of positive integers such that for any n > 0, the binary expansion of a(n) contains the binary expansion of k for k = 1..n and the binary expansion of a(n+1) is obtained by replacing a possibly empty substring of the binary expansion of a(n) by the binary expansion of n+1.

Original entry on oeis.org

1, 2, 6, 12, 44, 44, 92, 184, 1208, 1336, 5304, 5304, 10680, 10680, 21368, 42736, 567024, 673520, 5383920, 5383920, 21535472, 172283632, 172283632, 172283632, 344774384, 344774384, 344774384, 344774384, 689559280, 689559280, 1379118576, 2758237152, 71477713888

Offset: 1

Rémy Sigrist, May 11 2021

This sequence is a variant of A056744, easier to compute.

This sequence is not weakly increasing; a(109) < a(108).

			The first terms, alongside their binary expansion, are:
  n   a(n)   bin(n)  bin(a(n))
  --  -----  ------  ---------------
   1      1       1                1
   2      2      10               10
   3      6      11              110
   4     12     100             1100
   5     44     101           101100
   6     44     110           101100
   7     92     111          1011100
   8    184    1000         10111000
   9   1208    1001      10010111000
  10   1336    1010      10100111000
  11   5304    1011    1010010111000
  12   5304    1100    1010010111000
  13  10680    1101   10100110111000
  14  10680    1110   10100110111000
  15  21368    1111  101001101111000

Rémy Sigrist, Table of n, a(n) for n = 1..1024
Rémy Sigrist, Binary plot of the first 1024 terms
Rémy Sigrist, PARI program for A344184

Cf. A056744, A144016, A344183.

PARI
```
See Links section.
```

A144016(a(n)) >= n.

cp's OEIS Frontend

A261461 a(n) is the smallest nonzero number that is not a substring of n in its binary representation.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

Python

Formula

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

A300654 a(n) is the greatest k such that, for i = 1..k, the binary representation of i appears as a substring in the binary representation of 1/n (ignoring the radix point and adding trailing zeros if necessary in case of a terminating expansion).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A373553 For any number m, let m* be the bi-infinite string obtained by repetition of the binary expansion of m; a(n) is the largest positive integer k such that the binary expansions of all positive integers <= k are found within n*.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Python

Formula

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula