import math


def optimal_hash_length(num_sequences, max_shift=0, target_occupancy=0.5,
                        num_choices=4):
  """Calculate the shortest hash length such that random collisions are rare.

  Args:
    num_sequences: integer number of distinct sequences to partition.
    max_shift: optional integer giving the maximum number of positional shifts
      to consider when partitioning.
    target_occupancy: float indicating the maximum acceptable average number of
      randomly chosen sequences that would appear in the same hash bucket by
      chance.
    num_choices: optional integer giving the number of valid sequence elements.
      Default value is 4, corresponding to the four base pairs in DNA.

  Returns:
    Integer giving the optimal hash length.
  """
  return int(math.ceil(math.log(float(num_sequences * (max_shift + 1))
                                / target_occupancy)
                       / math.log(num_choices)))