#!/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";