Try this. It's correct at levels 1, 2, & 3, and Ithink it is correct for all levels, but it gets harder to discern.

I found this really tough to get right, whether through recursion or iteration. I'd given up and moved on before the pattern dawned on me. I think a mathematician may be able to reduce this to a formula, maybe involving some kind of polynomial, but it's beyond my abilities.

#! perl -slw
use strict;

$|++;

our $DEPTH ||= 3;

sub f{
    use integer;
    my( $x, $y, $depth ) = @_;
    my $bsize = 4**( $depth-1 );
    {
        if( $x == $y ) {
            return $depth;
        }
        elsif( $x/4 == $y/4 ) {
            return $depth-1;
        }
        elsif( $x/$bsize == $y/$bsize ) {
            $x %= 4;
            $y %= 4;
            --$depth;
            redo;
        }
        else {
            $x %= $bsize;
            $y %= $bsize;
            --$depth;
            redo;
        }
    }
}

for my $depth ( $DEPTH ) {
    for my $y ( 0 .. 4**$depth-1 ) {
        my $c = 0;
        for my $x ( 0 .. 4 ** $depth -1 ) {
            printf +( ( ++$c % 4 ) == 0 ? " %2d " : " %2d" ),
                f( $x, $y, $depth );
        }
        print +( $y % 4 ) == 3 ? "\n" : '';
    }
    print '';
}

__END__
[download]