Lesson 4. The Sierpinski triangle: a fractal from ten gates

After this lesson a real fractal appears on the screen — the Sierpinski triangle: a big triangle made of three like it, each of them of three even smaller ones, and so on down to a single dot. And the logic for it is six AND gates and a tree of OR.

4.1. The idea: not a single common bit

The dot (x, y) is lit if x and y have no common 1 bit: (x AND y) = 0.

Why a triangle? Look at the top bit. If it is 1 in x, the dot is in the right half; in y, in the bottom half. Both 1s at once are forbidden, so the bottom right square is empty, and in the other three the same rule applies to the five lower bits — the same picture at half size. And so six times.

Pascal's triangle gives the same pattern if you colour its odd numbers — that is how it was found long before computers.

4.2. Building

The same project as lesson 3: the scan, two CNT6 and the screen stay. Only the pattern changes — the logic that decides whether the dot (x, y) is lit.

The idea. A dot is lit if x and y have no common 1 bit: (x AND y) = 0.

From this simple rule the Sierpinski triangle grows: a big triangle is made of three like it, only half the size, and each of them of three more… On a 64 × 64 screen there are six such steps — one per bit — and 3⁶ = 729 dots are lit. Pascal's triangle gives the same pattern if you colour its odd numbers.

How to build it: 6 AND gates — one per bit, "both have a 1 in this bit". If any AND is lit, the dot goes dark: we collect all six with a tree of OR, and the last one is a NOR — it both collects and flips.

Step 1. Remove the old pattern

The label pix must keep a single source — the new NOR. Two sources on one label are a short circuit.

Step 2. The Sierpinski pattern

4.3. Check

If the triangle is "torn" or has extra dots, check the pairs on the AND gates: each AND gets bits of x and y with the same number. If the whole screen is dark, check that XOR (pattern) is deleted and pix comes out of the NOR.

Lesson 4 paste (Cmd+I)

Before pasting, delete XOR (pattern), whose output = pix: pix must keep a single source.

# Lesson 4 — the Sierpinski triangle: a dot is lit if (x AND y) = 0.AND(x0, y0, a0)AND(x1, y1, a1)AND(x2, y2, a2)AND(x3, y3, a3)AND(x4, y4, a4)AND(x5, y5, a5)OR(a0, a1, o01)OR(a2, a3, o23)OR(a4, a5, o45)OR(o01, o23, o03)NOR(o03, o45, pix)