login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A056744 a(n) is the smallest number which when written in binary contains as substrings the binary expansions of 1..n. 7
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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)

LINKS

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

FORMULA

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

EXAMPLE

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

PROG

(PARI)

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(#L<Z, while((#A<(#L+2))||(A[#L+2]!=#L+1),

      B=binary(x++); A=setbinop((y, z)->fromdigits(B[y..z], 2), [1..#B])); listput(L, x)); Vec(L)

} \\ Davis Smith, May 09 2021

CROSSREFS

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

Sequence in context: A127724 A178008 A266005 * A344184 A164859 A332868

Adjacent sequences:  A056741 A056742 A056743 * A056745 A056746 A056747

KEYWORD

base,nonn

AUTHOR

Fred J. Schalekamp, Aug 15 2000

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 23 04:06 EDT 2021. Contains 348211 sequences. (Running on oeis4.)