r3769
Posts:
30
Registered:
12/12/04


Re: Average length of random 1expansions
Posted:
Nov 17, 2000 11:54 PM


Hugo van der Sanden wrote : >rich_burge@mydeja.com wrote: >> >> Hugo van der Sanden wrote: >> > r3769 wrote: >> > > >> > > Hugo van der Sanden wrote: >> > > >r3769 wrote: >> > > >> >> > > >> Given an initial value x[0] with 0<x[0]<1, define a random 1expansion of >> > > >> x[0] recursively as follows: >> > > >> >> > > >> Choose [the integer] a[i] (randomly) subject to floor(a[i]*x[i])=1, >> > > >> and then set x[i+1]=a[i]*x[i]1. >> > > >> >> > > >> The length of a random 1expansion of x[0] is n where x[n]=0. >> > > >> >> > > >> What is the average length of all the random 1expansions of 1/7? >> >> > > >.. and solving gives a = 67, as required. >> > > >> > > If p is prime and 1<n<p, is f(1/p)>f(1/n)? >> > >> > I thought it would be, but no: f(1/13) = 16178/93 > 173, but f(1/17) = >> > 2942345/20304 < 145. It does seem likely that the converse it true, ie >> > that each new maximum will be a prime. >> >> Curiously, the same situation occurs if we modify >> the definition just slightly: >> >> Instead of selecting a[i] randomly from >> [amin..amax], flip a coin and set a[i]=amin if >> the result is heads otherwise set a[i]=amax. >> Here amin is the smallest integer s.t. floor(x[i] >> *amin)=1 and amax is the largest such integer. >> >> Unless I have made an error, f(1/13)=18 and f >> (1/17)=7.8 so my original conjecture is still >> false. I wonder if each new maximum is prime in >> this case? >> >> Just curious, > >Note that f(1/(2^k n)) = n/2 + f(1/n).
I think you wanted to write f(1/2^k n))=k/2 + f(1/n), no?
> >I may have screwed up, but I get f(1/13) = 19 and f(1/17) = 8.8; perhaps >I haven't quite got the same definition as you.
No, I made a mistake.
> >In any case, by the definition I am using the answer is no: f(1/23) = >71, f(1/46) = 71.5, and f(1/k) < 71 for all other k < 46. >
I figured it was to good to be true, thanks.
It is kind of interesting to note that the "coinflip 1expansion" defined above can be generalized:
Given any integer b>0, let amin be the smallest integer s.t. floor(x[i]*amin)=b and amax the largest such integer.
Now let f(b,x)=the average length of all the coinflip bexpansions of x.
For example f(1,1/11)=16, f(2,1/11)=6, f(4,1/11)=4, f(11,1/11)=51, and f(113,1/11)=18.
I suppose it's not too difficult to show the sequence <f(b,1/11)> is bounded, so what is it's sup?
Just curious,
R. Burge

