Sierpinski triangle

Produce an ASCII representation of a Sierpinski triangle of order N. For example, the Sierpinski triangle of order 4 should look like this:


	               *
	              * *
	             *   *
	            * * * *
	           *       *
	          * *     * *
	         *   *   *   *
	        * * * * * * * *
	       *               *
	      * *             * *
	     *   *           *   *
	    * * * *         * * * *
	   *       *       *       *
	  * *     * *     * *     * *
	 *   *   *   *   *   *   *   *
	* * * * * * * * * * * * * * * *

Common Lisp

(defun print-sierpinski (order)
  (loop with size = (expt 2 order)
        repeat size
        for v = (expt 2 (1- size)) then (logxor (ash v -1) (ash v 1))
        do (fresh-line)
           (loop for i below (integer-length v)
                 do (princ (if (logbitp i v) "*" " ")))))

Printing each row could also be done by printing the integer in base 2 and replacing zeroes with spaces: (princ (substitute #\Space #\0 (format nil "~%~2,vR" (1- (* 2 size)) v)))

Replacing the iteration with for v = 1 then (logxor v (ash v 1)) produces a "right" triangle instead of an "equilateral" one.

D

Translate from Lisp examples. <d>module sierpinski ; import std.stdio ;

long ipow(int x, int n) { return n == 0 ? 1 : x*ipow(x, n-1) ; }

void sietri(uint n) {

 if(n > 5) writefln("integer bit size limited : n should not be larger than 5") ;
 long size = ipow(2,n) ;
 long v = ipow(2, size) ;
 foreach(int i; 0..size) {
   foreach(int j; 0..v.sizeof*8) 
     writef(ipow(2,j) & v ? "*" : " ") ;
   writefln() ;
   v = (v << 1) ^ (v >> 1) ;
 }

}

void main() {

 foreach(n; 0..5)
   sietri(n) ;

}</d>

Haskell

sierpinski 0     = ["*"]
sierpinski (n+1) =    map ((space ++) . (++ space)) down 
                   ++ map (unwords . replicate 2)   down
  where down = sierpinski n
        space = replicate (2^n) ' '

printSierpinski = mapM_ putStrLn . sierpinski

J

There are any number of succinct ways to produce this in J. Here's one that exploits self-similarity:

   |._31]\,(,.~,])^:4,:'* '

Here's one that leverages the relationship between Sierpinski's and Pascal's triangles:

   ' *'{~'1'=(-|."_1[:":2|!/~)i.-16