[seqfan] Re: SImplified description of A161373 and A161374

[Hagen von EItzen]

Franklin T. Adams-Watters wrote:
> But 22 is punctual.
>
> Franklin T. Adams-Watters
Actually, I think that 22 is *not* punctual:
21 -> 10101, 22 -> 10110
and hence 22 occurs already here:
... 10011 10100 10[101 10]110 ...
which is before the natural position here:
... 10011 10100 10101 [10110] ...

You are right that 22 is listed as member of A161373, but I unterstand 
the given definition
    "Sequence gives numbers which occur in the string ahead of their 
natural place. "
in such a manner that 22 should be considered early bird. (But one migth 
interprete "ahead of" as "completely ahead of"),
But you are also right that the applicable portion 3.2.1 of my proof is 
incorrect / incomplete and requires a correction:

>
>
> -----Original Message-----
> From: Hagen von Eitzen <hagen at von-eitzen.de 
> <http://list.seqfan.eu/cgi-bin/mailman/listinfo/seqfan>>
> ...
> 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
This original case 3.2.1 ...
> 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.
... must be replaced with the following:

3.2.1) Assume length(c) >= length(a).

3.2.1.1) Assume length(a) > 0.
Let m = 1.c.1.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
NB: If for example n=22 (i.e. 10110 in binary) implies m = 21 and hence 
n is "overlappingly" early

3.2.1.2) Assume length(a) = 0.
Then 1.a.1.b.1.c = 11.b.1.c is a sequence of 3 or more 1's followed by 0 
or more 0's, i.e. n = 2^r-2^s for some integers 0 <=s < r.

3.2.1.2.1) Assume length(b)+2 >= length(c)
Let m = 11.b < n. Then m+1 = 1.d where d consists of length(b)+2 zeroes, 
i.e. m+1 begins with 1.c and hence n occurs early at the junction of m 
and m+1.

3.2.1.2.2) Assume length(b) +2 < length(c), esp. length(c) > 0.
Let m = 1.c - 1 < n. Then m ends in 11.b and 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.

As I had feared, another level of subcases was necessary. :)

Now we have the problem to decide which definition to apply (or to 
actually define two (pairs of) sequences).
In the above proof, n is always shown to be at the junction of m and m+1 
for some m < n.
But can we have n = m+1? In that case my interpretation of the 
definition would say that n is early bird, while it is possible that the 
authors Paolo P. Lava & Giorgio Balzarotti had something differnt in 
mind and would reject such "barely early birds".
One has to investigate those cases again:

3.1.1.: Can  m+1 = 1.c.1.a.1.d  = 1.a.1.b.1.c = n? First, this implies a=c.
Since b contains at least one 0, we have b=x.0.(1^t) and then d = x.1.(0^t).
Buit then m+1 = 1.a.1.a.1.x.1.(0^t) =1.a.1.x.0.(1^t).1.a implies that 
a=0^t and cancelling leads to a.1.x =x.0.(1^t).
If I'm not wrong the solutions of this are exactly: a = 0 and x = (01)*. 
This leads to n = 101(01)*0110, i.e. n = (2^(2k+1) +2)/3.
A closer look reveals that n occurs already at m and m+1 for m = 
(n-2)/4, so that these n are early bird with respect to both definitions.

3.1.2.: Since n >= 2m+1 and m>0, we can't have n = m+1.

3.2.1.1: We can indeed have n = m+1, e.g. for n=22:
If m+1 = 1.c.1.a.1.b  +1 = 1.a.1.b.1.c = n, then  length(c)=length(b)+1, 
i.e. writing c = 0^s, b = 1^(s-1) and a = 0^t we have
m+1 = 1.0^s.1.0^t.1^s + 1 = 1.0^s.1.0^(t-1).1.0^s   and n = 
1.0^t.1^(s+1).0^s, which implies s=t and after some cancellation 
1.0^(s-1) = 1^s, i.e. s=1.
Then n = 1.0^t.1.1^(s-1).1.0^s = 1.0.1.1.0 = 22.

3.2.1.2.1: We have n >= 2m+1, hence can't have n=m+1

3.2.1.2.2: m has only length(c) digits, but n has at least length(c) + 3 
digits, hence we can't have n=m+1.

3.2.2: Again n >= 2m+1, hence can't have n=m+1


In summary:
(Unless I have yet mised a subsubsubcase...) my characterization of 
early bird and punctual numbers > 3 remains valid with one possible 
exception:
Whether or not 22 is an early bird, depends on the exact interpretation 
of the definition: Must (the binary representation of) n occur merely 
before its natural position or must it additionally be disjoint with its 
natural position (i.e. occur in the string made from 0,1,...,n-1)?


Thanks again for hinting me at the discrepancy
Hagen