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

Sat Jul 17 13:49:46 CEST 2010

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).

Best regards,

----- 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,
>
>
> [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/
>