OFFSET
0,3
COMMENTS
Theorem: a(n) > 0 for all n > 1.
Proof. The claim is true for 2 <= n <= 7, so assume n >= 8, and let u = 1... denote the binary expansion of n. Let L denote the list of all binary vectors whose concatenation gives A076478.
To show a(n)>0 it is enough to exhibit a pair of successive binary vectors b, c in L whose concatenation contains a copy of u that begins in b and is such that b appears in L before u does. There are three cases.
(i) Suppose n is even, say u = 1x0. Take c = x00, and let b be the vector preceding c in L, so that b = y11, say. Then bc = y11x00 contains u.
(ii) Suppose n = 2^k-1, u = 1^k. Take b = 01^(k-1), c = 10^(k-1), so that bc = 0 1^k 0^(k-1).
(iii) Otherwise, n is an odd number whose binary expansion contains a 0, say u = 1^k 0x1. Take c = 0x10^k, and let b be the vector preceding c in L, so that b = y1^k, say, and bc = y1^k 0x10^k.
In each case we need to verify that b does appear in L before u, but we leave this easy verification to the reader. QED
LINKS
Rémy Sigrist, Table of n, a(n) for n = 0..16384
CROSSREFS
KEYWORD
AUTHOR
N. J. A. Sloane, Dec 14 2017, corrected and extended Dec 17 2017
EXTENSIONS
More terms from Rémy Sigrist, Dec 19 2017
STATUS
approved