Cyclically Permutable Codewords

cpc.rb

codewords = []

class Integer
  def rotate_left(bits, width = bit_width)
    bits %= width
    (self << bits | self >> (width - bits)) & ((1 << width) - 1)
  end
end

(2**8).times do |candidate|
  valid_candidate_p = true
  8.times do |bits|
    rotated_candidate = candidate.rotate_left(bits, 8)
    valid_candidate_p = false if codewords.include?(rotated_candidate)
  end
  codewords << candidate if valid_candidate_p
end

p codewords
puts codewords.length

#=> [0, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 37, 39, 43, 45, 47, 51, 53, 55, 59, 61, 63, 85, 87, 91, 95, 111, 119, 127, 255]
#=> 36

cpc2.rb

BITS = 8

class Integer
  def rotate_left(bits, width = bit_width)
    bits %= width
    (self << bits | self >> (width - bits)) & ((1 << width) - 1)
  end
end

candidates = (0...(2**BITS)).to_a

(2**BITS).times do |candidate|
  next if candidates[candidate].nil?
  (1...BITS).each do |bits|
    candidates[candidate.rotate_left(bits, BITS)] = nil
  end
end

codewords = candidates.compact

p codewords
puts codewords.length

#=> [1, 3, 5, 7, 9, 11, 13, 15, 19, 21, 23, 25, 27, 29, 31, 37, 39, 43, 45, 47, 53, 55, 59, 61, 63, 87, 91, 95, 111, 127]
#=> 30