A327232 Smallest integer k such that the set of all n consecutive digits of k equals the set of 0 to 2^n-1 written as n-digit binary numbers.

10, 10011, 1000101110, 1000010011010111100, 100000100011001010011101011011111000, 100000010000110001010001110010010110011010011110101011101101111110000

Offset

1,1

Comments

floor(a(n)/10^(n-1)) is the juxtaposition of a de Bruijn sequence. [This is because the first and last n-1 digits of a(n) are always identical - see my link for a general proof. - Jianing Song, Oct 29 2019]

Links

Table of n, a(n) for n=1..6.

Jianing Song, A general proof that the first and last n-1 digits of a(n) are identical

Eric Weisstein's World of Mathematics, de Bruijn Sequence

Wikipedia, de Bruijn Sequence

Formula

a(n) = A007088(A166315(n))*10^(n-2) + 10^(2^n+n-2) for n > 1. Proof: by the property mentioned in the comment section, write a(n) = (d_1)*10^(2^n+n-2) + (d_2)*10^(2^n+n-3) + ... + (d_2^n)*10^(n-1) + (d_1)*10^(n-2) + (d_2)*10^(n-3) + ... + (d_(n-1))*10^0, d_i = 0 or 1, then d_1 = 1, (d_2)*2^(2^n-1) + (d_3)*2^(2^n-2) + ... + (d_2^n)*2^1 + (d_1)*2^0 >= A166315(n), and d_2, d_3, ..., d_(n-1) >= 0. The equalities can hold simultaneously (when written as a 2^n-digit binary number, A166315(n) begins with n 0's and ends with a 1), which gives the formula. - Jianing Song, Oct 28 2019

a(n) = A004086(floor(A327233(n)/10^(n-2)))*10^(n-2) for n > 1. - Jinyuan Wang, Nov 02 2019

Example

For n = 2, the set of all n consecutive digits of 10011 is {10, 00, 01, 11} and the set of 0 to 2^n-1 in binary is {00, 01, 10, 11}.
For n = 3, the set of all n consecutive digits of 1000101110 is {100, 000, 001, 010, 101, 011, 111, 110} and the set of 0 to 2^n-1 in binary is {000, 001, 010, 011, 100, 101, 110, 111}.

Prog

(PARI) a(n) = {my(v=vector(2^n), w=vector(2^n)); k=2^(2^n+n-2)-1; for(i=1, 2^n, v[i]=fromdigits(binary(i-1))); while(Set(w)!=v, u=binary(k++); w[1]=fromdigits(u)\10^(2^n-1); for(i=2, 2^n, w[i]=u[i+n-1]+10*(w[i-1]%10^(n-1)))); fromdigits(u); }

Crossrefs

Cf. A007088, A166315 (earliest binary de Bruijn sequences), A166316 (largest binary de Bruijn sequences), A327233 (largest k).

Sequence in context: A139109 A317959 A119037 * A266841 A267677 A101305

Adjacent sequences: A327229 A327230 A327231 * A327233 A327234 A327235

Keyword

nonn

Author

Jinyuan Wang, Oct 26 2019

Extensions

a(5)-a(6) from Jinyuan Wang, Nov 02 2019

Status

approved