[seqfan] SImplified description of A161373 and A161374
Hagen von Eitzen
hagen at von-eitzen.de
Fri Jun 12 08:29:47 CEST 2009
Hello seqfans,
looking at the above sequences of early bird vs. punctual binary
numbers, as imple pattern emerges.
The proof is not difficult, but could someone please crosscheck if I
didn't miss a case or subcase or subsubsubcase ... ?
1) n = 2^k is punctual for all k>=0:
If a number n is early bird, then either the leading 1 of its binary
representation starts a number having less bits than n has; or another 1
starts a number <= n.
If n=2^k, there is only one 1 and the number starting there must be at
least k+1 digits long.
Therefore n is not early bird
2) n = 2^(2k+1) + 2^k is punctual for all k>=1:
The leading 1 cannot start a shorter number - it would have to be 2^k,
followed by 2^k+1, not matching the last bit.
If a number m<=n starts at the other 1, then it is preceded by m-1,
hence m ends in a 1 followed by (k-1) 0's followed by 1, esp. m>2^k and
m = 2^k +1 mod 2^(k+1).
Then m must begin with a 1, k 0's and then followed by at least k+1
digits, hence m >= 2^(2k+1).
Together with m = 2^k +1 mod 2^(k+1) we conclude m>n.
Hence n is not early bird.
3) All n with at least 3 1's in binary are early bird:
Write n in binary as 1.a.1.b.1.c where '.' denotes concatenation, a,b,c
are (possibly empty) strings and a and c consist only of 0's (i.e. we
have focused on the first, the second and the last 1).
3.1) Assume b contains at least one 0.
Then ingenearal x.b +1 = x.d for a string d with length(d)=length(b).
3.1.1) Assume length(c) > length(a).
Let m = 1.c.1.a.1.b. Then m < n and m+1 = 1.c.1.a.1.d, hence n occurs
early at the junction of m and m+1.
3.1.2) Assume length(c) <= length(a).
Let m = 1.a.1.b < n, then m+1 =1.a.1.d begins with 1.c, hence n occurs
early at the junction of m and m+1.
3.2) Assume b consists only of 1's
3.2.1) Assume length(c)>=length(a).
Let m = 1.c.0.a.1.b, then m<n and m+1 begins with 1.c, hence n occurs
early at the junction of m and m+1.
3.2.2) Assume length(c) < length(a), esp. length(a)>0
Let m = 1.a.1.b < n, then m+1 begins with 1.c, hence n occurs early at
the junction of m and m+1.
4) n = 2^m + 2^k with m>k and m != 2k+1 is early bird:
Write n = 1.a.1.c where a,c consist only of 0's.
4.1) Assume length(c)>length(a)>0.
Then m = 1.c.1.a <n and m+1 begins with 1.c, hence n occurs early at the
junction of m and m+1.
4.2) Assume length(c)<length(a).
Let m = 1.a. Then m+1 begins with 1.c, hence n occurs early at the
junction of m and m+1.
4.3) Assume length(c)>length(a)=0
Then n = 11.c. Let m = 1.c -1. Then m < n and odd, hence n occurs early
at the junction of m and m+1.
Summary:
A number n>3 is punctual iff it is of the form 2^k or 2^(2k+1) + 2^k.
Hagen
More information about the SeqFan
mailing list