New: 203 pattern programs with tested code in C, C++, Java and Python Explore patterns

Sierpinski Carpet Pattern

Read summary with AI tools

The Sierpinski carpet pattern cuts a square into nine smaller squares, removes the middle one, and does the same to every square that is left. On a 9 × 9 grid you can already see the big hole in the centre and eight small holes around it.

Quick answer: Write the row and column numbers in base 3. A cell is a hole if, at the same digit position, both numbers have the digit 1, because that means the cell is in the middle of a 3 × 3 block at that level. The test i % 3 == 1 && j % 3 == 1, repeated after dividing both by 3, checks every level.

This program is part of the Tricky Patterns collection.

Table of contents8 sections
  1. Output
  2. How the sierpinski carpet pattern works
  3. Program in C
  4. Program in C++
  5. Program in Java
  6. Program in Python
  7. Time and space complexity
  8. Frequently asked questions

Sierpinski Carpet Pattern output

Output (9 × 9):

#########
# ## ## #
#########
###   ###
# #   # #
###   ###
#########
# ## ## #
#########
Sierpinski Carpet Pattern layout diagram, row by row (9 × 9)
How each row of the sierpinski carpet pattern is built (9 × 9). Blue cells are printed characters; grey dots are spaces.

How the sierpinski carpet pattern works

Each base-3 digit of a coordinate tells you which third of a block the cell is in at one level of the picture: 0 is the first third, 1 the middle and 2 the last. A cell is removed when it sits in the middle third both across and down at any level. Dividing by 3 drops the last digit, which moves the test up one level. With a power of three for the size, every level of holes is complete.

  1. Run through every cell (i, j) of an n × n grid, counting from 0.
  2. Repeat while either number is above 0: if both i % 3 and j % 3 are 1, the cell is a hole; otherwise divide both by 3.
  3. Print a space for a hole and # for anything else.
  4. Move to the next line after each row.

Key takeaways

  • The carpet removes the middle of every 3 × 3 block, at every size.
  • Base-3 digits tell you where a cell sits at each level.
  • Dividing by 3 moves the test up one level.
  • Sizes 3, 9, 27 and 81 give complete carpets.

Sierpinski Carpet Pattern in C

#include <stdio.h>

int filled(int i, int j) {
    while (i > 0 || j > 0) {
        if (i % 3 == 1 && j % 3 == 1)   /* the middle of a 3 × 3 block at some level */
            return 0;
        i /= 3;
        j /= 3;
    }
    return 1;
}

int main(void) {
    int n = 9;                              /* a power of 3 */

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            printf(filled(i, j) ? "#" : " ");
        printf("\n");
    }
    return 0;
}

Sierpinski Carpet Pattern in C++

#include <iostream>
using namespace std;

bool filled(int i, int j) {
    while (i > 0 || j > 0) {
        if (i % 3 == 1 && j % 3 == 1)   // the middle of a 3 × 3 block at some level
            return false;
        i /= 3;
        j /= 3;
    }
    return true;
}

int main() {
    int n = 9;                              // a power of 3

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cout << (filled(i, j) ? "#" : " ");
        cout << endl;
    }
    return 0;
}

Sierpinski Carpet Pattern in Java

public class SierpinskiCarpet {
    static boolean filled(int i, int j) {
        while (i > 0 || j > 0) {
            if (i % 3 == 1 && j % 3 == 1)   // the middle of a 3 × 3 block at some level
                return false;
            i /= 3;
            j /= 3;
        }
        return true;
    }

    public static void main(String[] args) {
        int n = 9;                              // a power of 3

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                System.out.print(filled(i, j) ? "#" : " ");
            System.out.println();
        }
    }
}

Sierpinski Carpet Pattern in Python

def filled(i, j):
    while i > 0 or j > 0:
        if i % 3 == 1 and j % 3 == 1:   # the middle of a 3 × 3 block at some level
            return False
        i //= 3
        j //= 3
    return True


n = 9                                   # a power of 3

for i in range(n):
    for j in range(n):
        print("#" if filled(i, j) else " ", end="")
    print()

Time and space complexity

Each of the n² cells needs about log₃ n divisions, so the program runs in O(n² log n) time with O(1) extra memory.

Frequently asked questions

Both are fractals made by removing the middle piece again and again. The Sierpinski triangle removes the middle triangle of a triangle; the carpet removes the middle square of a square.

What does a 27 × 27 carpet look like?

It has one large hole in the middle, eight medium holes around it and 64 small holes, all arranged in the same nine-part pattern. Set n = 27 to print it.

Why does the test use base 3?

Because each step cuts a square into three parts across and three down. Base-3 digits match that cutting exactly, digit by digit.

Authored by

Ghanendra Yadav runs Pattern Programs from Bangalore, India. The site started in 2020 to help students practise loops and logic through pattern programs in C, C++, Java and Python. Every program published here is compiled and run before it goes live, and the output shown is the real output.

Latest articles

Leave a comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.