Half Sierpinski

anarchy golf

Half Sierpinski 終了。結局、ゴルフ的最良解に到ることはできなかった。Top Player たちの答えを見てみると、ただの、AND だった。ちょっとおどろき。よく、こんなの思いつくなぁ。
ただ、答えが分かって Wikipedia の Sierpinski triangle を見直してみると、確かにそんな記述がある。Construction 項目の下のほうの説明に、

bitwise AND - The 2D AND function, z=AND(x,y) can also also produce a white on black right angled Sierpinski triangle if all pixels of which z=0 are white, and all other values of z are black.

とある。この項目は事前に見ていたが、『ぁあ？なんで AND が？』と、よく言わんとしていることが分からなかった。でも、答えが分かってみると、まさに AND 関数が Sierpinski Triangle を生成するということなんだね。

(0..15).each{x->
  (0..15).each{y->
    print x&y?' ':'#'
  }
  println''
}

とやると(上記は Groovy の例)

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

↑こんな出力が得られる。うぁ、まんまだ。Wikipedia の記事はこういうことを言っていたんだ。(でも、Wikipedia の bitwise AND の次にある bitwise XOR の項目は何が言いたいんだかやっぱり分からない。)
AND がこんなパターンを生成するなんて面白いね。
さて、私が答えに使ったのは、

V(n)=V(n-1)^2*V(n-1)

という漸化式。要するに、ある項を 2 倍して XOR を取ると次の項が得られるというものだ。1 からはじめると、3, 5, 15, 17 ... という数列が得られ、各項の 2 進数表示が、やはり、Sierpinski Triangle のパターンを生成する。
それから、もうひとつ気づいたものとして、2^32-1 (つまり 2 進数で 1 が 32 個並んだ数)の約数を並べると、それらの約数の 2 進数表示がやはり Sierpinski Triangle になる。簡単のために bit 数の少ない、255 を例に取るとその約数は、

255: 11111111   (LSB <--> MSB)
 85: 1010101
 51: 110011
 17: 10001
 15: 1111
  5: 101
  3: 11
  1: 1

↑となる。それから、以前の日記に書いた Pascal Triangle との関係。

  • Sierpinski Triangle
  • 2 次元 AND 関数
  • V=V^2*V の漸化式の各項の 2 進数表示
  • 2^32-1 の約数の集合の 2 進数表示
  • Pascal Triangle の偶数を白、奇数を黒にしたもの

なんで、この一見関係ないようなものがみな同じ性質を示すんだろうね。面白いな。