Penney numerals

# There is a clever system for encoding complex numbers, developed by W. Penney (JACM 12 (1965) pp. 247-248). He notes that complex numbers can be represented by their "base i-1" representation, using only the digits 0 and 1. A bit more detail is given at wikipedia .

# WikiDbImage penney.gif

# Connecting the Gaussian integers in order by their representation in Penney's system produces a pretty self-similar curve closely related to the Dragon Curve. Here's a Tcl/Tk script that does it; it breaks down the integers into subranges to show the self-similarity of the curve.

 package require Tk

# We compute the powers of ( -1+i ) and keep them in the list, powers

 set y [list 1 0]
 set powers {}
 for { set i 0 } { $i < 32 } { incr i } {
     lappend powers $y
     foreach { a b } $y break
     set y [list [expr { -$a - $b }] \
                [expr { $a - $b }]]
 }

# This procedure draws a piece of the path that Penney's numbers take in the complex plane.

 proc penney { from to color } {
     variable powers
     set cmd [list .c create line]
     for { set i $from } { $i <= $to } { incr i } {
         set b 1
         set re 0
         set im 0
         foreach bit $powers {
             if { $i & $b } {
                 foreach { br bi } $bit break
                 incr re $br
                 incr im $bi
             }
             if { $b >= $i } {
                 break
             }
             incr b $b
         }
         lappend cmd [expr {128+3*$re}] [expr {108-3*$im}]
     }
     lappend cmd -fill $color
     eval $cmd
 }

# We draw four subranges of Penney's numbers, together with a little circle marking the origin of the complex plane.

 grid [canvas .c -width 240 -height 280 -bg black]
 penney 0 255 magenta
 penney 256 511 red
 penney 512 767 yellow
 penney 768 1023 green
 penney 1024 1535 cyan
 penney 1536 2047 blue
 .c create oval 126 106 130 110 -fill white

RS confirms that this code runs great (and pretty fast) on PocketPC. Thanks Kevin!