MathGroup Archive 1995

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: copy-paste bitmaps?
  • Next by Date: Multivariate analysis under Mathematica ?!?
  • Previous by thread: Re: Cantor set
  • Next by thread: Re: Cantor set