use Memoize;
memoize 'int_partitions';
## number of integer partitions of $N with smallest part $min
sub int_partitions {
my ($N, $min) = @_;
$min = 1 if not defined $min;
## only one way to split up 0
return 1 if $N == 0;
## the smallest item in the partition can be between $min .. $N
## and after we fix it, we need to partition the remaining
## $N-$_, into pieces that must all be >= $_
my $total = 0;
for ($min .. $N) {
$total += int_partitions($N-$_, $_);
}
return $total;
}
print int_partitions(shift), $/;