Let's define a generalized Cantor set by iteratively deleting some rational length segments from the middle of all intervals that haven't yet been deleted, starting from a single continuous interval.

Given the relative lengths of segments to delete or not, and the number of iterations to do, the problem is to write a program or function that outputs the relative lengths of the segments that have or have not been deleted after n iterations.

Example 3,1,1,1,2

Example: Iteratively delete the 4th and 6th eighth


n – number of iterations, indexed starting from 0 or 1

l – list of segment lengths as positive integers with gcd(l)=1 and odd length, representing the relative lengths of the parts that either stay as they are or get deleted, starting from a segment that doesn't get deleted. Since the list length is odd, the first and last segments never get deleted. For example for the regular Cantor set this would be [1,1,1] for one third that stays, one third that gets deleted and again one third that doesn't.


Integer list o, gcd(o)=1, of relative segment lengths in the nth iteration when the segments that weren't deleted in the previous iteration are replaced by a scaled down copy of the list l. The first iteration is just [1]. You can use any unambiguous output method, even unary.


n=0, l=[3,1,1,1,2] →                 [1]
n=1, l=[3,1,1,1,2] →     [3,    1,    1,    1,    2]
n=2, l=[3,1,1,1,2] → [9,3,3,3,6,8,3,1,1,1,2,8,6,2,2,2,4]

n=3, l=[5,2,3]     → [125,50,75,100,75,30,45,200,75,30,45,60,45,18,27]
n=3, l=[1,1,1]     → [1,1,1,3,1,1,1,9,1,1,1,3,1,1,1]

You can assume the input is valid. This is , so the shortest program measured in bytes wins.

  • \$\begingroup\$ Would it be acceptable to input and output the indices of non-deleted segments instead of the lengths? For instance, [0, 1, 2, 4, 6, 7] instead of [3, 1, 1, 1, 2]? \$\endgroup\$
    – user48543
    May 22, 2018 at 15:06
  • \$\begingroup\$ @Mnemonic it's not too far from unary, so I'd say it's fine. \$\endgroup\$
    – Angs
    May 22, 2018 at 15:25
  • \$\begingroup\$ Could you add one (or multiple) test case(s) for even-sized input-lists? \$\endgroup\$ May 23, 2018 at 7:09
  • 1
    \$\begingroup\$ @KevinCruijssen the input lists are guaranteed to be odd-sized \$\endgroup\$
    – Angs
    May 23, 2018 at 7:18

12 Answers 12


Jelly,  15 13  12 bytes

-2 thanks to Dennis (using a Link rather than a chain allows right to be used implicitly by ¡; No need to wrap the 1 in a list due to the fact that Jelly prints lists of one item the same as the item)
-1 thanks to Erik the Outgolfer (use Ɗ to save the newline from using Ç)


A full program printing a list in Jelly format (so [1] is printed as 1)

Try it online!


1×€³§JḤ$¦ẎƊ¡ - Main link: segmentLengths; iterations
1            - literal 1 (start with a single segment of length 1)
           ¡ - repeat...
             - ...times: implicitly use chain's right argument, iterations
          Ɗ  - ...do: last 3 links as a monad (with 1 then the previous output):
   ³         - (1) program's 3rd argument = segmentLengths
 ×€          -  1  multiply €ach (e.g. [1,2,3] ×€ [1,2,1] = [[1,4,3],[2,4,2],[3,6,3]])
        ¦    -  2  sparse application... 
       $     - (2) ...to: indices: last two links as a monad:
     J       - (2)          range of length = [1,2,3,...,numberOfLists]
      Ḥ      - (2)          double            [2,4,6,...] (note: out-of bounds are ignored by ¦)
    §        - (2) ...of: sum each (i.e. total the now split empty spaces)
         Ẏ   -  3  tighten (e.g. [[1,2,3],4,[5,6,7]] -> [1,2,3,4,5,6,7])
             - implicit print

Python 2, 120 107 104 103 100 99 89 bytes

f=lambda n,l:n and[x*y for i,x in enumerate(l)for y in[f(n-1,l),[sum(l)**~-n]][i%2]]or[1]

Try it online!


  • -10 bytes, thanks to Neil
  • 1
    \$\begingroup\$ 89 bytes \$\endgroup\$
    – Neil
    May 22, 2018 at 21:47

R, 94 bytes


Try it online!


