[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
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
_______________________________________________
Seqfan Mailing list - http://list.seqfan.eu/
_____________________________________________________________
Sign up for a 6mb FREE email from
http://www.spl.at
Take a look at our new message boards!
http://chat.spl.at
More information about the SeqFan
mailing list