Re: Cantor set

*To*: mathgroup at christensen.cybernetics.net*Subject*: [mg1007] Re: Cantor set*From*: "Lou D'Andria" <lou>*Date*: Mon, 8 May 1995 05:38:28 -0400*Organization*: Wolfram Research, Inc.

In article <3nkc8n$mq8 at news0.cybernetics.net> Hamburger Dani, dani at espresso.fh.huji.ac.il writes: >The ternary Cantor set can be constructed iteratively from the interval [0,1] by >removing at the n+1'th step the middle third of each interval obtained in the >n'th step. >Can anyone come up with a nice MMa formula for calculating the beginning and >end points of the k'th interval (counted from left) in the n'th iteration? All the solutions I've read so far involve determining all the intervals in the Cantor set in the n-th stage (C(n)), and then picking out the k-th interval (Int(n,k)). However, C(n) consists of 2^n intervals, so this approach will be very slow for moderately large n. For larger values of n, it makes sense to do things the other way around. First, figure out where Int(n,k) is, and then compute its endpoints. For instance, C(3) consists of 8 intervals, and so Int(3,7) will be somewhere in the right-most third of C(1) (namely, Int(1,2)), and again in the right-most third of Int(1,2). C(0) --------------------------- Int(0,1) C(1) --------- --------- Int(1,1) Int(1,2) C(2) --- --- --- --- Int(2,4) C(3) - - - - - - - - ^Int(3,7) This 'path' to Int(3,7) is summed up by choosing a path down through the intervals, at each stage deciding to take the left-subinterval or the right. For Int(3,7), the path would be {right, right, left}. This corresponds exactly to the base two representation of 6 (= 7-1). In[56]:= IntegerDigits[6,2] Out[56]= {1, 1, 0} An implementation based on this idea follows. (Forgive my choosing the right third of {-2,1} instead of starting right off with {0,1}. It made findposition[] and the Fold[] cleaner.) --------------------------------------------------------- In[1]:= findposition[n_,k_] := IntegerDigits[-1+k+2^n,2]; In[2]:= makechoice[{x_,y_},direction_] := If[direction===0,{x,x+(y-x)/3},{x+2(y-x)/3,y}]; In[3]:= int[n_,k_] := Fold[makechoice,{-2,1},findposition[n,k]]/;k<=2^n In[4]:= int[3,7] 8 25 Out[4]= {-, --} 9 27 In[5]:= int[50,2^50/2]//Timing 239299329230617529590082 1 Out[5]= {0.433333 Second, {------------------------, -}} 717897987691852588770249 3 ---------------------------------------------------------- Lou