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.

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