# How to create iterations of the Sierpinski carpet

What I want to do is create a sequence of iterations of the Sierpinski carpet. The Sierpinski carpet is created by dividing the square into nine congruent subsquares and removing the middle one, then then dividing the remaining subsquares into nine smaller subsquares and removing the middle one, then iterating the process.

I created the diagram below using tikz by drawing and, where necessary, filling each individual rectangle. However, this is a tedious and inefficient process, particularly as the next iteration would require an additional 512 white rectangles.

\begin{tikzpicture}
\fill (0, 0) rectangle (1, 1);
\begin{scope}[xshift = 1.5 cm]
\fill (0, 0) rectangle (1, 1);
\fill[color=white] (1/3, 1/3) rectangle (2/3, 2/3);
\end{scope}
\begin{scope}[xshift = 3 cm]
\fill (0, 0) rectangle (1, 1);
\fill[color=white] (1/3, 1/3) rectangle (2/3, 2/3);
\fill[color=white] (1/9, 1/9) rectangle (2/9, 2/9);
\fill[color=white] (4/9, 1/9) rectangle (5/9, 2/9);
\fill[color=white] (7/9, 1/9) rectangle (8/9, 2/9);
\fill[color=white] (1/9, 4/9) rectangle (2/9, 5/9);
\fill[color=white] (7/9, 4/9) rectangle (8/9, 5/9);
\fill[color=white] (1/9, 7/9) rectangle (2/9, 8/9);
\fill[color=white] (4/9, 7/9) rectangle (5/9, 8/9);
\fill[color=white] (7/9, 7/9) rectangle (8/9, 8/9);
\end{scope}
\begin{scope}[xshift = 4.5 cm]
\fill (0, 0) rectangle (1, 1);
\fill[color=white] (1/3, 1/3) rectangle (2/3, 2/3);
\fill[color=white] (1/9, 1/9) rectangle (2/9, 2/9);
\fill[color=white] (4/9, 1/9) rectangle (5/9, 2/9);
\fill[color=white] (7/9, 1/9) rectangle (8/9, 2/9);
\fill[color=white] (1/9, 4/9) rectangle (2/9, 5/9);
\fill[color=white] (7/9, 4/9) rectangle (8/9, 5/9);
\fill[color=white] (1/9, 7/9) rectangle (2/9, 8/9);
\fill[color=white] (4/9, 7/9) rectangle (5/9, 8/9);
\fill[color=white] (7/9, 7/9) rectangle (8/9, 8/9);
\fill[color=white] (4/81, 4/81) rectangle (5/81, 5/81);
\fill[color=white] (13/81, 4/81) rectangle (14/81, 5/81);
\fill[color=white] (22/81, 4/81) rectangle (23/81, 5/81);
\fill[color=white] (31/81, 4/81) rectangle (32/81, 5/81);
\fill[color=white] (40/81, 4/81) rectangle (41/81, 5/81);
\fill[color=white] (49/81, 4/81) rectangle (50/81, 5/81);
\fill[color=white] (58/81, 4/81) rectangle (59/81, 5/81);
\fill[color=white] (67/81, 4/81) rectangle (68/81, 5/81);
\fill[color=white] (76/81, 4/81) rectangle (77/81, 5/81);
\fill[color=white] (4/81, 13/81) rectangle (5/81, 14/81);
\fill[color=white] (22/81, 13/81) rectangle (23/81, 14/81);
\fill[color=white] (31/81, 13/81) rectangle (32/81, 14/81);
\fill[color=white] (49/81, 13/81) rectangle (50/81, 14/81);
\fill[color=white] (58/81, 13/81) rectangle (59/81, 14/81);
\fill[color=white] (76/81, 13/81) rectangle (77/81, 14/81);
\fill[color=white] (4/81, 22/81) rectangle (5/81, 23/81);
\fill[color=white] (13/81, 22/81) rectangle (14/81, 23/81);
\fill[color=white] (22/81, 22/81) rectangle (23/81, 23/81);
\fill[color=white] (31/81, 22/81) rectangle (32/81, 23/81);
\fill[color=white] (40/81, 22/81) rectangle (41/81, 23/81);
\fill[color=white] (49/81, 22/81) rectangle (50/81, 23/81);
\fill[color=white] (58/81, 22/81) rectangle (59/81, 23/81);
\fill[color=white] (67/81, 22/81) rectangle (68/81, 23/81);
\fill[color=white] (76/81, 22/81) rectangle (77/81, 23/81);
\fill[color=white] (4/81, 31/81) rectangle (5/81, 32/81);
\fill[color=white] (13/81, 31/81) rectangle (14/81, 32/81);
\fill[color=white] (22/81, 31/81) rectangle (23/81, 32/81);
\fill[color=white] (58/81, 31/81) rectangle (59/81, 32/81);
\fill[color=white] (67/81, 31/81) rectangle (68/81, 32/81);
\fill[color=white] (76/81, 31/81) rectangle (77/81, 32/81);
\fill[color=white] (4/81, 40/81) rectangle (5/81, 41/81);
\fill[color=white] (22/81, 40/81) rectangle (23/81, 41/81);
\fill[color=white] (58/81, 40/81) rectangle (59/81, 41/81);
\fill[color=white] (76/81, 40/81) rectangle (77/81, 41/81);
\fill[color=white] (4/81, 49/81) rectangle (5/81, 50/81);
\fill[color=white] (13/81, 49/81) rectangle (14/81, 50/81);
\fill[color=white] (22/81, 49/81) rectangle (23/81, 50/81);
\fill[color=white] (58/81, 49/81) rectangle (59/81, 50/81);
\fill[color=white] (67/81, 49/81) rectangle (68/81, 50/81);
\fill[color=white] (76/81, 49/81) rectangle (77/81, 50/81);
\fill[color=white] (4/81, 58/81) rectangle (5/81, 59/81);
\fill[color=white] (13/81, 58/81) rectangle (14/81, 59/81);
\fill[color=white] (22/81, 58/81) rectangle (23/81, 59/81);
\fill[color=white] (31/81, 58/81) rectangle (32/81, 59/81);
\fill[color=white] (40/81, 58/81) rectangle (41/81, 59/81);
\fill[color=white] (49/81, 58/81) rectangle (50/81, 59/81);
\fill[color=white] (58/81, 58/81) rectangle (59/81, 59/81);
\fill[color=white] (67/81, 58/81) rectangle (68/81, 59/81);
\fill[color=white] (76/81, 58/81) rectangle (77/81, 59/81);
\fill[color=white] (4/81, 67/81) rectangle (5/81, 68/81);
\fill[color=white] (22/81, 67/81) rectangle (23/81, 68/81);
\fill[color=white] (31/81, 67/81) rectangle (32/81, 68/81);
\fill[color=white] (49/81, 67/81) rectangle (50/81, 68/81);
\fill[color=white] (58/81, 67/81) rectangle (59/81, 68/81);
\fill[color=white] (76/81, 67/81) rectangle (77/81, 68/81);
\fill[color=white] (4/81, 76/81) rectangle (5/81, 77/81);
\fill[color=white] (13/81, 76/81) rectangle (14/81, 77/81);
\fill[color=white] (22/81, 76/81) rectangle (23/81, 77/81);
\fill[color=white] (31/81, 76/81) rectangle (32/81, 77/81);
\fill[color=white] (40/81, 76/81) rectangle (41/81, 77/81);
\fill[color=white] (49/81, 76/81) rectangle (50/81, 77/81);
\fill[color=white] (58/81, 76/81) rectangle (59/81, 77/81);
\fill[color=white] (67/81, 76/81) rectangle (68/81, 77/81);
\fill[color=white] (76/81, 76/81) rectangle (77/81, 77/81);
\end{scope}
\end{tikzpicture}