Haskell, 76 58 bytes

l%n=do(x,m)<-l%(n-1)`zip`cycle[l,[sum l]];map(*x)m

Try it online!

The function (%) takes the list of line lengths l as first argument and the number of iterations n as second input.

Thanks to Angs and Ørjan Johansen for -18 bytes!

  • \$\begingroup\$ You should be able to save at least 7 bytes by switching to a recursion on n and dropping # altogether \$\endgroup\$
    – Angs
    May 23, 2018 at 23:59
  • \$\begingroup\$ Independently of @Angs 's suggestion, the original % can be shortened to l%a=do(x,m)<-zip a$a>>[l,[sum l]];(*x)<$>m . \$\endgroup\$ May 24, 2018 at 18:09

JavaScript (Firefox 42-57), 80 bytes

f=(n,l,i=0)=>n--?[for(x of l)for(y of(i^=1)?f(n,l):[eval(l.join`+`)**n])x*y]:[1]

Needs those specific versions because it uses both array comprehensions and exponentiation.


JavaScript (Node.js), 71 bytes


Try it online!


Java 10, 261 bytes

L->n->{if(n<1){L.clear();L.add(1);}else if(n>1){var C=new java.util.ArrayList<Integer>(L);for(int l=C.size(),i,x,t,s;n-->1;)for(i=x=0;i<L.size();){t=L.remove(i);if(i%2<1)for(;i%-~l<l;)L.add(i,C.get((i++-x)%l)*t);else{x++;s=0;for(int c:C)s+=c;L.add(i++,t*s);}}}}

Modifies the input-List instead of returning a new one to save bytes.

Try it online.

L->n->{                       // Method with List and integer parameters and no return-type
  if(n<1){                    //  If `n` is 0:
    L.clear();                //   Remove everything from the List
    L.add(1);}                //   And only add a single 1
                              //  Else-if `n` is 1: Leave the List as is
  else if(n>1){               //  Else-if `n` is 2 or larger:
    var C=new java.util.ArrayList<Integer>(L);
                              //   Create a copy of the input-List
    for(int l=C.size(),       //   Set `l` to the size of the input-List
        i,x,t,s;              //   Index and temp integers
        n-->1;)               //   Loop `n-1` times:
      for(i=x=0;              //    Reset `x` to 0
          i<L.size();){       //    Inner loop `i` over the input-List
        t=L.remove(i);        //     Remove the current item, saving its value in `t`
        if(i%2<1)             //     If the current iteration is even:
          for(;i%-~l<l;)      //      Loop over the copy-List
                              //       And add the values multiplied by `t`
                              //       at index `i` to the List `L`
        else{                 //     Else (the current iteration is odd):
          x++;                //      Increase `x` by 1
          s=0;for(int c:C)s+=c;
                              //      Calculate the sum of the copy-List
          L.add(i++,t*s);}}}} //      Add this sum multiplied by `t`
                              //      at index `i` to the List `L`

Jelly, 13 bytes


Try it online!

Full program. Outputs 1 instead of [1]. Annoyingly, doesn't work like ×S¥ in this context, and ƭ doesn't work well with nilads. >_<


APL (Dyalog Classic), 20 bytes


Try it online!


K (ngn/k), 27 bytes


Try it online!

{ } is a function with arguments x and y

(y;+/y) a pair of y and its sum

{ }[(y;+/y)] projection (aka currying or partial application) of a dyadic function with one argument. x will be (y;+/y) and y will be the argument when applied.

,1 singleton list containing 1

x{ }[ ]/ apply the projection x times

(#y)#x reshape to the length of the current result, i.e. alternate between the outer y and its sum

y* multiply each element of the above with the corresponding element of the current result

,/ concatenate


Ruby, 73 bytes


Try it online!


Pyth, 20 bytes


Input is segment array l, then iterations n. Try it online here, or verify all the test cases at once here.

us.e?%k2*bsQ*LbQGE]1   Implicit, Q=1st arg (segment array), E=2nd arg (iterations)
u                E     Execute E times, with current value G...
                  ]1   ... and initial value [1]:
  .e            G        Map G, with element b and index k:
        *bsQ               Multiply b and the sum of Q {A}
            *LbQ           Multiply each value of Q by b {B}
    ?%k2                   If k is odd, yield {A}, otherwise yield {B}
 s                       Flatten the resulting nested array

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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