[seqfan] Re: "near-Fibonacci sequences" and interval [0,1]

[Vladimir Shevelev]

Dear Marc,
 
You are right that to the (uncancelled) fractions from [0,1] with powers of 2 denominators correspond two different near-Fibonacci sequences. For these fractions x one can consider 
{F_x^(+)(n)} (in case of "more" 1's) and {F_x^(-)(n)} (otherwise). For example, in case of 
x=1/2, we have: {F_x^(+)(n)}={1,1,2,4,7,12,20,33,54,88,...} (cf.A000071:F(n)-1, for n>=1) while {F_x^(-)(n)}={1,2,3,4,6,9,14,22,35,56,...}(cf. A001611:F_n+1, for n>=2), such that  F_x^(+)(n)-F_x^(-)(n)>0, for n>=5 (cf. A001911:F(n)-2).

It is more exactly to say that we have one-to-one correspondence between the set of (infinite) (0,1)-sequences and the set of near-Fibonacci sequences.

 
Best regards,
Vladimir

----- Original Message -----
From: Marc LeBrun <mlb at well.com>
Date: Wednesday, July 7, 2010 3:33
Subject: [seqfan] Re: "near-Fibonacci  sequences" and interval [0,1]
To: Sequence Fanatics <seqfan at list.seqfan.eu>

> >="Vladimir Shevelev" <shevelev at bgu.ac.il>
> > Dear Seq Fans,
>  
> I would like to discuss the following construction.
> It is
> > easy to prove that, for n>=1, the Fibonacci sequence 
> {F(n)}={1,1,2,3,5,8,...}> (A000045) one can reproduce by the 
> recursion: F(n)=1 and, for n>=2,
> > F(n)=floor(\phi*F(n-1)), if n is even, and F(n)=ceil(\phi*F(n-
> 1)), if n is
> > odd, where \phi=Golden ratio.
>   Let x belong to [0,1] with the binary
> > expansion x=0.x_1x_2...x_n..., where x_k, k=0,1,..., is in 
> {0,1}.  Define
> > sequence {F_x(n)} by the recursion F_x(0)=1 and, for n>=2,
> > F_x(n)=foor((\phi*F_x(n-1)), if x_(n-1)=0, and  
> F_x(n)=ceil((\phi*F_x(n-1)),
> > if x_(n-1)=1.
> Then sequence {F_(n)} of Fobonacci numbers corresponds to
> > x=0.010101...=1/3.
> In case of x=2/3=0.10101...we obtain sequence
> > {1,2,3,5,8,...}, i.e. a shift of {F(n)}, while in case of 
> x=1=0.111111...we> obtain sequence {1,2,4,7,12,20,...}, i.e. 
> {F(n+2)-1}_(n>=1)-cf. A000071. Thus
> > sequences {F_x(n)}, when 1/3<=x<=1, it is natural to 
> call "near-Fibonacci
> > sequences". The growth of every near-Fibonacci sequence is 
> O(\phi^n) with the
> > constant C in O(...) in interval [1/sqrt(5), \phi^2/sqrt(5)].
> On the other
> > hand, for x decreases from 1/3 to 0, we have a more 
> complicated law with
> > essentially decreasing growth.  What is this?
>  In case of the ternary
> > expansion y=0.y_1y_2,,,y_n..., where y belongs to the Cantor's 
> set, i.e. y_k
> > is in {0,2}, we obtain "near-Fibonacci sequences" for the part 
> of  Cantor's
> > set in [1/4,1].
>  
> Regards,
> Vladimir Shevelev
> 
> 
> [Terminology note: in the OEIS (and elsewhere) these "control 
> programs" of
> 0s and 1s are often referred to as "characteristic" sequences or 
> functions.]
> Agreed: characteristic sequences can nicely encode the "choices" 
> for a 2-way
> branching process, such as the rounding direction here.
> 
> But characteristic sequences and binary expansions aren't 
> naturally quite
> 1-to-1.  A program with an infinite tail of 0s maps to the 
> same value as
> another program with an infinite tails of 1s.
> 
> So--unless the process always computes equal outputs when fed 
> "numericallyequivalent" programs--beware that x is just an 
> informal shorthand for a
> certain characteristic sequence X, rather than a real magnitude, lest
> glitchy technicalities intrude.
> 
> ====
> 
> Anyway, all that aside, F(n+1)/F(n) being the continued fraction 
> convergentsto phi, I'm guessing that CFs might shed some light here?
> 
> Recall the process for extracting the CF terms for ANY real 
> number p is to
> emit floor(p), then subtract and reciprocate.
> 
> The reciprocation reflects the direction of the real p-line and 
> thus swaps
> the effects of floor and ceiling.  This induces the 
> observed alternation and
> relates to how the convergents of p's CF are alternately above 
> and below p.
> 
> Hence: each characteristic sequence X defines a "variant CF expansion
> process".  Where the Xn deviates from the "classic" 
> alternation, then the
> extraction process uses ceiling instead of floor.
> 
> ----
> 
> BTW instead of mapping 0 to floor and 1 to ceiling we could have 
> built the
> alternation into the process itself, implementing a new 
> interpretation of
> characteristic sequences wherein 0 means "do the vanilla CF 
> thing" for this
> step, while 1 means "do the opposite".
> 
> To switch processors we simply convert between these programming 
> languagesby "XORing with 1/3".
> 
> Similarly, consider another kind of expansion where instead we 
> try to
> preserve direction by reflecting in TWO different ways, taking 
> 1/(1-p)
> versus 1/p.  Is there a characteristic sequence for a CF 
> variant that will
> produce the same expansions as this process?
> 
> ----
> 
> Lastly, recall that the vanilla CF expansion of a quadratic root is
> periodic, and vice versa.  Is this equally true for all 
> variant expansions
> based on periodic programs?
> 
> 
> 
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/
> 

 Shevelev Vladimir‎