What I was hoping to do is adapt Jake's solution using lindenmayer systems to How to create a Sierpinski triangle in LaTeX? to a rectangle, as marsupilam did for a hexagon in Tikz Fractal - Sierpinski Hexagon.

I am aware that questions about generating a Sierpinski carpet have been asked previously. Mark Wibrow's answer to Generating a Sierpinski carpet with tikz does not use a lindenmayer system and causes my system to hang. Henri Menke's answer to Drawing a Simple Fractal in Tikz is beautiful, but it becomes quite small when I reduce the order of the fractal and sits on a vertex rather than a side. I wish to keep each iteration the same size, as shown above.

I suppose that if I set order=\level, I would want to set the \squarewidth=9^\level since each square is divided into nine squares and that I should set the angle=90 since each angle is a right angle. However, I am confused about how to adapt the rules for the symbols X and Y that Jake and marsupilam used in their answers to generate the patterns shown above.

• Where do you need these pictures? Create the pictures you need once, save them as a PDF and only import them in your document. The TikZ library external can do this for you on-the-fly. Oct 13, 2022 at 18:20

Here is a macro that places white nodes at the appropriate locations.

\sierpinski[options]{levels}

The option I have in mind is scale=, but rotate= will work as well. Or xscale= if you want rectangles that aren't squares. Be sure to use transform shape.

