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
Sierpinski Triangle Pattern output
Output (8 rows):
*
* *
* *
* * * *
* *
* * * *
* * * *
* * * * * * * *
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.
- Run the outer loop for
ifrom 0 ton − 1. - Print
n − i − 1spaces. - For
jfrom 0 toi, print"* "if(j & i) == j, otherwise two spaces. - Move to the next line.
Key takeaways
- The Sierpinski triangle is Pascal’s triangle with only the odd entries kept.
(j & i) == jtells 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.











