RotW.py

def join_string(fn):
    def fn_(*a, **k):
        return "".join(reversed(list(fn(*a, **k))))
    return fn_

@join_string
def binary_string(number, bit_count):
    for bit in xrange(bit_count):
        yield "1" if number & 1 == 1 else "0"
        number = number >> 1

def numbers_up_to_bit_count(bit_count):
    for x in xrange(1 << bit_count):
        yield x

def has_adjacent_bits(number, bit_ct):
    for bit in xrange(bit_ct - 1):
        bits = number & 3
        if bits == 3:
            return True
        number = number >> 1
    return False

def numbers_without_adjacent_bits(bit_count):
    return [n for n in numbers_up_to_bit_count(bit_count)
            if not has_adjacent_bits(n, bit_count)]

def sum_of_numbers_without_adjacent_bits(bit_count):
    return sum(1 for number in numbers_up_to_bit_count(bits)
               if not has_adjacent_bits(number, bits))

def fib(x):
    a, b = 1, 1
    for n in xrange(x):
        a, b = b, a + b
    return b

for bits in xrange(2, 7):
    print "{} has {} ({}) without adjacent 1s".format(bits, 
                                                      sum_of_numbers_without_adjacent_bits(bits),
                                                      fib(bits))
    #print "\n".join("    {} -> {}".format(n, binary_string(n, bits)) for n in numbers_without_adjacent_bits(bits))