\documentclass{article}

\usepackage{tikz}

\newcommand{\sierpinski}[2][]{\tikz[#1]{
\draw[fill=black] rectangle(1,1);
\foreach \n[evaluate=\n as \m using \n-1, evaluate=\n as \s using 1/3^\n, evaluate=\m as \p using 3^\m] in {1,...,#2}{
\foreach \k[evaluate=\k as \x using (2*\k-1)/2/3^\m] in {1,...,\p}{
\foreach \j[evaluate=\j as \y using (2*\j-1)/2/3^\m] in {1,...,\p}{
\node[fill=white, minimum size=\s cm, inner sep=0] at (\x,\y){};
}}}}}

\begin{document}

\end{document}


Here is \sierpinski[scale=3, transform shape]{5}, which is about all my machine can handle. It's O(9ⁿ), so prepare to wait.

• Thank you for your contribution. I am glad that it has earned you some recognition. On my computer, the fifth entry in the row did not render properly, so I am hoping that someone will produce an answer using the Lindenmayer systems library or fractals library. That said, thanks again. Oct 11, 2022 at 23:44
• Once again, I'm stealing your math. Oct 13, 2022 at 18:21
• @Qrrbrbirlbel: Ha! Let's just call it borrowing. Oct 13, 2022 at 20:32
• I got your code to work properly when I switched from using TexMaker to TexStudio as my LaTeX editor since TexStudio compiles faster. What I could not figure out how to do is add nodes below your squares in order to label them. Is there a simple way to do that? Oct 16, 2022 at 14:26
• @N.F.Taussig: each (unscaled) picture is contained in the rectangle (0,0) to (1,1). So inside the tikz picture but not in the for loop you could use \node[below] at (.5,0) {Caption};. You could add this as an additional (or replacement) option to the macro. Sorry I can’t code this right now I’m away from my computer this week. Oct 16, 2022 at 22:32

with an up-to-date https://ctan.org/pkg/pst-fractal and running lualatex :

\documentclass[pstricks]{standalone}
\usepackage{pst-fractal}
\begin{document}

\begin{pspicture}(18,3)
\multido{\iA=1+1,\iB=0+12}{6}{%
\psSierCarpet[scale=0.25,n=\iA](\iB,0.2)}
\end{pspicture}

\end{document}


and with option basecolor=red,linecolor=blue:

• The rest of my document was done with tikz, so I am looking for a tikz solution. However, this will clearly benefit users who use pstricks. Nice job. Oct 14, 2022 at 9:21

You have gotten the tikz answer you were looking for, so I feel free to add an answer made with MetaPost/MetaFun. Probably the code can be optimized, and probably one can do something similar with tikz (but I cannot). The first version draws a square and loops and unfills the parts that should be white. The second uses recursion.

Regarding the timing:

First version: 2.9s
Second version: 1.8s


I have wrapped it into MetaPost pages in ConTeXt lmtx. The file can be compiled with context.

