# [seqfan] Re: SImplified description of A161373 and A161374

Paolo Lava ppl at spl.at
Tue Jun 16 15:59:09 CEST 2009

```Hagen,

my intention was to consider as "early bird" any number which occurs "complitely ahead of" its natural place. I understand that the definition is a little ambiguous.

In any case you have done a good job!

Paolo

--- math at von-eitzen.de wrote:

From: Hagen von EItzen <math at von-eitzen.de>
To: seqfan at list.seqfan.eu
Subject: [seqfan]   Re: SImplified description of A161373 and A161374
Date: Fri, 12 Jun 2009 18:20:37 +0200

> But 22 is punctual.
>
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
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

_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/

_____________________________________________________________