#!/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 ---