\starttext
\startMPpage[offset=1dk]
vardef sierpinski(expr w, n) =
image(
fill unitsquare scaled w ;
for i = 1 upto n :
for j = 1 upto (3^(i-1)) :
for k = 1 upto (3^(i-1)) :
unfill unitsquare scaled (w/(3^i)) shifted ( (3*j-2)*w/(3^i), (3*k-2)*w/(3^i) ) ;
endfor
endfor
endfor)
enddef ;

for i = 1 upto 3 :
draw sierpinski(3cm,i)   shifted (4*(i-1)*cm,  0  ) ;
draw sierpinski(3cm,i+3) shifted (4*(i-1)*cm, -4cm) ;
endfor ;
\stopMPpage

\startMPpage[offset=1dk]
vardef Sierpinski(expr w,n) =
save tmppic ;
picture tmppic ;
if n = 1 :
image(
fill unitsquare scaled w ;
unfill unitsquare scaled (w/3) shifted (w/3,w/3) ;
)
else :
tmppic := Sierpinski(w, n - 1) scaled 1/3 ;
image(
for i = 1 upto 3 :
for j = 1 upto 3 :
if ((i*j) <> 4) :
draw tmppic shifted (((i-1)/3)*w,((j-1)/3)*w) ;
fi
endfor
endfor
)
fi
enddef ;

for i = 1 upto 3 :
draw Sierpinski(3cm,i)   shifted (4*(i-1)*cm,  0  ) ;
draw Sierpinski(3cm,i+3) shifted (4*(i-1)*cm, -4cm) ;
endfor ;
\stopMPpage
\stoptext


The output looks the same in both variants (as far as I can see), so I only show one of them.

• Thank you for your contribution, which looks good. I am looking for a tikz answer since the rest of my diagrams in the document are done with tikz. The last entry in the row in Sandy G's tikz answer does not render properly on my computer, so I am still hoping for an answer using the tikz lindenmayer systems package or, perhaps, the tikz fractals package. Oct 13, 2022 at 14:42
• I hope you will get a tikz answer that works for you. Oct 13, 2022 at 14:55

# Optimized PGF placing white rectangles.

Here's a PGF version of Sandy G's TikZ nodes-based solution.

A few ideas to further speed up the process:

• No evaluate key from \foreach since it it adds parsing overhand

• Using \inteval (eTeX integer mathematics) that should be faster than PGFmath.

• Using quick versions of a few PGFmath functions.

• Using quick versions of \pgfqpointxy.

• Using quick version \pgfusepathqfill.

