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

[Vladimir Shevelev]

Thanks, Marc, for your remarks.
 
There are many sequences in OEIS having no any general formula, such that the "decoding" of its definitions is obtained with some exactness connecting with  number of the computed terms.  In such cases we have only an approximative impression about a sequence over its first terms. Therefore, there are so many  b-files ( up to 100,500,1000 etc.) in OEIS making our impression more exact and giving a possibility to compare a sequence with others. The idea to use CF, maybe, is good, but I yet prefer to use the binary expansions.
 
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‎