Discrete Fractals

1. An Interference Pattern of Binary Digits

The applet below builds a fractal-like image using the patterns present in the binary representation of natural numbers. The sharp color boundaries come from the suddenness of bit changes in the vicinity of powers of 2. The self-similarity arises from the recursive nesting of the bit change boundaries. This discrete fractal is not a true fractal since there is no level of detail beyond the 0th bit -- the self-similarity has only a finite depth.

Usage Guide

Color Mixing: Use the scrollbars labeled "R", "G" and "B" to select the red, green and blue intensities of a color.
Color Selection: Mix a color and click the "Set Foreground" button to set it as the foreground color. Mix another color and click the "Set Background" button to set it as the background color. (The background color is the one that appears at the upper left corner.)
Drawing: Click the "F-Draw" button to draw with a fixed cycle. Click the "R-Draw" button to draw with a random cycle.
Image Quality: On machines with small color maps, the following might be of help in getting a sharp image:
- Make sure your browser has a sufficient chunk of the color map. You can, for example, start Netscape with the "-install" option to make it keep a private color map.
- Select foreground and background colors that are quite far apart. Browsers tend to replace similar colors with a single average color -- which makes the image look "dusty."

2. A Discrete Fractal Based on Pascal's Triangle

The binomial coefficient C(n, r) is defined by:

Pascal's triangle is an arrangement of the binomial coefficients in the shape of a triangle with C(n, r) as the rth entry from left in the nth row. The apex of the triangle, namely entry number 0 in row number 0, has C(0,0) = 1. The applet below builds an image by coloring each position in the triangle in one of two different colors based on whether the binomial coefficient at that position is odd or even.

In the final image that is remarkably similar to the Sierpinski triangle fractal, each odd/even value in Pascal's triangle is represented by a single black/white pixel.

A Note on Implementation

Except for building the triangle of numbers in the first step, we need only the parity, not the value, of C(n, r). The parities can be computed in several ways:

C(n, r) is odd if and only if

r(n-r) = 0 or exactly one of C(n-1, r) and C(n-1, r-1) is odd.
E(n) = E(r) + E(n-r) where E(i) is the largest k for which 2^k divides i!.
There are no carries during the binary addition of n-r and r.
At each bit position in the binary representations of n and r, the bit of n greater than or equal to the bit of r.

For the second test, observe that the E(i) values can be precomputed iteratively:

E(0) = 0 E(i+1) = E(i) + number of trailing 0s in the binary representation of i+1

The amortized time for each iterative step is only O(1), though a particular step might take O(log(i)) time. The third and fourth tests, which are essentially the same, can be coded using bit operations as

(~n & r) == 0

The applet uses this test.

Thus, the color of any position in the triangle can be determined in O(1) time, with no bookkeeping information and no knowledge of the color of any neighboring positions. This technique can also be used to draw the Sierpinski triangle fractal on a discrete medium if one is not too particular about the angles of the triangle.

A Bit of Theory

The discrete fractals built by the two applets are quite related, as shown by the following theorem:

Let s be the number of ones in the binary representation of n. Then the nth row of Pascal's triangle has exactly 2^s odd numbers.

This result, the claim above about the amortized cost and the correctness of the last two tests for the parity of C(n, r) can all be proved from the following general theorem by Joseph-Louis Lagrange:

For a prime p, let S(n) be the sum of the digits in the base-p representation of n and let E(n) be the largest k for which p^k divides n!. Then E(n) = (n - S(n)) / (p - 1)

V. B. Balayoghan (vbb@cs.utexas.edu)