Hi, I am working with binary "don't care"-expressions/-numbers. For example, the expression "11xx0" represents a sum of binary coordinates: 11xx0 = 11000 + 11010 + 11100 + 11110 "x" means "don't care if 0 or 1". for all expressions of length 3 ... a Sierpinsky triangle appears xxx = 000 + 001 + 010 + 011 + 100 + 101 + 110 + 111 xx1 = 001 + 011 + 101 + 111 x1x = 010 + 011 + 110 + 111 x11 = 011 + 111 1xx = 100 + 101 + 110 + 111 1x1 = 101 + 111 11x = 110 + 111 111 = 111 now, one reformulate this as a matrix multiplication with a coefficient matrix: |xxx| | 1 1 1 1 1 1 1 1 | |000| |xx1| | 0 1 0 1 0 1 0 1 | |001| |x1x| | 0 0 1 1 0 0 1 1 | |010| |x11| | 0 0 0 1 0 0 0 1 | |011| |1xx| = | 0 0 0 0 1 1 1 1 | * |100| |1x1| | 0 0 0 0 0 1 0 1 | |101| |11x| | 0 0 0 0 0 0 1 1 | |110| |111| | 0 0 0 0 0 0 0 1 | |111| The matrix can (as you probably know) be evaluating the recurrence: | M1(t) M1(t) | | M0(t) M0(t) | M1(t+1) = | | with M0(t+1) = | | | M0(t) M1(t) | | M0(t) M0(t) | for don't-care-expressions of length n this matrix consumes O(2^n*2^n) = O(4^n) units of memory. This memory can be saved if the matrix elements can be queried on the fly without constructing the matrix. So my idea ... * the don't-care expressions of length n xx...x to 11...1 are numbered with i=0,...,2^n-1 * the binary coordinates of length n 00...0 to 11...1 are numbered with j=0,...,2^n-1 to see, if a binary coordinate has to be added to the don't-care sum one has to compare both digit by digit: [1] if don't-care's digit is "x" the binary digit is allowed to have a '0' or '1' [2] if don't-care's digit is "1" the binary digit must be also "1" [3] if checks [1] and [2] pass for all digits of the binary coordinate, is must be added to the don't-care sum. checks [1] and [2] can be summarized in a truth table: dc bc | pass? dc = don't care, bc = binary coord. ------+------ x 0 | 1 (yes) x 1 | 1 (yes) 1 0 | 0 (no) 1 1 | 1 (yes) this means, checks [1] and [2] pass iff dc='x' or dc='1' and bc='1' (short: ~dc|dc&bc). The checks can also be applied to the indices i and j themselves if one thinks 'x' for the '0'-bits in i. The checks can be serialized if one uses C's binary operators: (~i|i&j). If the result consists of n '1'-bits, the matrix contains a '1' in element (i,j); a '0' otherwise. Because it's easier to check whether a number's value is zero and the boolean expression ~(~i|i&j) can be simplified to i&~j: M(i,j) == 1 <=> i&~j == 0 A small C-program that prints the Sierpinsky triangle: #include <stdio.h> int main() { int i,j; for (i=0; i<32; i++) { for (j=0; j<32; j++) putchar((i&~j)?' ':'#'); putchar('\n'); } return 0; } The triangle flips, if you play with the negation symbol "~" before i and j. I had the suspicion I wasn't the first who discovered this ... and indeed I found the formula in a book [[1]] on fractals - discovered by "E.E. Bloch" (1810-1893) - but without mentioning the justification/proof. So if you knew this formula and didn't know why this works ... ;-) [[1]] Peitgen, JÃŒrgens, Saupe: Bausteine des Chaos - Fraktale -- Michael Weitzel ... all work and no play makes Jack a dull boy ...