#! /usr/bin/perl -w
use strict;
use Memoize;
memoize('partition_intermediate');

# This counts partitions of $n whose smallest value is at least $k
sub partition_intermediate {
  my ($n, $k) = @_;
  if ($n == $k) {
    return 1;
  }
  elsif ($n < $k) {
    return 0;
  }
  else {
    return partition_intermediate($n, $k+1) + partition_intermediate($n-$k, $k);  }
}

sub partitions {
  my $n = shift;
  return partition_intermediate($n, 1);
}

print "$_: ", partitions($_), "\n" for @ARGV;