Draw the Devil's Staircase
J (73 68 58 41 39 38 35 34 characters)

After thinking about the problem for some time, I found an entirely different way to generate the Devil's Staircase pattern. The old answer including its explanation has been removed, you can look into the revisions of this answer to figure out how it was.

This answer returns an array of blanks and sharps, representing the devil's staircase.

' #'{~1(]|.@=@#~[:,3^q:)2}.@i.@^&gt;:


Here is the answer split into its two parts in explicit notation:

f =: 3 : '|. = (, 3 ^ 1 q: y) # y'
g =: 3 : '(f }. i. 2 ^ &gt;: y) { '' #'''


Explanation

The approach is a bit different, so observe and be amazed.


&gt;: 3 – three incremented, that is,

4

2 ^ &gt;: 3 – two to the power of three incremented, that is,

16

i. 2 ^ &gt;: 3 – the first 2 ^ &gt;: 3 integers, that is,

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

}. i. 2 ^ 4 – the first 2 ^ &gt;: 3 integers, beheaded, that is,

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15


Let's call this sequence s; we enter f now.
1 q: s – the exponents of 2 in the prime decomposition of each item of s. In general, x q: y yields a table of the exponents for the first x primes in the prime decomposition of y. This yields:

0
1
0
2
0
1
0
3
0
1
0
2
0
1
0

3 ^ 1 q: s – three to the power of these exponents, that is,

 1
 3
 1
 9
 1
 3
 1
27
 1
 3
 1
 9
 1
 3
 1

, 3 ^ 1 q: s – the ravel (that is, the argument with it's structure collapsed into a vector) of the previous result. This is needed because q: introduces an unwanted trailing axis. This yields

 1 3 1 9 1 3 1 27 1 3 1 9 1 3 1

(, 3 ^ 1 q: s) # s – each item of s replicated as often as the corresponding item in the previous result, that is,

1 2 2 2 3 4 4 4 4 4 4 4 4 4 5 6 6 6 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 10 10 10 11 12 12 12 12 12 12 12 12 12 13 14 14 14 15

= (, 3 ^ 1 q: s) # s – the self classification of the previous result, this is, a matrix where each row represents one of the unique items of the argument, each column represents the corresponding item of the argument and each cell represents whether the items of row and column are equal, that is,

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

|. = (, 3 ^ 1 q: s) # s – the previous result flipped along the vertical axis.
(|. = (, 3 ^ 1 q: s) # s) { ' #' – the items of the previous result used as indices into the array ' #', so 0 is replaced by &nbsp; and 1 is replaced by #, that is,

                                                                #
                                                             ### 
                                                            #    
                                                   #########     
                                                  #              
                                               ###               
                                              #                  
                   ###########################                   
                  #                                              
               ###                                               
              #                                                  
     #########                                                   
    #                                                            
 ###                                                             
#      


the result we want.