3
$\begingroup$

I have been trying to figure out how to get the values for the limits of the Cantor set intervals (see here). The formulas that i could find only gave the interval themselves but what i need is only the limits. For example for set number 1 the limits are 0 and 1, for set number 2 the limits are 0, 1/3, 2/3 and 1 and so on. I need to use these limits in some other calculations.

I have found here how to generate these intervals (see the second answer) but there is a problem with this method. In I want to generate say 25 of these intervals, my computer runs out of memory (I have 16 Gb RAM!). I have adapted that answer for my needs to obtain these limits, see below:

nCantor=5;
cantor=Block[{nn=nCantor,int,intCantor,rule,a,b},
   rule=Interval[{a_,b_}]:>With[{dd=b-a},{Interval[{a,a + dd/3}],Interval[{b-dd/3,b}]}];
   intCantor=NestList[#/.rule&,Interval[{0,1}],nn];
   int=Table[Flatten[intCantor[[i]]],{i,1,Length[intCantor]}];
   Table[
     Flatten[Table[{Min[int[[j,i]]],Max[int[[j,i]]]},{i,1,Length[int[[j]]]}]],
   {j, 1, Length[int]}
   ]
  ];

So for example if you look at element cantor[[5]] the result would be:

{0, 1/81, 2/81, 1/27, 2/27, 7/81, 8/81, 1/9, 2/9, 19/81, 20/81, 7/27, 8/27, 25/81, 26/81, 1/3, 2/3, 55/81, 56/81, 19/27, 20/27, 61/81, 62/81, 7/9, 8/9, 73/81, 74/81, 25/27, 26/27, 79/81, 80/81, 1}

which is what I am looking for.

The question is: Is there a way to obtain these limits faster? I have looked all over and I am stuck. I can calculate these until nCantor=20 but I was hoping to be able to obtain the limits for larger values.

Cheers

$\endgroup$
2
$\begingroup$

Let's try rewriting the code a bit more functionally. This often just helps by itself, but it also just makes the code easier to reason about.

This is just a Map:

int = Table[Flatten[intCantor[[i]]], {i, 1, Length[intCantor]}]

Is

int = Map[Flatten, intCantor]

The last line is also a Map:

Table[{Min[int[[j, i]]], Max[int[[j, i]]]}, {i, 1, Length[int[[j]]]}]

Is

Map[MinMax, int[[j]]]

And the last line is then just:

Map[Flatten]@Map[MinMax, int, {2}]

Rule often should be functions:

rule = Interval[{a_, b_}] :> With[{dd = b - a}, {Interval[{a, a + dd/3}], Interval[{b - dd/3, b}]}];
intCantor = NestList[# /. rule &, Interval[{0, 1}], nn];

Is

intervalSplit[Interval[{a_, b_}]] := 
 With[{dd = b - a}, 
   {Interval[{a, a + dd/3}], Interval[{b - dd/3, b}]}];
intCantor = 
 NestList[Flatten@*Map[intervalSplit], {Interval[{0, 1}]}, nn];

So, I would rewrite the cantor as a function like this:

cantor[nn_] := 
 Module[{intCantor, intervalSplit}, 
  intervalSplit[Interval[{a_, b_}]] := 
   With[{dd = b - a}, {Interval[{a, a + dd/3}], 
     Interval[{b - dd/3, b}]}];
  intCantor = 
   NestList[Flatten@*Map[intervalSplit], {Interval[{0, 1}]}, nn];
  Map[Flatten]@Map[MinMax, intCantor, {2}]]
$\endgroup$
  • $\begingroup$ sorry for the delayed reaction but I had to drop this for a bit. I gave your solution a try today but I get this error: "List or SparseArray or StructuredArray expected at position 1 in MinMax[Interval[{0,1}]]." I think this is because Interval doesn't give you a list! That was the problem with my initial approach. I had to transform the interval in a list somehow. $\endgroup$ – lucian Jan 12 '16 at 9:52
2
$\begingroup$

In each step of constructing the Cantor set, the amount of work to be done doubles, which roughly implies that doing the next step takes as much time as all the previous steps together. So you cannot expect to go very deep; moreover, you will get very long lists of endpoints.

Here is a function for finding the new list of cantorlimits from a given list of cantorlimits.

nextstep[cantorlist_] := Flatten[Table[(1-n/3) z[[1]]+n z[[2]]/3, {z,Partition[cantorlist, 2]}, {n,0,3}]]

Nest[ nextstep, {0,1}, 4]

(* {0,1/81,2/81,1/27,2/27,7/81,8/81,1/9,2/9,19/81,20/81,7/27,8/27,25/81,26/81,1/3,2/3,55/81,56/81,19/27,20/27,61/81,62/81,7/9,8/9,73/81,74/81,25/27,26/27,79/81,80/81,1} *)

Nest[ nextstep, {0,1}, 20] // Length // Timing
(* {20.9665,2097152} *)

Only 20 seconds, so you can go some steps further,

$\endgroup$
  • $\begingroup$ This is another cool method to get the Cantor set, however I think the limit on my machine is around 22 so that's that! I will try to limit my application to these values. At 20 there are a lot of intervals to use! $\endgroup$ – lucian Jan 14 '16 at 12:26
2
$\begingroup$

Check out Stan Wagon's Mathematica in Action, chapter 5. There he defines spawn.

spawn[{a_Rational, b_Rational}] := 
   Module[{w = (b - a)/3}, {{a - 2 w, a - w}, {b + w, b + 2 w}}]
spawn[intervals_List] := Map[spawn, intervals]

Then to get your Cantor endpoints use the following.

cantor[1] = {0, 1};
cantor[n_] := Join[{0}, Sort[Flatten[NestList[spawn, {1/3, 2/3}, n - 2]]], {1}]

There are 2^n terms in cantor[n], so the memory requirements are unavoidable; however, the iterations seem fast enough, depending on your patience. Running cantor[25] took about 100 seconds and required only about 3 GB, on my machine.

$\endgroup$
  • $\begingroup$ I like the spawn function although I don't fully understand it, however I haven't managed to get cantor[25] to calculate. Not in 100 seconds! I will use a smaller value. Thank you for your help! $\endgroup$ – lucian Jan 12 '16 at 10:18
1
$\begingroup$

In version 11.1 you can use CantorMesh and get its MeshCoordinates:

Flatten @ Rationalize @ MeshCoordinates[CantorMesh[4]]

{0, 1/81, 2/81, 1/27, 2/27, 7/81, 8/81, 1/9, 2/9, 19/81, 20/81, 7/27, 8/27, 25/81, 26/81, 1/3, 2/3, 55/81, 56/81, 19/27, 20/27, 61/81, 62/81, 7/9, 8/9, 73/81, 74/81, 25/27, 26/27, 79/81, 80/81, 1}

% == cantor[[5]] (* from OP *)

True

Without Rationalize it is much faster

Flatten@MeshCoordinates[CantorMesh[18]]; // AbsoluteTiming// First

2.88507

Flatten@Rationalize@MeshCoordinates[CantorMesh[18]]; // AbsoluteTiming// First

14.8317

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.