#!/usr/bin/perl
use strict;
use warnings;
use PDL;
use PDL::NiceSlice;
# Compute the partition function P(n,k) using the recurrence
# relation: P(n,k) = P(n-1,k-1) + P(n-k,k)
# Use this to solve the challenge Q(667,10).
# Q(667,10) = P(667 - 45, 10)
# Note: The 45 comes from (k)(k-1)/2, the sum of (0..k-1).
my $kmax = 10;
my $nmax = 667 - 45;
# Final results for unique partitions would be created by
# adding (0..9) to the plain partition results, so restrict
# my maximum extry to 91.
my $entrymax = 100 - 9;
my ($n, $k, %triangle);
sub shiftpdl {
my ($pdl_a) = @_;
my $pdl_b = rotate($pdl_a,1)->copy;
$pdl_b(0) .= 0;
return $pdl_b;
}
# Initialize corner of the triangle.
my $p1 = zeroes $entrymax;
$p1(0) .= 1; # Single item with a max entry of one.
$triangle{1,1} = $p1;
# Use the recurrence relation to populate the triangle,
# but accumulate for each maximum number separately so
# we can shift off and eliminate cases that would take
# our maximum entry over 100.
for $n (2..$nmax) {
for $k (1..$kmax) {
my $psum = zeroes $entrymax;
if (exists $triangle{$n-1,$k-1}) {
# New entries for this case are created by tacking
# on a one to each result, so the maximum is unchanged.
$psum += $triangle{$n-1,$k-1};
}
if (exists $triangle{$n-$k, $k}) {
# New entries for this case are created by adding
# a one to each entry, so shift all counts up one place.
$psum += shiftpdl($triangle{$n-$k, $k});
}
$triangle{$n,$k} = $psum;
}
}
my $sum = sumover $triangle{$nmax,$kmax};
print "Total unique partitions C(677,10) on {1..100} is ",$sum,"\n";