#!/usr/bin/python # A289670 (and A284116) maps a bitstring to a new bitstring: # If it begins with "0", append "00" and remove the first three bits. # If it begins with "1", append "1101" and remove the first three bits. # That means that bits at (zero-indexed) positions 1,2,4,5,7,8,... # (non-multiples of 3) don't affect anything. # These are the Unimportant bits. # An obvious representation of a bitstring is a long integer, but one # also needs a length: there may be leading zeroes. # One needs to store only Important bits. # It's good to reverse the bitstring: one can test the _last_ bit # easily, and one can remove the _last_ important bit with a shift. # BTW, Python regards (1234L,12) and (1234,12) to be equal, even as set # elements. We needn't worry about ordinary vs. long integers. import sys # Bitstring representation: # (important bits, number of important bits, number of (all) bits mod 3) def update(bitstr): bimp = bitstr[0] bimplen = bitstr[1] blenmod3 = bitstr[2] if (bimp & 1) == 0: # prepend 00, shift 3 (shorten by one) if blenmod3 == 0: blenmod3 = 2 elif blenmod3 == 1: blenmod3 = 0 bimplen -= 1 else: blenmod3 = 1 else: # prepend reversed 1101, shift 3 (lengthen by one) if blenmod3 == 0: bimp += 3 << bimplen # _1_ 01 _1_ blenmod3 = 1 bimplen += 1 elif blenmod3 == 1: # bimp unchanged # 1 _0_ 11 blenmod3 = 2 else: bimp += 1 << bimplen # 10 _1_ 1 blenmod3 = 0 return (bimp >> 1, bimplen, blenmod3) if len(sys.argv) != 2: print "usage:", sys.argv[0], "length" sys.exit(1) size = int(sys.argv[1]) sizemod3 = size % 3 important = (size+2) / 3 toEmptySet = set([(0,0,0)]) toEmptyQuan = 1 # zero always maps to empty for bits in range(1, 1 << important): reachedSet = set() bitstr = (bits, important, sizemod3) while True: if bitstr in reachedSet: break # found a loop, not the empty bitstring if bitstr in toEmptySet: toEmptySet = toEmptySet.union(reachedSet) toEmptyQuan += 1 break reachedSet.add(bitstr) bitstr = update(bitstr) # print bits, "reached", bitstr print size, toEmptyQuan << (size - important) # multiply by 2^(number-of-unimportant-bits) --- end of program ---