sub partitions {
  my $n = shift;
  my @partitions = 1;
  for my $i (1..$n) {
    for my $j (0..($n-2*$i), $n-$i) {
      $partitions[$i+$j] += $partitions[$j];
    }
  }
  return $partitions[$n];
}