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

Sierpinski Triangle Pattern

Read summary with AI tools

The Sierpinski triangle pattern prints a triangle made of smaller triangles, with the centre of each one cut out. Surprisingly, you get it from Pascal’s triangle by keeping only the odd numbers.

Quick answer: Lay out Pascal’s triangle as usual, with n − i − 1 spaces before row i, but print "* " where the number would be odd and two spaces where it would be even. You never need the numbers: C(i, j) is odd exactly when (j & i) == j, a bitwise AND test. Use a power of 2 such as 8 for n.

This program is part of the Tricky Patterns collection.

Table of contents8 sections
  1. Output
  2. How the sierpinski triangle 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 Triangle Pattern output

Output (8 rows):

       *
      * *
     *   *
    * * * *
   *       *
  * *     * *
 *   *   *   *
* * * * * * * *
Sierpinski Triangle Pattern layout diagram, row by row (8 rows)
How each row of the sierpinski triangle pattern is built (8 rows). Blue cells are printed characters; grey dots are spaces.

How the sierpinski triangle pattern works

Pascal’s numbers grow too quickly to store for many rows, but their parity follows a neat rule known as Lucas’s theorem: C(i, j) is odd when every bit set in j is also set in i. The expression (j & i) == j checks that in one step. Printing a star for odd entries and a gap for even ones draws the famous fractal, and with a power of two rows the picture comes out complete.

  1. Run the outer loop for i from 0 to n − 1.
  2. Print n − i − 1 spaces.
  3. For j from 0 to i, print "* " if (j & i) == j, otherwise two spaces.
  4. Move to the next line.

Key takeaways

  • The Sierpinski triangle is Pascal’s triangle with only the odd entries kept.
  • (j & i) == j tells you whether C(i, j) is odd without computing it.
  • Rows in a power of two (4, 8, 16, 32) give a complete picture.
  • Each position is two characters wide, which keeps the triangle centred like Pascal’s.

Sierpinski Triangle Pattern in C

#include <stdio.h>

int main(void) {
    int n = 8;                              /* a power of 2 gives the cleanest picture */

    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n - i - 1; k++)
            printf(" ");
        for (int j = 0; j <= i; j++)
            printf((j & i) == j ? "* " : "  ");
        printf("\n");
    }
    return 0;
}

Sierpinski Triangle Pattern in C++

#include <iostream>
using namespace std;

int main() {
    int n = 8;                              // a power of 2 gives the cleanest picture

    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n - i - 1; k++)
            cout << " ";
        for (int j = 0; j <= i; j++)
            cout << ((j & i) == j ? "* " : "  ");
        cout << endl;
    }
    return 0;
}

Sierpinski Triangle Pattern in Java

public class SierpinskiTriangle {
    public static void main(String[] args) {
        int n = 8;                              // a power of 2 gives the cleanest picture

        for (int i = 0; i < n; i++) {
            for (int k = 0; k < n - i - 1; k++)
                System.out.print(" ");
            for (int j = 0; j <= i; j++)
                System.out.print((j & i) == j ? "* " : "  ");
            System.out.println();
        }
    }
}

Sierpinski Triangle Pattern in Python

n = 8                                   # a power of 2 gives the cleanest picture

for i in range(n):
    print(" " * (n - i - 1), end="")
    for j in range(i + 1):
        print("* " if (j & i) == j else "  ", end="")
    print()

Time and space complexity

The program tests each of the n(n + 1) / 2 positions once with a single AND, so it runs in O(n²) time with O(1) extra memory.

Frequently asked questions

Why does the bitwise test work?

Lucas’s theorem says C(i, j) is odd when, in binary, j has a 1 only where i also has a 1. For i = 6 (110) and j = 2 (010) that holds, and C(6, 2) = 15 is odd. For j = 1 (001) it fails, and C(6, 1) = 6 is even.

What happens if n is not a power of 2?

The program still runs, but the bottom of the picture is cut off part way through a level, so the last triangles look unfinished. Powers of two end exactly where a level of the fractal ends.

Can I draw it with recursion instead?

Yes: a triangle of size 2k is three triangles of size k. That version is longer and needs a grid in memory; the bitwise test prints the same picture directly, row by row.

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.