Sierpinski triangle

From Rosetta Code
Jump to: navigation, search
Task
Sierpinski triangle
You are encouraged to solve this task according to the task description, using any language you may know.

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

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

See Sierpinski triangle/Graphical for graphics images of this pattern. See also Sierpinski carpet

Contents

[edit] ACL2

(defun pascal-row (prev)
(if (endp (rest prev))
(list 1)
(cons (+ (first prev) (second prev))
(pascal-row (rest prev)))))
 
(defun pascal-triangle-r (rows prev)
(if (zp rows)
nil
(let ((curr (cons 1 (pascal-row prev))))
(cons curr (pascal-triangle-r (1- rows) curr)))))
 
(defun pascal-triangle (rows)
(cons (list 1)
(pascal-triangle-r rows (list 1))))
 
(defun print-odds-row (row)
(if (endp row)
(cw "~%")
(prog2$ (cw (if (oddp (first row)) "[]" " "))
(print-odds-row (rest row)))))
 
(defun print-spaces (n)
(if (zp n)
nil
(prog2$ (cw " ")
(print-spaces (1- n)))))
 
(defun print-odds (triangle height)
(if (endp triangle)
nil
(progn$ (print-spaces height)
(print-odds-row (first triangle))
(print-odds (rest triangle) (1- height)))))
 
(defun print-sierpenski (levels)
(let ((height (1- (expt 2 levels))))
(print-odds (pascal-triangle height)
height)))

[edit] Ada

This Ada example creates a string of the binary value for each line, converting the '0' values to spaces.

with Ada.Text_Io; use Ada.Text_Io;
with Ada.Strings.Fixed;
with Interfaces; use Interfaces;
 
procedure Sieteri_Triangles is
subtype Practical_Order is Unsigned_32 range 0..4;
 
 
function Pow(X : Unsigned_32; N : Unsigned_32) return Unsigned_32 is
begin
if N = 0 then
return 1;
else
return X * Pow(X, N - 1);
end if;
end Pow;
 