We could probably also add quick versions of \pgfpointadd or something like \inteval for decimal values. (I'm just drawing a rectangle from (\x-\s, \x-\s) to (\x+\s, \x+\s) after all.)

(There are also lightweight loop implementation available but I don't know how much they actually add to the compilation time.)

That said, as with Sandy G's solution, this draws white rectangles where you don't actually need one. I'm not a mathematician but there's probably a formula to skip those (but then we already calculated \x and possibly \y).

Either way, since TeX breaks down with \sirpinksiPGFpicture{6} we can create a 6-leveled picture by just placing eight 5s in a matrix. (Which is the first step of the recursion.)

## Code

\documentclass{article}
\usepackage{pgf,pgffor}
\def        \pgfmathqint#1.#2\relax{#1} % not really PGFmath
\newcommand*\pgfmathqdouble[2]{\edef#1{\the\numexpr2*#2\relax}}%
\makeatletter
\newcommand*\pgfmathqpow[3]{%
\pgfmathpow@{#2}{#3}\edef#1{\expandafter\pgfmathqint\pgfmathresult\relax}}
\makeatother
\newcommand*\sirpinksiPGFpicture[2][1cm]{%
\pgfpicture
\pgfsetxvec{\pgfqpoint{#1}{0pt}}
\pgfsetyvec{\pgfqpoint{0pt}{#1}}
\pgfsetbaselinepointnow{\pgfqpointxy{.5}{.5}}% for tabular solution
\pgfpathrectangle{\pgfpointorigin}{\pgfqpointxy{1}{1}}
\pgfusepathqfill
\foreach \n in {1,...,#2}{
\edef\m{\the\numexpr\n-1\relax}
\pgfmathqpow\p{3}{\m}
\pgfmathqdouble\pDoubled{\p}%
\pgfmathsetmacro\s{.5/3^\n}
\foreach \k in {1,...,\p}{
\pgfmathsetmacro\x{(2*\k-1)/\pDoubled}
\foreach \j in {1,...,\p}{
\pgfmathsetmacro\y{(2*\j-1)/\pDoubled}
\pgfpathrectanglecorners
\pgfsetfillcolor{white}
\pgfusepathqfill
\endpgfpicture}
\begin{document}
\centering
\foreach \N in {1,...,5} {\sirpinksiPGFpicture[.19\linewidth]{\N} }

\vspace{5ex}
% save the picture for level 5 in a box
% this makes it easy to reuse it without
% PGF having to recalculate it over and over again
\newsavebox\sirpAtFive
\savebox\sirpAtFive{\sirpinksiPGFpicture[.333\linewidth]{5}}%
\begin{tabular}{@{}c@{}c@{}c@{}}
\usebox\sirpAtFive &   \usebox\sirpAtFive &   \usebox\sirpAtFive \\
\usebox\sirpAtFive &                      &   \usebox\sirpAtFive \\
\usebox\sirpAtFive &   \usebox\sirpAtFive &   \usebox\sirpAtFive \\
\end{tabular}
\end{document}


# TikZ/PGFkeys with recursion

A TikZ/PGFkeys based solution that uses recursion and the even odd rule on only one path!

This only places those “white” rectangles that are actually needed. However, it doesn't actually fill them with white but cuts them out from the base rectangle.

The most important handler here is scoped since it places everything in a group.

There's also a solution that creates level-dependent carpet/split <level> styles that restore the values from before but both break down when used as startCarpet = 6.

It looks like that's just the limit of TeX/PGF/TikZ even when using PGF, no PGFkeys and not everything on one single path.

We can also draw a bunch of boxes (similar to my \fbox version) instead of filling an area which just needs a few adjustments but this also doesn't work anymore with level 6.

Of course, as with the PGF version you can use a box:

\newsavebox\sirpAtFive
\savebox\sirpAtFive{\tikz[baseline={(.5,.5)},x=.3333\linewidth,y=.3333\linewidth]{
\fill[even odd rule] (-.5,-.5) rectangle +(1,1) [startCarpet={5}];}}%
\begin{tabular}{@{}c@{}c@{}c@{}}
\usebox\sirpAtFive &   \usebox\sirpAtFive &   \usebox\sirpAtFive \\
\usebox\sirpAtFive &                      &   \usebox\sirpAtFive \\
\usebox\sirpAtFive &   \usebox\sirpAtFive &   \usebox\sirpAtFive \\
\end{tabular}


However, TeX broke down again when I'm trying to place this on the same page as the other five.

## Code

\documentclass[varwidth]{standalone}
\usepackage{tikz}
\makeatletter
\pgfqkeys{/handlers}{
.scoped/.code=\begingroup\pgfkeys@exp@call{#1}\endgroup,
.--/.code=% decrements a value (only TeX integers!)
\pgfkeyssetevalue{\pgfkeyscurrentpath}
{\the\numexpr\pgfkeysvalueof{\pgfkeyscurrentpath}-1\relax},
.value/.code=% copies the value of one key to another w/o expanding it
\pgfkeysgetvalue{#1}\pgfkeys@temp
\expandafter\pgfkeys@exp@call\expandafter{\pgfkeys@temp},
/utils/TeX/ifnum/.code n args={3}{% \usetikzlibrary{ext.misc}
\ifnum#1\relax\expandafter\pgfutil@firstoftwo\else
\expandafter\pgfutil@secondoftwo\fi{\pgfkeysalso{#2}}{\pgfkeysalso{#3}}}}
\makeatother
\tikzset{
startCarpet/.style={% initialize
carpet/shiftWidth/.initial=1, carpet/drawWidth/.initial=.3333,
carpet/level/.initial/.expanded={#1}, carpet/do},% and go!
carpet/do/.style={%
carpet/place,% level = 1? Stop recursion and do nothing more
/utils/TeX/ifnum={\pgfkeysvalueof{/tikz/carpet/level}=1}{}{%
carpet/level/.--, % level = level - 1
carpet/shiftWidth/.value=/tikz/carpet/drawWidth,
carpet/drawWidth/.evaluated=\pgfkeysvalueof{/tikz/carpet/drawWidth}/3,
carpet/split/.scoped/.list={-+, {0*}+, ++, -{0*}, +{0*}, --, {0*}-, +-}}},
carpet/split/.style 2 args={% #1 = x-prefix, #2 = y-prefix
shift={(#1\pgfkeysvalueof{/tikz/carpet/shiftWidth},
#2\pgfkeysvalueof{/tikz/carpet/shiftWidth})},
carpet/do},
carpet/place/.default=\pgfkeysvalueof{/tikz/carpet/drawWidth},
carpet/place/.style={insert path={(-#1/2, -#1/2) rectangle +(#1,#1)}}}
\begin{document}
\foreach \N in {1,...,5}
\space\tikz[x=.19\linewidth,y=.19\linewidth]
\fill[even odd rule] (-.5,-.5) rectangle +(1,1) (0,0) [startCarpet={\N}];
\end{document}

• I am getting error messages when I try to compile this code. Oct 14, 2022 at 10:26
• @N.F.Taussig What's the error message? It works for me on TeXLive 2022 from Overleaf. Oct 14, 2022 at 10:49
• There are multiple error messages for line 41: \foreach \N in {1,...,5} {\sirpinksiPGFpicture[.19\linewidth]{\N} }, starting with undefined control sequence \pdffor@body, then missing number treated as zero, illegal unit of measure, and so forth. I am using texlive full with TeXMaker on the Linux Mint 21 operating system. I have not checked whether it works on Overleaf. I trust that it does since you have generated beautiful diagrams. Oct 14, 2022 at 14:11
• @N.F.Taussig I've updated my PGF version slightly and added a TikZ/PGFkeys based recursion solution. Has the same limit (level 6). Didn't compare it with any other solution runtime-wise. Oct 14, 2022 at 16:35

Here's a pure LaTeX and recursion version.

This obviouly only works because youre using rectangles (which are very easily placed with a tabular).

## Code

\documentclass{article}
\newcommand*\startCarpet[2][1em]{{%
\renewcommand*\arraystretch{0}%
\setlength\fboxsep{0pt}\setlength\fboxrule{#1}%
\edef\BOX{\noexpand\fbox{%
\noexpand\rule[-\the\dimexpr#1/2\relax]{0pt}{#1}\noexpand\rule{#1}{0pt}}}%
\def\TAB##1{\tabular{@{}c@{}c@{}c@{}}##1&##1&##1\\##1&&##1\\##1&##1&##1\endtabular}%
\def\level{#2}%
\def\doCarpet{%
\ifnum\level=0
\def\next{\TAB{\BOX}}%
\else
\def\next{%
\edef\level{\inteval{\level-1}}%
\TAB{\doCarpet}}%
\fi
\next}
\doCarpet}}
\begin{document}
\centering
\startCarpet{0}
\startCarpet[.3333em]{1}
\startCarpet[.1111em]{2}

\startCarpet[.117em]{3}
\end{document}


## Output

• For very small dimensions, tabular inserts vertical white space between rows I don't know how to remove completely. Oct 13, 2022 at 18:56
• I am getting error messages when I try to compile this code. Oct 14, 2022 at 10:26
• @N.F.Taussig What's the error message? It works for me on TeXLive 2022 from Overleaf. Oct 14, 2022 at 10:48
• Here is the first error message: ! Undefined control sequence.\next ->\edef \level {\inteval{\level -1}}\TAB {\doCarpet } \startCarpet[.3333em]{1}. I am getting multiple error messages for each of the \startCarpet lines. Again, I trust that it works on Overleaf, although your other answer produces a better output than this one for the reason you mentioned in your first comment. Oct 14, 2022 at 14:15