procedure Print(Item : Unsigned_32) is
use Ada.Strings.Fixed;
package Ord_Io is new Ada.Text_Io.Modular_Io(Unsigned_32);
use Ord_Io;
Temp : String(1..36) := (others => ' ');
First : Positive;
Last  : Positive;
begin
Put(To => Temp, Item => Item, Base => 2);
First := Index(Temp, "#") + 1;
Last  := Index(Temp(First..Temp'Last), "#") - 1;
for I in reverse First..Last loop
if Temp(I) = '0' then
Put(' ');
else
Put(Temp(I));
end if;
end loop;
New_Line;
end Print;
 
procedure Sierpinski (N : Practical_Order) is
Size : Unsigned_32 := Pow(2, N);
V : Unsigned_32 := Pow(2, Size);
begin
for I in 0..Size - 1 loop
Print(V);
V := Shift_Left(V, 1) xor Shift_Right(V,1);
end loop;
end Sierpinski;
 
begin
for N in Practical_Order loop
Sierpinski(N);
end loop;
end Sieteri_Triangles;

alternative using modular arithmetic:

with Ada.Command_Line;
with Ada.Text_IO;
 
procedure Main is
subtype Order is Natural range 1 .. 32;
type Mod_Int is mod 2 ** Order'Last;
 
procedure Sierpinski (N : Order) is
begin
for Line in Mod_Int range 0 .. 2 ** N - 1 loop
for Col in Mod_Int range 0 .. 2 ** N - 1 loop
if (Line and Col) = 0 then
Ada.Text_IO.Put ('X');
else
Ada.Text_IO.Put (' ');
end if;
end loop;
Ada.Text_IO.New_Line;
end loop;
end Sierpinski;
 
N : Order := 4;
begin
if Ada.Command_Line.Argument_Count = 1 then
N := Order'Value (Ada.Command_Line.Argument (1));
end if;
Sierpinski (N);
end Main;

output:

XXXXXXXXXXXXXXXX
X X X X X X X X
XX  XX  XX  XX
X   X   X   X
XXXX    XXXX
X X     X X
XX      XX
X       X
XXXXXXXX
X X X X
XX  XX
X   X
XXXX
X X
XX
X

[edit] ALGOL 68

Translation of: python
Works with: ALGOL 68 version Standard - no extensions to language used
Works with: ALGOL 68G version Any - tested with release mk15-0.8b.fc9.i386
PROC sierpinski = (INT n)[]STRING: (
FLEX[0]STRING d := "*";
FOR i TO n DO
[UPB d * 2]STRING next;
STRING sp := " " * (2 ** (i-1));
FOR x TO UPB d DO
STRING dx = d[x];
next[x] := sp+dx+sp;
next[UPB d+x] := dx+" "+dx
OD;
d := next
OD;
d
);
 
printf(($gl$,sierpinski(4)))

[edit] AutoHotkey

ahk discussion

Loop 6
MsgBox % Triangle(A_Index)
 
Triangle(n,x=0,y=1) { ; Triangle(n) -> string of dots and spaces of Sierpinski triangle
Static t, l ; put chars in a static string
If (x < 1) { ; when called with one parameter
l := 2*x := 1<<(n-1) ; - compute location, string size
VarSetCapacity(t,l*x,32) ; - allocate memory filled with spaces
Loop %x%
NumPut(13,t,A_Index*l-1,"char") ; - new lines in the end of rows
}
If (n = 1) ; at the bottom of recursion
Return t, NumPut(46,t,x-1+(y-1)*l,"char") ; - write "." (better at proportional fonts)
u := 1<<(n-2)
Triangle(n-1,x,y) ; draw smaller triangle here
Triangle(n-1,x-u,y+u) ; smaller triangle down-left
Triangle(n-1,x+u,y+u) ; smaller triangle down right
Return t
}

[edit] AWK

# WST.AWK - Waclaw Sierpinski's triangle contributed by Dan Nielsen
# syntax: GAWK -f WST.AWK [-v X=anychar] iterations
# example: GAWK -f WST.AWK -v X=* 2
BEGIN {
n = ARGV[1] + 0 # iterations
if (n !~ /^[0-9]+$/) { exit(1) }
if (n == 0) { width = 3 }
row = split("X,X X,X X,X X X X",A,",") # seed the array
for (i=1; i<=n; i++) { # build triangle
width = length(A[row])
for (j=1; j<=row; j++) {
str = A[j]
A[j+row] = sprintf("%-*s %-*s",width,str,width,str)
}
row *= 2
}
for (j=1; j<=row; j++) { # print triangle
if (X != "") { gsub(/X/,substr(X,1,1),A[j]) }
sub(/ +$/,"",A[j])
printf("%*s%s\n",width-j+1,"",A[j])
}
exit(0)
}

[edit] BASH (feat. sed & tr)

This version completely avoids any number-theoretic workarounds. Instead, it repeatedly replaces characters by "blocks of characters". The strategy is in no way bash-specific, it would work with any other language just as well, but is particularly well suited for tools like sed and tr.

 
#!/bin/bash
 
# Basic principle:
#
#
# x -> dxd d -> dd s -> s
# xsx dd s
#
# In the end all 'd' and 's' are removed.
# 0x7F800000
function rec(){
if [ $1 == 0 ]
then
echo "x"
else
rec $[ $1 - 1 ] | while read line ; do
echo "$line" | sed "s/d/dd/g" | sed "s/x/dxd/g"
echo "$line" | sed "s/d/dd/g" | sed "s/x/xsx/g"
done
fi
}
 
rec $1 | tr 'dsx' ' *'
 

[edit] BASIC

Works with: QBasic
DECLARE SUB triangle (x AS INTEGER, y AS INTEGER, length AS INTEGER, n AS INTEGER)
 
CLS
triangle 1, 1, 16, 5
 
SUB triangle (x AS INTEGER, y AS INTEGER, length AS INTEGER, n AS INTEGER)
IF n = 0 THEN
LOCATE y, x: PRINT "*";
ELSE
triangle x, y + length, length / 2, n - 1
triangle x + length, y, length / 2, n - 1
triangle x + length * 2, y + length, length / 2, n - 1
END IF
END SUB

Note: The total height of the triangle is 2 * parameter length. It should be power of two so that the pattern matches evenly with the character cells. Value 16 will thus create pattern of 32 lines.

[edit] BBC BASIC

      MODE 8
OFF
 
order% = 5
PROCsierpinski(0, 0, 2^(order%-1))
REPEAT UNTIL GET
END
 
DEF PROCsierpinski(x%, y%, l%)
IF l% = 0 THEN
PRINT TAB(x%,y%) "*";
ELSE
PROCsierpinski(x%, y%+l%, l% DIV 2)
PROCsierpinski(x%+l%, y%, l% DIV 2)
PROCsierpinski(x%+l%+l%, y%+l%, l% DIV 2)
ENDIF
ENDPROC

[edit] C

#include <stdio.h>
 
#define SIZE (1 << 4)
int main()
{
int x, y, i;
for (y = SIZE - 1; y >= 0; y--, putchar('\n')) {
for (i = 0; i < y; i++) putchar(' ');
for (x = 0; x + y < SIZE; x++)
printf((x & y) ? " " : "* ");
}
return 0;
}

[edit] Automaton

This solution uses a cellular automaton (rule 90) with a proper initial status.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
 
#ifndef _POSIX_C_SOURCE
char *strdup(const char *s)
{
int l = strlen(s);
char *r = malloc(l+1);
memcpy(r, s, l+1);
return r;
}
#endif
 
#define truth(X) ((X)=='*'?true:false)
void rule_90(char *evstr)
{
int i;
int l = strlen(evstr);
bool s[3];
char *cp = strdup(evstr);
 
for(i=0;i < l; i++) {
s[1] = truth(cp[i]);
s[0] = (i-1) < 0 ? false : truth(cp[i-1]);
s[2] = (i+1) < l ? truth(cp[i+1]) : false;
if ( (s[0] && !s[2]) || (!s[0] && s[2]) ) {
evstr[i] = '*';
} else {
evstr[i] = ' ';
}
}
free(cp);
}
void sierpinski_triangle(int n)
{
int i;
int l = 1<<(n+1);
char *b = malloc(l+1);
 
memset(b, ' ', l);
b[l] = 0;
b[l>>1] = '*';
 
printf("%s\n", b);
for(i=0; i < l/2-1;i++) {
rule_90(b);
printf("%s\n", b);
}
 
free(b);
}
int main()
{
sierpinski_triangle(4);
return EXIT_SUCCESS;
}

[edit] C++

Works with: C++11

A STL-centric recursive solution that uses the new lambda functions in C++11.

#include <iostream>
#include <string>
#include <list>
#include <algorithm>
#include <iterator>
 
using namespace std;
 
template<typename OutIt>
void sierpinski(int n, OutIt result)
{
if( n == 0 )
{
*result++ = "*";
}
else
{
list<string> prev;
sierpinski(n-1, back_inserter(prev));
 
string sp(1 << (n-1), ' ');
result = transform(prev.begin(), prev.end(),
result,
[sp](const string& x) { return sp + x + sp; });
transform(prev.begin(), prev.end(),
result,
[sp](const string& x) { return x + " " + x; });
}
}
 
int main()
{
sierpinski(4, ostream_iterator<string>(cout, "\n"));
return 0;
}

[edit] C#

using System;
using System.Collections;
 
namespace RosettaCode {
class SierpinskiTriangle {
int len;
BitArray b;
 
public SierpinskiTriangle(int n) {
if (n < 1) {
throw new ArgumentOutOfRangeException("Order must be greater than zero");
}
len = 1 << (n+1);
b = new BitArray(len+1, false);
b[len>>1] = true;
}
 
public void Display() {
for (int j = 0; j < len / 2; j++) {
for (int i = 0; i < b.Count; i++) {
Console.Write("{0}", b[i] ? "*" : " ");
}
Console.WriteLine();
NextGen();
}
}
 
private void NextGen() {
BitArray next = new BitArray(b.Count, false);
for (int i = 0; i < b.Count; i++) {
if (b[i]) {
next[i - 1] = next[i - 1] ^ true;
next[i + 1] = next[i + 1] ^ true;
}
}
b = next;
}
}
}
namespace RosettaCode {
class Program {
static void Main(string[] args) {
SierpinskiTriangle t = new SierpinskiTriangle(4);
t.Display();
}
}
}
Translation of: OCaml
Works with: C# version 3.0+
using System;
using System.Collections.Generic;
using System.Linq;
 
class Program
{
public static List<String> Sierpinski(int n)
{
var lines = new List<string> { "*" };
string space = " ";
 
for (int i = 0; i < n; i++)
{
lines = lines.Select(x => space + x + space)
.Concat(lines.Select(x => x + " " + x)).ToList();
space += space;
}
 
return lines;
}
 
static void Main(string[] args)
{
foreach (string s in Sierpinski(4))
Console.WriteLine(s);
}
}

Or, with fold / reduce (a.k.a. aggregate):

using System;
using System.Collections.Generic;
using System.Linq;
 
class Program
{
static List<string> Sierpinski(int n)
{
return Enumerable.Range(0, n).Aggregate(
new List<string>(){"*"},
(p, i) => {
string SPACE = " ".PadRight((int)Math.Pow(2, i));
 
var temp = new List<string>(from x in p select SPACE + x + SPACE);
temp.AddRange(from x in p select x + " " + x);
 
return temp;
}
);
}
 
static void Main ()
{
foreach(string s in Sierpinski(4)) { Console.WriteLine(s); }
}
}

[edit] Clojure

Translation of: Ada
Translation of: Common Lisp

With a touch of Clojure's sequence handling.

(ns example
(:require [clojure.contrib.math :as math]))
 
; Length of integer in binary
; (copied from a private multimethod in clojure.contrib.math)
(defmulti #^{:private true} integer-length class)
 
(defmethod integer-length java.lang.Integer [n]
(count (Integer/toBinaryString n)))
(defmethod integer-length java.lang.Long [n]
(count (Long/toBinaryString n)))
(defmethod integer-length java.math.BigInteger [n]
(count (.toString n 2)))
 
(defn sierpinski-triangle [order]
(loop [size (math/expt 2 order)
v (math/expt 2 (- size 1))]
(when (pos? size)
(println
(apply str (map #(if (bit-test v %) "*" " ")
(range (integer-length v)))))
(recur
(dec size)
(bit-xor (bit-shift-left v 1) (bit-shift-right v 1))))))
 
(sierpinski-triangle 4)

[edit] 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.


Alternate approach:

(defun sierpinski (n)
(if (= n 0) '("*")
(nconc (mapcar (lambda (e) (format nil "~A~A~0@*~A" (make-string (expt 2 (1- n)) :initial-element #\ ) e)) (sierpinski (1- n)))
(mapcar (lambda (e) (format nil "~A ~A" e e)) (sierpinski (1- n))))))
 
(mapc #'print (sierpinski 4))

[edit] D

[edit] Run-time Version

void main() {
import std.stdio, std.algorithm, std.string, std.array;
 
enum level = 4;
auto d = ["*"];
foreach (immutable n; 0 .. level) {
immutable sp = " ".replicate(2 ^^ n);
d = d.map!(a => sp ~ a ~ sp).array ~
d.map!(a => a ~ " " ~ a).array;
}
d.join("\n").writeln;
}
Output:
               *               
              * *              
             *   *             
            * * * *            
           *       *           
          * *     * *          
         *   *   *   *         
        * * * * * * * *        
       *               *       
      * *             * *      
     *   *           *   *     
    * * * *         * * * *    
   *       *       *       *   
  * *     * *     * *     * *  
 *   *   *   *   *   *   *   * 
* * * * * * * * * * * * * * * *

[edit] Compile-time Version

Same output.

import std.string, std.range;
 
string sierpinski(int level) pure nothrow /*@safe*/ {
auto d = ["*"];
foreach (immutable i; 0 .. level) {
immutable sp = " ".replicate(2 ^^ i);
d = d.map!(a => sp ~ a ~ sp).array ~
d.map!(a => a ~ " " ~ a).array;
}
return d.join("\n");
}
 
pragma(msg, 4.sierpinski);
void main() {}

[edit] Delphi

Translation of: DWScript
program SierpinskiTriangle;
 
{$APPTYPE CONSOLE}
 
procedure PrintSierpinski(order: Integer);
var
x, y, size: Integer;
begin
size := (1 shl order) - 1;
for y := size downto 0 do
begin
Write(StringOfChar(' ', y));
for x := 0 to size - y do
begin
if (x and y) = 0 then
Write('* ')
else
Write(' ');
end;
Writeln;
end;
end;
 
begin
PrintSierpinski(4);
end.

[edit] DWScript

Translation of: E
procedure PrintSierpinski(order : Integer);
var
x, y, size : Integer;
begin
size := (1 shl order)-1;
for y:=size downto 0 do begin
Print(StringOfChar(' ', y));
for x:=0 to size-y do begin
if (x and y)=0 then
Print('* ')
else Print(' ');
end;
PrintLn('');
end;
end;
 
PrintSierpinski(4);
 

[edit] E

def printSierpinski(order, out) {
def size := 2**order
for y in (0..!size).descending() {
out.print(" " * y)
for x in 0..!(size-y) {
out.print((x & y).isZero().pick("* ", " "))
}
out.println()
}
}
? printSierpinski(4, stdout)

Non-ASCII version (quality of results will depend greatly on text renderer):

def printSierpinski(order, out) {
def size := 2**order
for y in (0..!size).descending() {
out.print(" " * y)
for x in 0..!(size-y) {
out.print((x & y).isZero().pick("◢◣", "  "))
}
out.println()
}
}

[edit] Erlang

Translation of: OCaml
-module(sierpinski).
-export([triangle/1]).
 
triangle(N) ->
F = fun(X) -> io:format("~s~n",[X]) end,
lists:foreach(F, triangle(N, ["*"], " ")).
 
triangle(0, Down, _) -> Down;
triangle(N, Down, Sp) ->
NewDown = [Sp++X++Sp || X<-Down]++[X++" "++X || X <- Down],
triangle(N-1, NewDown, Sp++Sp).

[edit] Euphoria

Translation of: BASIC
procedure triangle(integer x, integer y, integer len, integer n)
if n = 0 then
position(y,x) puts(1,'*')
else
triangle (x, y+len, floor(len/2), n-1)
triangle (x+len, y, floor(len/2), n-1)
triangle (x+len*2, y+len, floor(len/2), n-1)
end if
end procedure
 
clear_screen()
triangle(1,1,8,4)

[edit] F#

let sierpinski n =
let rec loop down space n =
if n = 0 then
down
else
loop (List.map (fun x -> space + x + space) down @
List.map (fun x -> x + " " + x) down)
(space + space)
(n - 1)
in loop ["*"] " " n
 
let () =
List.iter (fun (i:string) -> System.Console.WriteLine(i)) (sierpinski 4)

[edit] FALSE

This example is incorrect. Different results with different interpreters (like http://morphett.info/false/false.html and http://www.quirkster.com/iano/js/false-js.html Please fix the code and remove this message.
[[$][$1&["*"]?$~1&[" "]?2/]#%"
"]s: { stars }
[$@$@|@@&~&]x: { xor }
[1\[$][1-\2*\]#%]e: { 2^n }
[e;!1\[$][\$s;!$2*x;!\1-]#%%]t:
4t;!

[edit] Factor

Translation of: OCaml
USING: io kernel math sequences ;
IN: sierpinski
 
: iterate-triangle ( triange spaces -- triangle' )
[ [ dup surround ] curry map ]
[ drop [ dup " " glue ] map ] 2bi append ;
 
: (sierpinski) ( triangle spaces n -- triangle' )
dup 0 = [ 2drop "\n" join ] [
[
[ iterate-triangle ]
[ nip dup append ] 2bi
] dip 1 - (sierpinski)
] if ;
 
: sierpinski ( n -- )
[ { "*" } " " ] dip (sierpinski) print ;

[edit] Forth

: stars ( mask -- )
begin
dup 1 and if [char] * else bl then emit
1 rshift dup
while space repeat drop ;
 
: triangle ( order -- )
1 swap lshift ( 2^order )
1 over 0 do
cr over i - spaces dup stars
dup 2* xor
loop 2drop ;
 
5 triangle

[edit] Fortran

Works with: Fortran version 90 and later

This method calculates a Pascal's triangle and replaces every odd number with a * and every even number with a space. The limitation of this approach is the size of the numbers in the Pascal's triangle. Tryng to print an order 8 Sierpinski's triangle will overflow a 32 bit integer and an order 16 will overflow a 64 bit integer.

program Sierpinski_triangle
implicit none
 
call Triangle(4)
 
contains
 
subroutine Triangle(n)
implicit none
integer, parameter :: i64 = selected_int_kind(18)
integer, intent(in) :: n
integer :: i, k
integer(i64) :: c
 
do i = 0, n*4-1
c = 1
write(*, "(a)", advance="no") repeat(" ", 2 * (n*4 - 1 - i))
do k = 0, i
if(mod(c, 2) == 0) then
write(*, "(a)", advance="no") " "
else
write(*, "(a)", advance="no") " * "
end if
c = c * (i - k) / (k + 1)
end do
write(*,*)
end do
end subroutine Triangle
end program Sierpinski_triangle

[edit] GAP

# Using parity of binomial coefficients
SierpinskiTriangle := function(n)
local i, j, s, b;
n := 2^n - 1;
b := " ";
while Size(b) < n do
b := Concatenation(b, b);
od;
for i in [0 .. n] do
s := "";
for j in [0 .. i] do
if IsEvenInt(Binomial(i, j)) then
Append(s, " ");
else
Append(s, "* ");
fi;
od;
Print(b{[1 .. n - i]}, s, "\n");
od;
end;
 
SierpinskiTriangle(4);
*
* *
* *
* * * *
* *
* * * *
* * * *
* * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *

[edit] gnuplot

Making and printing a text string, using bit-twiddling to decide whether each character should be a space or a star.

# Return a string space or star to print at x,y.
# Must have x<y. x<0 is the left side of the triangle.
# If x<-y then it's before the left edge and the return is a space.
char(x,y) = (y+x>=0 && ((y+x)%2)==0 && ((y+x)&(y-x))==0 ? "*" : " ")
 
# Return a string which is row y of the triangle from character
# position x through to the right hand end x==y, inclusive.
row(x,y) = (x<=y ? char(x,y).row(x+1,y) : "\n")
 
# Return a string of stars, spaces and newlines which is the
# Sierpinski triangle from row y to limit, inclusive.
# The first row is y=0.
triangle(y,limit) = (y <= limit ? row(-limit,y).triangle(y+1,limit) : "")
 
# Print rows 0 to 15, which is the order 4 triangle per the task.
print triangle(0,15)

[edit] Go

"Δ" (Greek capital letter delta) looks good for grain, as does Unicode triangle, "△". ASCII "." and "^" are pleasing. "/\\", "´`", and "◢◣"" make interesting wide triangles.

package main
 
import (
"fmt"
"strings"
"unicode/utf8"
)
 
var order = 4
var grain = "*"
 
func main() {
t := []string{grain + strings.Repeat(" ", utf8.RuneCountInString(grain))}
for ; order > 0; order-- {
sp := strings.Repeat(" ", utf8.RuneCountInString(t[0])/2)
top := make([]string, len(t))
for i, s := range t {
top[i] = sp + s + sp
t[i] += s
}
t = append(top, t...)
}
for _, r := range t {
fmt.Println(r)
}
}

[edit] Groovy

Solution:

def stPoints;
stPoints = { order, base=[0,0] ->
def right = [base[0], base[1]+2**order]
def up = [base[0]+2**(order-1), base[1]+2**(order-1)]
(order == 0) \
? [base]
 : (stPoints(order-1, base) + stPoints(order-1, right) + stPoints(order-1, up))
}
 
def stGrid = { order ->
def h = 2**order
def w = 2**(order+1) - 1
def grid = (0..<h).collect { (0..<w).collect { ' ' } }
stPoints(order).each { grid[it[0]][it[1]] = (order%10).toString() }
grid
}

Test:

stGrid(0).reverse().each { println it.sum() }
println()
stGrid(1).reverse().each { println it.sum() }
println()
stGrid(2).reverse().each { println it.sum() }
println()
stGrid(3).reverse().each { println it.sum() }
println()
stGrid(4).reverse().each { println it.sum() }
println()
stGrid(5).reverse().each { println it.sum() }
println()
stGrid(6).reverse().each { println it.sum() }

Output:

0

 1 
1 1

   2   
  2 2  
 2   2 
2 2 2 2

       3       
      3 3      
     3   3     
    3 3 3 3    
   3       3   
  3 3     3 3  
 3   3   3   3 
3 3 3 3 3 3 3 3

               4               
              4 4              
             4   4             
            4 4 4 4            
           4       4           
          4 4     4 4          
         4   4   4   4         
        4 4 4 4 4 4 4 4        
       4               4       
      4 4             4 4      
     4   4           4   4     
    4 4 4 4         4 4 4 4    
   4       4       4       4   
  4 4     4 4     4 4     4 4  
 4   4   4   4   4   4   4   4 
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4

                               5                               
                              5 5                              
                             5   5                             
                            5 5 5 5                            
                           5       5                           
                          5 5     5 5                          
                         5   5   5   5                         
                        5 5 5 5 5 5 5 5                        
                       5               5                       
                      5 5             5 5                      
                     5   5           5   5                     
                    5 5 5 5         5 5 5 5                    
                   5       5       5       5                   
                  5 5     5 5     5 5     5 5                  
                 5   5   5   5   5   5   5   5                 
                5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5                
               5                               5               
              5 5                             5 5              
             5   5                           5   5             
            5 5 5 5                         5 5 5 5            
           5       5                       5       5           
          5 5     5 5                     5 5     5 5          
         5   5   5   5                   5   5   5   5         
        5 5 5 5 5 5 5 5                 5 5 5 5 5 5 5 5        
       5               5               5               5       
      5 5             5 5             5 5             5 5      
     5   5           5   5           5   5           5   5     
    5 5 5 5         5 5 5 5         5 5 5 5         5 5 5 5    
   5       5       5       5       5       5       5       5   
  5 5     5 5     5 5     5 5     5 5     5 5     5 5     5 5  
 5   5   5   5   5   5   5   5   5   5   5   5   5   5   5   5 
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5

                                                               6                                                               
                                                              6 6                                                              
                                                             6   6                                                             
                                                            6 6 6 6                                                            
                                                           6       6                                                           
                                                          6 6     6 6                                                          
                                                         6   6   6   6                                                         
                                                        6 6 6 6 6 6 6 6                                                        
                                                       6               6                                                       
                                                      6 6             6 6                                                      
                                                     6   6           6   6                                                     
                                                    6 6 6 6         6 6 6 6                                                    
                                                   6       6       6       6                                                   
                                                  6 6     6 6     6 6     6 6                                                  
                                                 6   6   6   6   6   6   6   6                                                 
                                                6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6                                                
                                               6                               6                                               
                                              6 6                             6 6                                              
                                             6   6                           6   6                                             
                                            6 6 6 6                         6 6 6 6                                            
                                           6       6                       6       6                                           
                                          6 6     6 6                     6 6     6 6                                          
                                         6   6   6   6                   6   6   6   6                                         
                                        6 6 6 6 6 6 6 6                 6 6 6 6 6 6 6 6                                        
                                       6               6               6               6                                       
                                      6 6             6 6             6 6             6 6                                      
                                     6   6           6   6           6   6           6   6                                     
                                    6 6 6 6         6 6 6 6         6 6 6 6         6 6 6 6                                    
                                   6       6       6       6       6       6       6       6                                   
                                  6 6     6 6     6 6     6 6     6 6     6 6     6 6     6 6                                  
                                 6   6   6   6   6   6   6   6   6   6   6   6   6   6   6   6                                 
                                6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6                                
                               6                                                               6                               
                              6 6                                                             6 6                              
                             6   6                                                           6   6                             
                            6 6 6 6                                                         6 6 6 6                            
                           6       6                                                       6       6                           
                          6 6     6 6                                                     6 6     6 6                          
                         6   6   6   6                                                   6   6   6   6                         
                        6 6 6 6 6 6 6 6                                                 6 6 6 6 6 6 6 6                        
                       6               6                                               6               6                       
                      6 6             6 6                                             6 6             6 6                      
                     6   6           6   6                                           6   6           6   6                     
                    6 6 6 6         6 6 6 6                                         6 6 6 6         6 6 6 6                    
                   6       6       6       6                                       6       6       6       6                   
                  6 6     6 6     6 6     6 6                                     6 6     6 6     6 6     6 6                  
                 6   6   6   6   6   6   6   6                                   6   6   6   6   6   6   6   6                 
                6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6                                 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6                
               6                               6                               6                               6               
              6 6                             6 6                             6 6                             6 6              
             6   6                           6   6                           6   6                           6   6             
            6 6 6 6                         6 6 6 6                         6 6 6 6                         6 6 6 6            
           6       6                       6       6                       6       6                       6       6           
          6 6     6 6                     6 6     6 6                     6 6     6 6                     6 6     6 6          
         6   6   6   6                   6   6   6   6                   6   6   6   6                   6   6   6   6         
        6 6 6 6 6 6 6 6                 6 6 6 6 6 6 6 6                 6 6 6 6 6 6 6 6                 6 6 6 6 6 6 6 6        
       6               6               6               6               6               6               6               6       
      6 6             6 6             6 6             6 6             6 6             6 6             6 6             6 6      
     6   6           6   6           6   6           6   6           6   6           6   6           6   6           6   6     
    6 6 6 6         6 6 6 6         6 6 6 6         6 6 6 6         6 6 6 6         6 6 6 6         6 6 6 6         6 6 6 6    
   6       6       6       6       6       6       6       6       6       6       6       6       6       6       6       6   
  6 6     6 6     6 6     6 6     6 6     6 6     6 6     6 6     6 6     6 6     6 6     6 6     6 6     6 6     6 6     6 6  
 6   6   6   6   6   6   6   6   6   6   6   6   6   6   6   6   6   6   6   6   6   6   6   6   6   6   6   6   6   6   6   6 
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6

[edit] Haskell

sierpinski 0 = ["*"]
sierpinski n = map ((space ++) . (++ space)) down ++
map (unwords . replicate 2) down
where down = sierpinski (n - 1)
space = replicate (2 ^ (n - 1)) ' '
 
main = mapM_ putStrLn $ sierpinski 4

Output:

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

Using bitwise and between x and y coords:

import Data.Bits ((.&.))
 
sierpinski n = map row [m, m-1 .. 0] where
m = 2^n - 1
row y = replicate y ' ' ++ concatMap cell [0..m - y] where
cell x | y .&. x == 0 = " *"
| otherwise = " "
 
main = mapM_ putStrLn $ sierpinski 4

[edit] Haxe

class Main 
{
static function main()
{
triangle(3);
}
 
static inline var SPACE = ' ';
static inline var STAR = '*';
 
static function triangle(o) {
var n = 1 << o;
var line = new Array<String>();
 
for (i in 0...(n*2)) line[i] = SPACE;
 
line[n] = '*';
 
for (i in 0...n) {
Sys.println(line.join(''));
var u ='*';
var start = n - i;
var end = n + i + 1;
var t = SPACE;
for (j in start...end) {
t = (line[j-1] == line[j+1] ? SPACE : STAR);
line[j-1] = u;
u = t;
}
 
line[n+i] = t;
line[n+i+1] = STAR;
}
}
}

[edit] IDL

The only 'special' thing here is that the math is done in a byte array, filled with the numbers 32 and 42 and then output through a "string(array)" which prints the ascii representation of each individual element in the array.

pro sierp,n
s = (t = bytarr(3+2^(n+1))+32b)
t[2^n+1] = 42b
for lines = 1,2^n do begin
print,string( (s = t) )
for i=1,n_elements(t)-2 do if s[i-1] eq s[i+1] then t[i]=32b else t[i]=42b
end
end

[edit] Icon and Unicon

This is a text based adaption of a program from the IPL and Icon Graphics book. The triangle is presented with a twist. Based on an idea from "Chaos and Fractals" by Peitgen, Jurgens, and Saupe.

# text based adaptaion of 
 
procedure main(A)
 
width := 2 ^ ( 1 + (order := 0 < integer(\A[1]) | 4)) # order of arg[1] or 4
write("Triangle order= ",order)
 
every !(canvas := list(width)) := list(width," ") # prime the canvas
every y := 1 to width & x := 1 to width do # traverse it
if iand(x - 1, y - 1) = 0 then canvas[x,y] := "*" # fill
 
every x := 1 to width & y := 1 to width do
writes((y=1,"\n")|"",canvas[x,y]," ") # print
 
end

Adapted from graphics/sier1.icn

Sample output for order 3:
Triangle order = 2

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

[edit] J

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

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

Here, (,.~ , ])^:4 ,: '* ' is the basic structure (with 4 iterations) and the rest of it is just formatting.

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

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

Here, !/~ i._16 gives us pascal's triangle (and we want a power of 2 (or, for the formatting we are using here a negative of a power of 2) for the size of the square in which contains the triangle, and (2 + |/~) i._16 is a boolean representation where the 1s correspond to odd values in pascal's triangle, and the rest is just formatting.

(Aside: it's popular to say that booleans are not integers, but this is a false representation of George Boole's work.)

[edit] Java

Translation of: JavaScript
public static void triangle(int n){
n= 1 << n;
StringBuilder line= new StringBuilder(); //use a "mutable String"
char t= 0;
char u= 0; // avoid warnings
for(int i= 0;i <= 2 * n;++i)
line.append(" "); //start empty
line.setCharAt(n, '*'); //with the top point of the triangle
for(int i= 0;i < n;++i){
System.out.println(line);
u= '*';
for(int j= n - i;j < n + i + 1;++j){
t= (line.charAt(j - 1) == line.charAt(j + 1) ? ' ' : '*');
line.setCharAt(j - 1, u);
u= t;
}
line.setCharAt(n + i, t);
line.setCharAt(n + i + 1, '*');
}
}
Translation of: Haskell
Works with: Java version 1.5+
import java.util.*;
 
public class Sierpinski
{
public static List<String> sierpinski(int n)
{
List<String> down = Arrays.asList("*");
String space = " ";
for (int i = 0; i < n; i++) {
List<String> newDown = new ArrayList<String>();
for (String x : down)
newDown.add(space + x + space);
for (String x : down)
newDown.add(x + " " + x);
 
down = newDown;
space += space;
}
return down;
}
 
public static void main(String[] args)
{
for (String x : sierpinski(4))
System.out.println(x);
}
}

[edit] JavaFX Script

Translation of: Python
function sierpinski(n : Integer) {
var down = ["*"];
var space = " ";
for (i in [1..n]) {
down = [for (x in down) "{space}{x}{space}", for (x in down) "{x} {x}"];
space = "{space}{space}";
}
 
for (x in down) {
println("{x}")
}
}
 
sierpinski(4);

[edit] JavaScript

function triangle(o) {
var n = 1<<o, line = new Array(2*n), i,j,t,u;
for (i=0; i<line.length; ++i) line[i] = '&nbsp;';
line[n] = '*';
for (i=0; i<n; ++i) {
document.write(line.join('')+"\n");
u ='*';
for(j=n-i; j<n+i+1; ++j) {
t = (line[j-1] == line[j+1] ? '&nbsp;' : '*');
line[j-1] = u;
u = t;
}
line[n+i] = t;
line[n+i+1] = '*';
}
}
document.write("<pre>\n");
triangle(6);
document.write("</pre>");

[edit] Julia

pprint(matrix) = print(mapslices(x-> [join(x)], matrix, [2]))
 
spaces(m,n) = [" " for i=1:m, j=1:n]
 
function sierpinski(n)
x = ["*" for i=1, j=1]
for i = 1:n
h,w = size(x)
s = spaces(h,(w+1)/2)
t = spaces(h,1)
x = [[s x s] ; [x t x]]
end
x
end
 
Output:
julia> pprint(sierpinski(4))
               *               
              * *              
             *   *             
            * * * *            
           *       *           
          * *     * *          
         *   *   *   *         
        * * * * * * * *        
       *               *       
      * *             * *      
     *   *           *   *     
    * * * *         * * * *    
   *       *       *       *   
  * *     * *     * *     * *  
 *   *   *   *   *   *   *   * 
* * * * * * * * * * * * * * * *

[edit] Liberty BASIC

nOrder=4
call triangle 1, 1, nOrder
end
 
SUB triangle x, y, n
IF n = 0 THEN
LOCATE x,y: PRINT "*";
ELSE
n=n-1
length=2^n
call triangle x, y+length, n
call triangle x+length, y, n
call triangle x+length*2, y+length, n
END IF
END SUB

[edit]

; Print rows of the triangle from 0 to :limit inclusive.
; limit=15 gives the order 4 form per the task.
; The range of :y is arbitrary, any rows of the triangle can be printed.
 
make "limit 15
for [y 0 :limit] [
for [x -:limit :y] [
type ifelse (and :y+:x >= 0  ; blank left of triangle
(remainder :y+:x 2) = 0  ; only "even" squares
(bitand :y+:x :y-:x) = 0  ; Sierpinski bit test
) ["*] ["| |]  ; star or space
]
print []
]

[edit] Mathematica

Cellular automaton (rule 90) based solution:

n=4;Grid[CellularAutomaton[90,{{1},0},2^n-1]/.{0->" ",1->"*"},ItemSize->All]

[edit] NetRexx

Translation of: Java
/* NetRexx */
options replace format comments java crossref symbols nobinary
 
numeric digits 1000
runSample(arg)
return
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method runSample(arg) public static
BLACK_UPPOINTING_TRIANGLE = '\u25b2'
parse arg ordr filr .
if ordr = '' | ordr = '.' then ordr = 4
if filr = '' | filr = '.' then filler = BLACK_UPPOINTING_TRIANGLE
else filler = filr
drawSierpinskiTriangle(ordr, filler)
return
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method drawSierpinskiTriangle(ordr, filler = Rexx '^') public static
n = 1 * (2 ** ordr)
line = ' '.copies(2 * n)
line = line.overlay(filler, n + 1) -- set the top point of the triangle
loop row = 1 to n -- NetRexx arrays, lists etc. index from 1
say line.strip('t')
u = filler
loop col = 2 + n - row to n + row
cl = line.substr(col - 1, 1)
cr = line.substr(col + 1, 1)
if cl == cr then t = ' '
else t = filler
line = line.overlay(u, col - 1)
u = t
end col
j2 = n + row - 1
j3 = n + row
line = line.overlay(t, j2 + 1)
line = line.overlay(filler, j3 + 1)
end row
return
 
Output:
                ▲
               ▲ ▲
              ▲   ▲
             ▲ ▲ ▲ ▲
            ▲       ▲
           ▲ ▲     ▲ ▲
          ▲   ▲   ▲   ▲
         ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲
        ▲               ▲
       ▲ ▲             ▲ ▲
      ▲   ▲           ▲   ▲
     ▲ ▲ ▲ ▲         ▲ ▲ ▲ ▲
    ▲       ▲       ▲       ▲
   ▲ ▲     ▲ ▲     ▲ ▲     ▲ ▲
  ▲   ▲   ▲   ▲   ▲   ▲   ▲   ▲
 ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲

[edit] Nimrod

Translation of: C
const size = 1 shl 4 - 1
 
for y in countdown(size, 0):
for i in 0 .. <y:
stdout.write " "
for x in 0 .. size-y:
if (x and y) != 0:
stdout.write " "
else:
stdout.write "* "
stdout.write "\n"

[edit] OCaml

let sierpinski n =
let rec loop down space n =
if n = 0 then
down
else
loop (List.map (fun x -> space ^ x ^ space) down @
List.map (fun x -> x ^ " " ^ x) down)
(space ^ space)
(n - 1)
in loop ["*"] " " n
 
let () =
List.iter print_endline (sierpinski 4)

[edit] Oz

declare
fun {NextTriangle Triangle}
Sp = {Spaces {Length Triangle}}
in
{Flatten
[{Map Triangle fun {$ X} Sp#X#Sp end}
{Map Triangle fun {$ X} X#" "#X end}
]}
end
 
fun {Spaces N} if N == 0 then nil else & |{Spaces N-1} end end
 
fun lazy {Iterate F X}
X|{Iterate F {F X}}
end
 
SierpinskiTriangles = {Iterate NextTriangle ["*"]}
in
{ForAll {Nth SierpinskiTriangles 5} System.showInfo}

[edit] PARI/GP

Translation of: C
Sierpinski(n)={
my(s=2^n-1);
forstep(y=s,0,-1,
for(i=1,y,print1(" "));
for(x=0,s-y,
print1(if(bitand(x,y)," ","*"))
);
print()
)
};
Sierpinski(4)
Output:
               *
              **
             * *
            ****
           *   *
          **  **
         * * * *
        ********
       *       *
      **      **
     * *     * *
    ****    ****
   *   *   *   *
  **  **  **  **
 * * * * * * * *
****************

[edit] Pascal

Translation of: C
Works with: Free Pascal
program Sierpinski;
 
function ipow(b, n : Integer) : Integer;
var
i : Integer;
begin
ipow := 1;
for i := 1 to n do
ipow := ipow * b
end;
 
function truth(a : Char) : Boolean;
begin
if a = '*' then
truth := true
else
truth := false
end;
function rule_90(ev :  String) : String;
var
l, i : Integer;
cp : String;
s : Array[0..1] of Boolean;
begin
l := length(ev);
cp := copy(ev, 1, l);
for i := 1 to l do begin
if (i-1) < 1 then
s[0] := false
else
s[0] := truth(ev[i-1]);
if (i+1) > l then
s[1] := false
else
s[1] := truth(ev[i+1]);
if ( (s[0] and not s[1]) or (s[1] and not s[0]) ) then
cp[i] := '*'
else
cp[i] := ' ';
end;
rule_90 := cp
end;
 
procedure triangle(n : Integer);
var
i, l : Integer;
b : String;
begin
l := ipow(2, n+1);
b := ' ';
for i := 1 to l do
b := concat(b, ' ');
b[round(l/2)] := '*';
writeln(b);
for i := 1 to (round(l/2)-1) do begin
b := rule_90(b);
writeln(b)
end
end;
begin
triangle(4)
end.

[edit] Perl

sub sierpinski {
my ($n) = @_;
my @down = '*';
my $space = ' ';
foreach (1..$n) {
@down = (map("$space$_$space", @down), map("$_ $_", @down));
$space = "$space$space";
}
return @down;
}
 
print "$_\n" foreach sierpinski 4;

[edit] Perl 6

Translation of: Perl
sub sierpinski ($n) {
my @down = '*';
my $space = ' ';
for ^$n {
@down = @down.map({"$space$_$space"}), @down.map({"$_ $_"});
$space x= 2;
}
return @down;
}
 
.say for sierpinski 4;

[edit] PL/I

sierpinski: procedure options (main); /* 2010-03-30 */
declare t (79,79) char (1);
declare (i, j, k) fixed binary;
declare (y, xs, ys, xll, xrr, ixrr, limit) fixed binary;
 
t = ' ';
xs = 40; ys = 1;
/* Make initial triangle */
call make_triangle (xs, ys);
y = ys + 4;
xll = xs-4; xrr = xs+4;
do k = 1 to 3;
limit = 0;
do forever;
ixrr = xrr;
do i = xll to xll+limit by 8;
if t(y-1, i) = ' ' then
do;
call make_triangle (i, y);
if t(y+3,i-5) = '*' then
t(y+3,i-4), t(y+3,ixrr+4) = '*';
call make_triangle (ixrr, y);
end;
ixrr = ixrr - 8;
end;
xll = xll - 4; xrr = xrr + 4;
y = y + 4;
limit = limit + 8;
if xll+limit > xs-1 then leave;
end;
t(y-1,xs) = '*';
end;
 
/* Finished generation; now print the Sierpinski triangle. */
put edit (t) (skip, (hbound(t,2)) a);
 
make_triangle: procedure (x, y);
declare (x, y) fixed binary;
declare i fixed binary;
 
do i = 0 to 3;
t(y+i, x-i), t(y+i, x+i) = '*';
end;
do i = x-2 to x+2; /* The base of the triangle. */
t(y+3, i) = '*';
end;
end make_triangle;
 
end sierpinski;

[edit] PicoLisp

Translation of: Python
(de sierpinski (N)
(let (D '("*") S " ")
(do N
(setq
D (conc
(mapcar '((X) (pack S X S)) D)
(mapcar '((X) (pack X " " X)) D) )
S (pack S S) ) )
D ) )
 
(mapc prinl (sierpinski 4))

[edit] PostScript

This draws the triangles in a string-rewrite fashion, where all edges form a single polyline. 9 page document showing progession.

%!PS-Adobe-3.0
%%BoundingBox 0 0 300 300
 
/F { 1 0 rlineto } def
/+ { 120 rotate } def
/- {-120 rotate } def
/v {.5 .5 scale } def
/^ { 2 2 scale } def
/!0{ dup 1 sub dup -1 eq not } def
 
/X { !0 { v X + F - X - F + X ^ } { F } ifelse pop } def
 
0 1 8 { 300 300 scale 0 1 12 div moveto
X + F + F fill showpage } for
%%EOF

[edit] Pop11

Solution using line buffer in an integer array oline, 0 represents ' ' (space), 1 represents '*' (star).

define triangle(n);
lvars k = 2**n, j, l, oline, nline;
initv(2*k+3) -> oline;
initv(2*k+3) -> nline;
for l from 1 to 2*k+3 do 0 -> oline(l) ; endfor;
1 -> oline(k+2);
0 -> nline(1);
0 -> nline(2*k+3);
for j from 1 to k do
for l from 1 to 2*k+3 do
printf(if oline(l) = 0 then ' ' else '*' endif);
endfor;
printf('\n');
for l from 2 to 2*k+2 do
(oline(l-1) + oline(l+1)) rem 2 -> nline(l);
endfor;
(oline, nline) -> (nline, oline);
endfor;
enddefine;
 
triangle(4);

Alternative solution, keeping all triangle as list of strings

define triangle2(n);
lvars acc = ['*'], spaces = ' ', j;
for j from 1 to n do
maplist(acc, procedure(x); spaces >< x >< spaces ; endprocedure)
<> maplist(acc, procedure(x); x >< ' ' >< x ; endprocedure) -> acc;
spaces >< spaces -> spaces;
endfor;
applist(acc, procedure(x); printf(x, '%p\n'); endprocedure);
enddefine;
 
triangle2(4);

[edit] PowerShell

Translation of: JavaScript
function triangle($o) {
$n = [Math]::Pow(2, $o)
$line = ,' '*(2*$n+1)
$line[$n] = '█'
$OFS = ''
for ($i = 0; $i -lt $n; $i++) {
Write-Host $line
$u = '█'
for ($j = $n - $i; $j -lt $n + $i + 1; $j++) {
if ($line[$j-1] -eq $line[$j+1]) {
$t = ' '
} else {
$t = '█'
}
$line[$j-1] = $u
$u = $t
}
$line[$n+$i] = $t
$line[$n+$i+1] = '█'
}
}

[edit] Prolog

Works with SWI-Prolog;

sierpinski_triangle(N) :-
Len is 2 ** (N+1) - 1,
length(L, Len),
numlist(1, Len, LN),
maplist(init(N), L, LN),
atomic_list_concat(L, Line),
writeln(Line),
NbTours is 2**N - 1,
loop(NbTours, LN, Len, L).
 
init(N, Cell, Num) :-
( Num is 2 ** N + 1 -> Cell = *; Cell = ' ').
 
loop(0, _, _, _) :- !.
 
loop(N, LN, Len, L) :-
maplist(compute_next_line(Len, L), LN, L1),
atomic_list_concat(L1, Line),
writeln(Line),
N1 is N - 1,
loop(N1, LN, Len, L1).
 
 
 
compute_next_line(Len, L, I, V) :-
I1 is I - 1,
I2 is I+1,
( I = 1 -> V0 = ' '; nth1(I1, L, V0)),
nth1(I, L, V1),
( I = Len -> V2 = ' '; nth1(I2, L, V2)),
rule_90(V0, V1, V2, V).
 
rule_90('*','*','*', ' ').
rule_90('*','*',' ', '*').
rule_90('*',' ','*', ' ').
rule_90('*',' ',' ', '*').
rule_90(' ','*','*', '*').
rule_90(' ','*',' ', ' ').
rule_90(' ',' ','*', '*').
rule_90(' ',' ',' ', ' ').
 

Output :

 ?- sierpinski_triangle(4).
                *                
               * *               
              *   *              
             * * * *             
            *       *            
           * *     * *           
          *   *   *   *          
         * * * * * * * *         
        *               *        
       * *             * *       
      *   *           *   *      
     * * * *         * * * *     
    *       *       *       *    
   * *     * *     * *     * *   
  *   *   *   *   *   *   *   *  
 * * * * * * * * * * * * * * * * 
true 

[edit] PureBasic

Procedure Triangle (X,Y, Length, N)
If N = 0
DrawText( Y,X, "*",#Blue)
Else
Triangle (X+Length, Y, Length/2, N-1)
Triangle (X, Y+Length, Length/2, N-1)
Triangle (X+Length, Y+Length*2, Length/2, N-1)
EndIf
EndProcedure
 
 
OpenWindow(0, 100, 100,700,500 ,"Sierpinski triangle", #PB_Window_SystemMenu |1)
StartDrawing(WindowOutput(0))
DrawingMode(#PB_2DDrawing_Transparent )
Triangle(10,10,120,5)
StopDrawing()
 
Repeat
Until WaitWindowEvent()=#PB_Event_CloseWindow
End

[edit] Python

def sierpinski(n):
d = ["*"]
for i in xrange(n):
sp = " " * (2 ** i)
d = [sp+x+sp for x in d] + [x+" "+x for x in d]
return d
 
print "\n".join(sierpinski(4))
Or, using fold / reduce
Works with: Python version 3.x
import functools
 
def sierpinski(n):
 
def aggregate(TRIANGLE, I):
SPACE = " " * (2 ** I)
return [SPACE+X+SPACE for X in TRIANGLE] + [X+" "+X for X in TRIANGLE]
 
return functools.reduce(aggregate, range(n), ["*"])
 
print("\n".join(sierpinski(4)))

[edit] R

Based on C# but using some of R's functionality to abbreviate code where possible.

sierpinski.triangle = function(n) {
len <- 2^(n+1)
b <- c(rep(FALSE,len/2),TRUE,rep(FALSE,len/2))
for (i in 1:(len/2))
{
cat(paste(ifelse(b,"*"," "),collapse=""),"\n")
n <- rep(FALSE,len+1)
n[which(b)-1]<-TRUE
n[which(b)+1]<-xor(n[which(b)+1],TRUE)
b <- n
}
}
sierpinski.triangle(5)

Shortened to a function of one line.

sierpinski.triangle = function(n) {
c(paste(ifelse(b<<- c(rep(FALSE,2^(n+1)/2),TRUE,rep(FALSE,2^(n+1)/2)),"*"," "),collapse=""),replicate(2^n-1,paste(ifelse(b<<-xor(c(FALSE,b[1:2^(n+1)]),c(b[2:(2^(n+1)+1)],FALSE)),"*"," "),collapse="")))
}
cat(sierpinski.triangle(5),sep="\n")

[edit] Racket

 
#lang racket
(define (sierpinski n)
(if (zero? n)
'("*")
(let ([spaces (make-string (expt 2 (sub1 n)) #\space)]
[prev (sierpinski (sub1 n))])
(append (map (λ(x) (~a spaces x spaces)) prev)
(map (λ(x) (~a x " " x)) prev)))))
(for-each displayln (sierpinski 5))
 

[edit] REXX

/*REXX program draws a  Sierpinski triangle  of up to around order 10k. */
parse arg n mk . /*get the order of the triangle. */
if n=='' | n==',' then n=4 /*if none specified, assume 4. */
if mk=='' then mk='*' /*use the default of an asterisk.*/
if length(mk)==2 then mk=x2c(mk) /*MK was specified in hexadecimal*/
if length(mk)==3 then mk=d2c(mk) /*MK was specified in decimal. */
numeric digits 12000 /*this otta handle the die-hards.*/
/* [↓] the blood-'n-guts of pgm.*/
do j=0 for n*4;  !=1; z=left('',n*4-1-j) /*indent the line. */
do k=0 for j+1 /*build the line with J+1 parts*/
if !//2==0 then z=z' ' /*it's either a blank, or ··· */
else z=z mk /*it's one of them thar character*/
 !=!*(j-k)%(k+1) /*calculate a handy-dandy thingy.*/
end /*k*/ /* [↑] finished building a line.*/
say z /*display a line of the triangle.*/
end /*j*/ /* [↑] finished displaying tri. */
/*stick a fork in it, we're done.*/

output (using the default of order 4):

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

output when using the input of: 8 1e

                                ▲
                               ▲ ▲
                              ▲   ▲
                             ▲ ▲ ▲ ▲
                            ▲       ▲
                           ▲ ▲     ▲ ▲
                          ▲   ▲   ▲   ▲
                         ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲
                        ▲               ▲
                       ▲ ▲             ▲ ▲
                      ▲   ▲           ▲   ▲
                     ▲ ▲ ▲ ▲         ▲ ▲ ▲ ▲
                    ▲       ▲       ▲       ▲
                   ▲ ▲     ▲ ▲     ▲ ▲     ▲ ▲
                  ▲   ▲   ▲   ▲   ▲   ▲   ▲   ▲
                 ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲
                ▲                               ▲
               ▲ ▲                             ▲ ▲
              ▲   ▲                           ▲   ▲
             ▲ ▲ ▲ ▲                         ▲ ▲ ▲ ▲
            ▲       ▲                       ▲       ▲
           ▲ ▲     ▲ ▲                     ▲ ▲     ▲ ▲
          ▲   ▲   ▲   ▲                   ▲   ▲   ▲   ▲
         ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲                 ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲
        ▲               ▲               ▲               ▲
       ▲ ▲             ▲ ▲             ▲ ▲             ▲ ▲
      ▲   ▲           ▲   ▲           ▲   ▲           ▲   ▲
     ▲ ▲ ▲ ▲         ▲ ▲ ▲ ▲         ▲ ▲ ▲ ▲         ▲ ▲ ▲ ▲
    ▲       ▲       ▲       ▲       ▲       ▲       ▲       ▲
   ▲ ▲     ▲ ▲     ▲ ▲     ▲ ▲     ▲ ▲     ▲ ▲     ▲ ▲     ▲ ▲
  ▲   ▲   ▲   ▲   ▲   ▲   ▲   ▲   ▲   ▲   ▲   ▲   ▲   ▲   ▲   ▲
 ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲

output when using the input of: 32 db

                                                                                                                                █
                                                                                                                               █ █
                                                                                                                              █   █
                                                                                                                             █ █ █ █
                                                                                                                            █       █
                                                                                                                           █ █     █ █
                                                                                                                          █   █   █   █
                                                                                                                         █ █ █ █ █ █ █ █
                                                                                                                        █               █
                                                                                                                       █ █             █ █
                                                                                                                      █   █           █   █
                                                                                                                     █ █ █ █         █ █ █ █
                                                                                                                    █       █       █       █
                                                                                                                   █ █     █ █     █ █     █ █
                                                                                                                  █   █   █   █   █   █   █   █
                                                                                                                 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
                                                                                                                █                               █
                                                                                                               █ █                             █ █
                                                                                                              █   █                           █   █
                                                                                                             █ █ █ █                         █ █ █ █
                                                                                                            █       █                       █       █
                                                                                                           █ █     █ █                     █ █     █ █
                                                                                                          █   █   █   █                   █   █   █   █
                                                                                                         █ █ █ █ █ █ █ █                 █ █ █ █ █ █ █ █
                                                                                                        █               █               █               █
                                                                                                       █ █             █ █             █ █             █ █
                                                                                                      █   █           █   █           █   █           █   █
                                                                                                     █ █ █ █         █ █ █ █         █ █ █ █         █ █ █ █
                                                                                                    █       █       █       █       █       █       █       █
                                                                                                   █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █
                                                                                                  █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █
                                                                                                 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
                                                                                                █                                                               █
                                                                                               █ █                                                             █ █
                                                                                              █   █                                                           █   █
                                                                                             █ █ █ █                                                         █ █ █ █
                                                                                            █       █                                                       █       █
                                                                                           █ █     █ █                                                     █ █     █ █
                                                                                          █   █   █   █                                                   █   █   █   █
                                                                                         █ █ █ █ █ █ █ █                                                 █ █ █ █ █ █ █ █
                                                                                        █               █                                               █               █
                                                                                       █ █             █ █                                             █ █             █ █
                                                                                      █   █           █   █                                           █   █           █   █
                                                                                     █ █ █ █         █ █ █ █                                         █ █ █ █         █ █ █ █
                                                                                    █       █       █       █                                       █       █       █       █
                                                                                   █ █     █ █     █ █     █ █                                     █ █     █ █     █ █     █ █
                                                                                  █   █   █   █   █   █   █   █                                   █   █   █   █   █   █   █   █
                                                                                 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █                                 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
                                                                                █                               █                               █                               █
                                                                               █ █                             █ █                             █ █                             █ █
                                                                              █   █                           █   █                           █   █                           █   █
                                                                             █ █ █ █                         █ █ █ █                         █ █ █ █                         █ █ █ █
                                                                            █       █                       █       █                       █       █                       █       █
                                                                           █ █     █ █                     █ █     █ █                     █ █     █ █                     █ █     █ █
                                                                          █   █   █   █                   █   █   █   █                   █   █   █   █                   █   █   █   █
                                                                         █ █ █ █ █ █ █ █                 █ █ █ █ █ █ █ █                 █ █ █ █ █ █ █ █                 █ █ █ █ █ █ █ █
                                                                        █               █               █               █               █               █               █               █
                                                                       █ █             █ █             █ █             █ █             █ █             █ █             █ █             █ █
                                                                      █   █           █   █           █   █           █   █           █   █           █   █           █   █           █   █
                                                                     █ █ █ █         █ █ █ █         █ █ █ █         █ █ █ █         █ █ █ █         █ █ █ █         █ █ █ █         █ █ █ █
                                                                    █       █       █       █       █       █       █       █       █       █       █       █       █       █       █       █
                                                                   █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █
                                                                  █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █
                                                                 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
                                                                █                                                                                                                               █
                                                               █ █                                                                                                                             █ █
                                                              █   █                                                                                                                           █   █
                                                             █ █ █ █                                                                                                                         █ █ █ █
                                                            █       █                                                                                                                       █       █
                                                           █ █     █ █                                                                                                                     █ █     █ █
                                                          █   █   █   █                                                                                                                   █   █   █   █
                                                         █ █ █ █ █ █ █ █                                                                                                                 █ █ █ █ █ █ █ █
                                                        █               █                                                                                                               █               █
                                                       █ █             █ █                                                                                                             █ █             █ █
                                                      █   █           █   █                                                                                                           █   █           █   █
                                                     █ █ █ █         █ █ █ █                                                                                                         █ █ █ █         █ █ █ █
                                                    █       █       █       █                                                                                                       █       █       █       █
                                                   █ █     █ █     █ █     █ █                                                                                                     █ █     █ █     █ █     █ █
                                                  █   █   █   █   █   █   █   █                                                                                                   █   █   █   █   █   █   █   █
                                                 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █                                                                                                 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
                                                █                               █                                                                                               █                               █
                                               █ █                             █ █                                                                                             █ █                             █ █
                                              █   █                           █   █                                                                                           █   █                           █   █
                                             █ █ █ █                         █ █ █ █                                                                                         █ █ █ █                         █ █ █ █
                                            █       █                       █       █                                                                                       █       █                       █       █
                                           █ █     █ █                     █ █     █ █                                                                                     █ █     █ █                     █ █     █ █
                                          █   █   █   █                   █   █   █   █                                                                                   █   █   █   █                   █   █   █   █
                                         █ █ █ █ █ █ █ █                 █ █ █ █ █ █ █ █                                                                                 █ █ █ █ █ █ █ █                 █ █ █ █ █ █ █ █
                                        █               █               █               █                                                                               █               █               █               █
                                       █ █             █ █             █ █             █ █                                                                             █ █             █ █             █ █             █ █
                                      █   █           █   █           █   █           █   █                                                                           █   █           █   █           █   █           █   █
                                     █ █ █ █         █ █ █ █         █ █ █ █         █ █ █ █                                                                         █ █ █ █         █ █ █ █         █ █ █ █         █ █ █ █
                                    █       █       █       █       █       █       █       █                                                                       █       █       █       █       █       █       █       █
                                   █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █                                                                     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █
                                  █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █                                                                   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █
                                 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █                                                                 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
                                █                                                               █                                                               █                                                               █
                               █ █                                                             █ █                                                             █ █                                                             █ █
                              █   █                                                           █   █                                                           █   █                                                           █   █
                             █ █ █ █                                                         █ █ █ █                                                         █ █ █ █                                                         █ █ █ █
                            █       █                                                       █       █                                                       █       █                                                       █       █
                           █ █     █ █                                                     █ █     █ █                                                     █ █     █ █                                                     █ █     █ █
                          █   █   █   █                                                   █   █   █   █                                                   █   █   █   █                                                   █   █   █   █
                         █ █ █ █ █ █ █ █                                                 █ █ █ █ █ █ █ █                                                 █ █ █ █ █ █ █ █                                                 █ █ █ █ █ █ █ █
                        █               █                                               █               █                                               █               █                                               █               █
                       █ █             █ █                                             █ █             █ █                                             █ █             █ █                                             █ █             █ █
                      █   █           █   █                                           █   █           █   █                                           █   █           █   █                                           █   █           █   █
                     █ █ █ █         █ █ █ █                                         █ █ █ █         █ █ █ █                                         █ █ █ █         █ █ █ █                                         █ █ █ █         █ █ █ █
                    █       █       █       █                                       █       █       █       █                                       █       █       █       █                                       █       █       █       █
                   █ █     █ █     █ █     █ █                                     █ █     █ █     █ █     █ █                                     █ █     █ █     █ █     █ █                                     █ █     █ █     █ █     █ █
                  █   █   █   █   █   █   █   █                                   █   █   █   █   █   █   █   █                                   █   █   █   █   █   █   █   █                                   █   █   █   █   █   █   █   █
                 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █                                 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █                                 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █                                 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
                █                               █                               █                               █                               █                               █                               █                               █
               █ █                             █ █                             █ █                             █ █                             █ █                             █ █                             █ █                             █ █
              █   █                           █   █                           █   █                           █   █                           █   █                           █   █                           █   █                           █   █
             █ █ █ █                         █ █ █ █                         █ █ █ █                         █ █ █ █                         █ █ █ █                         █ █ █ █                         █ █ █ █                         █ █ █ █
            █       █                       █       █                       █       █                       █       █                       █       █                       █       █                       █       █                       █       █
           █ █     █ █                     █ █     █ █                     █ █     █ █                     █ █     █ █                     █ █     █ █                     █ █     █ █                     █ █     █ █                     █ █     █ █
          █   █   █   █                   █   █   █   █                   █   █   █   █                   █   █   █   █                   █   █   █   █                   █   █   █   █                   █   █   █   █                   █   █   █   █
         █ █ █ █ █ █ █ █                 █ █ █ █ █ █ █ █                 █ █ █ █ █ █ █ █                 █ █ █ █ █ █ █ █                 █ █ █ █ █ █ █ █                 █ █ █ █ █ █ █ █                 █ █ █ █ █ █ █ █                 █ █ █ █ █ █ █ █
        █               █               █               █               █               █               █               █               █               █               █               █               █               █               █               █
       █ █             █ █             █ █             █ █             █ █             █ █             █ █             █ █             █ █             █ █             █ █             █ █             █ █             █ █             █ █             █ █
      █   █           █   █           █   █           █   █           █   █           █   █           █   █           █   █           █   █           █   █           █   █           █   █           █   █           █   █           █   █           █   █
     █ █ █ █         █ █ █ █         █ █ █ █         █ █ █ █         █ █ █ █         █ █ █ █         █ █ █ █         █ █ █ █         █ █ █ █         █ █ █ █         █ █ █ █         █ █ █ █         █ █ █ █         █ █ █ █         █ █ █ █         █ █ █ █
    █       █       █       █       █       █       █       █       █       █       █       █       █       █       █       █       █       █       █       █       █       █       █       █       █       █       █       █       █       █       █       █
   █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █     █ █
  █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █   █
 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █

Output with an input of 64 was too large for this page. See Sierpinski triangle/REXX output 64

[edit] Ruby

From the command line:

ruby -le'16.times{|y|print" "*(15-y),(0..y).map{|x|~y&x>0?"  ":" *"}}'
or,
Translation of: Python
def sierpinski_triangle(n)
triangle = ["*"]
n.times do |i|
sp = " " * (2**i)
triangle = triangle.collect {|x| sp + x + sp} +
triangle.collect {|x| x + " " + x}
end
triangle
end
 
puts sierpinski_triangle(4)

Using fold / reduce (aka. inject):

def sierpinski_triangle(n)
(0...n).inject(["*"]) {|triangle, i|
space = " " * (2**i)
triangle.map {|x| space + x + space} + triangle.map {|x| x + " " + x}
}
end
 
puts sierpinski_triangle(4)

[edit] Scala

The Ruby command-line version (on Windows):

scala -e "for(y<-0 to 15){println(\" \"*(15-y)++(0 to y).map(x=>if((~y&x)>0)\"  \"else\" *\")mkString)}"

The Forth version:

def sierpinski(n: Int) {
def star(n: Long) = if ((n & 1L) == 1L) "*" else " "
def stars(n: Long): String = if (n == 0L) "" else star(n) + " " + stars(n >> 1)
def spaces(n: Int) = " " * n
((1 << n) - 1 to 0 by -1).foldLeft(1L) {
case (bitmap, remainingLines) =>
println(spaces(remainingLines) + stars(bitmap))
(bitmap << 1) ^ bitmap
}
}

The Haskell version:

def printSierpinski(n: Int) {
def sierpinski(n: Int): List[String] = {
lazy val down = sierpinski(n - 1)
lazy val space = " " * (1 << (n - 1))
n match {
case 0 => List("*")
case _ => (down map (space + _ + space)) :::
(down map (List.fill(2)(_) mkString " "))
}
}
sierpinski(n) foreach println
}

[edit] Scheme

Translation of: Haskell
(define (sierpinski n)
(for-each
(lambda (x) (display (list->string x)) (newline))
(let loop ((acc (list (list #\*))) (spaces (list #\ )) (n n))
(if (zero? n)
acc
(loop
(append
(map (lambda (x) (append spaces x spaces)) acc)
(map (lambda (x) (append x (list #\ ) x)) acc))
(append spaces spaces)
(- n 1))))))

[edit] Seed7

$ include "seed7_05.s7i";
 
const func array string: sierpinski (in integer: n) is func
result
var array string: parts is 1 times "*";
local
var integer: i is 0;
var string: space is " ";
var array string: parts2 is 0 times "";
var string: x is "";
begin
for i range 1 to n do
parts2 := 0 times "";
for x range parts do
parts2 &:= [] (space & x & space);
end for;
for x range parts do
parts2 &:= [] (x & " " & x);
end for;
parts := parts2;
space &:= space;
end for;
end func;
 
const proc: main is func
begin
writeln(join(sierpinski(4), "\n"));
end func;

[edit] Sidef

func sierpinski_triangle(n) {
var triangle = ['*'];
{ |i|
var sp = (' ' * Math.pow(2, i-1));
triangle = (triangle.map {|x| sp + x + sp} +
triangle.map {|x| x + ' ' + x});
} * n;
triangle.join("\n");
}
 
say sierpinski_triangle(4);

[edit] TI-83 BASIC

Uses Wolfram Rule 90.

PROGRAM:SIRPNSKI
:ClrHome
:Output(1,8,"^")
:{0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0}→L1
:{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}→L2
:L2→L3
:For(X,2,8,1)
:For(Y,2,17,1)
:If L1(Y-1)
:Then
:4→N
:End
:If L1(Y)
:Then
:N+2→N
:End
:If L1(Y+1)
:Then
:N+1→N
:End
:If N=1 or N=3 or N=4 or N=6
:Then
:1→L2(Y)
:Output(X,Y-1,"^")
:End
:0→N
:End
:L2→L1
:L3→L2
:End
 

[edit] Tcl

Translation of: Perl
package require Tcl 8.5
 
proc map {lambda list} {
foreach elem $list {
lappend result [apply $lambda $elem]
}
return $result
}
 
proc sierpinski_triangle n {
set down [list *]
set space " "
for {set i 1} {$i <= $n} {incr i} {
set down [concat \
[map [subst -nocommands {x {expr {"$space[set x]$space"}}}] $down] \
[map {x {expr {"$x $x"}}} $down] \
]
append space $space
}
return [join $down \n]
}
 
puts [sierpinski_triangle 4]

[edit] Unlambda

```ci``s``s`ks``s`k`s``s`kc``s``s``si`kr`k. `k.*k
`k``s``s``s``s`s`k`s``s`ksk`k``s``si`kk`k``s`kkk
`k``s`k`s``si`kk``s`kk``s``s``s``si`kk`k`s`k`s``s`ksk`k`s`k`s`k`si``si`k`ki
`k``s`k`s``si`k`ki``s`kk``s``s``s``si`kk`k`s`k`s`k`si`k`s`k`s``s`ksk``si`k`ki
`k`ki``s`k`s`k`si``s`kkk

This produces an infinite, left-justified triangle:

*
**
* *
****
*   *
**  **
* * * *
********
*       *
**      **
* *     * *
****    ****
*   *   *   *
**  **  **  **
* * * * * * * *
****************
*               *
**              **
* *             * *
****            ****
*   *           *   *
**  **          **  **
* * * *         * * * *
********        ********
*       *       *       *
**      **      **      **
* *     * *     * *     * *
****    ****    ****    ****
*   *   *   *   *   *   *   *
**  **  **  **  **  **  **  **
* * * * * * * * * * * * * * * *
********************************
*                               *
**                              **
* *                             * *
            ........

[edit] Ursala

the straightforward recursive solution

#import nat
 
triangle = ~&a^?\<<&>>! ^|RNSiDlrTSPxSxNiCK9xSx4NiCSplrTSPT/~& predecessor

the cheeky cellular automaton solution

#import std
#import nat
 
rule = -$<0,&,0,0,&,0,0,0>@rSS zipp0*ziD iota8
evolve "n" = @iNC ~&x+ rep"n" ^C\~& @h rule*+ swin3+ :/0+ --<0>
sierpinski = iota; --<&>@NS; iota; ^H/evolve@z @NS ^T/~& :/&

an example of each (converting from booleans to characters)

#show+
 
examples = mat0 ~&?(`*!,` !)*** <sierpinski3,triangle4>

output:

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

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

[edit] Vedit macro language

[edit] Iterative

Translation of: JavaScript

The macro writes the fractal into an edit buffer where it can be viewed and saved to file if required. This allows creating images larger than screen, the size is only limited by free disk space.

#3 = 16    // size (height) of the triangle
Buf_Switch(Buf_Free) // Open a new buffer for output
Ins_Char(' ', COUNT, #3*2+2) // fill first line with spaces
Ins_Newline
Line(-1) Goto_Col(#3)
Ins_Char('*', OVERWRITE) // the top of triangle
for (#10=0; #10 < #3-1; #10++) {
BOL Reg_Copy(9,1) Reg_Ins(9) // duplicate the line
#20 = '*'
for (#11 = #3-#10; #11 < #3+#10+1; #11++) {
Goto_Col(#11-1)
if (Cur_Char==Cur_Char(2)) { #21=' ' } else { #21='*' }
Ins_Char(#20, OVERWRITE)
#20 = #21
}
Ins_Char(#21, OVERWRITE)
Ins_Char('*', OVERWRITE)
}

[edit] Recursive

Translation of: BASIC

Vedit macro language does not have recursive functions, so some pushing and popping is needed to implement recursion.

#1 = 1		// x
#2 = 1 // y
#3 = 16 // length (height of the triangle / 2)
#4 = 5 // depth of recursion
 
Buf_Switch(Buf_Free) // Open a new buffer for output
Ins_Newline(#3*2) // Create as many empty lines as needed
Call("Triangle") // Draw the triangle
BOF
Return
 
:Triangle:
if (#4 == 0) {
Goto_Line(#2)
EOL Ins_Char(' ', COUNT, #1-Cur_Col+1) // add spaces if needed
Goto_Col(#1)
Ins_Char('*', OVERWRITE)
} else {
Num_Push(1,4)
#2 += #3; #3 /= 2; #4--; Call("Triangle")
Num_Pop(1,4)
Num_Push(1,4)
#1 += #3; #3 /= 2; #4--; Call("Triangle")
Num_Pop(1,4)
Num_Push(1,4)
#1 += 2*#3; #2 += #3; #3 /= 2; #4--; Call("Triangle")
Num_Pop(1,4)
}
Return

[edit] X86 Assembly

Translation of XPL0. Assemble with tasm, tlink /t

        .model  tiny
.code
.486
org 100h
start: xor ebx, ebx ;S1:= 0
mov edx, 8000h ;S2:= $8000
mov cx, 16 ;for I:= Size downto 1
tri10: mov ebx, edx ; S1:= S2
tri15: test edx, edx ; while S2#0
je tri20
mov al, '*' ; ChOut
test dl, 01h ; if S2&1 then '*' else ' '
jne tri18
mov al, ' '
tri18: int 29h
shr edx, 1 ; S2>>1
jmp tri15
tri20: mov al, 0Dh ;new line
int 29h
mov al, 0Ah
int 29h
shl ebx, 1 ;S2:= S2 xor S1<<1
xor edx, ebx
shr ebx, 2 ;S2:= S2 xor S1>>1
xor edx, ebx
loop tri10 ;next I
ret
end start

Output:

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

[edit] XPL0

code ChOut=8, CrLf=9;
def Order=4, Size=1<<Order;
int S1, S2, I;
[S1:= 0; S2:= $8000;
for I:= 0 to Size-1 do
[S1:= S2;
while S2 do
[ChOut(0, if S2&1 then ^* else ^ ); S2:= S2>>1];
CrLf(0);
S2:= S2 xor S1<<1;
S2:= S2 xor S1>>1;
];
]

Output:

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

[edit] zkl

Translation of: D
reg level = 3, d = T("*");
foreach n in ([0 .. level]){
sp := " "*(2.0).pow(n).toInt();
d = d.apply('wrap(a){ String(sp,a,sp) }).extend(
d.apply(fcn(a){ String(a," ",a) }));
}
d.concat("\n").println();
Output:
               *               
              * *              
             *   *             
            * * * *            
           *       *           
          * *     * *          
         *   *   *   *         
        * * * * * * * *        
       *               *       
      * *             * *      
     *   *           *   *     
    * * * *         * * * *    
   *       *       *       *   
  * *     * *     * *     * *  
 *   *   *   *   *   *   *   * 
* * * * * * * * * * * * * * * *
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox