function that counts...

[Bryan]

Jean-Michel Pichavant wrote:
> I still don't see "how many positive integers less than n have digits
> that sum up to m" makes it a "partition" though if that what prttn
> means. Surely because I miss the context.

A partition of a positive integer m is an unordered collection of
positive integers that sum to m. [1, 1, 2, 5] is a partition of 9. The
problem at issue here is not that of counting partitions.

My algorithm for our prttn separated out the 'ndsums' sub-problem:
Count d-digit ints with digits summing to m. I found a generalization
of that problem stated in the /CRC Handbook of Discrete and
Combinatorial Mathematics/ (2000 edition, section 2.1) among "counting
problems" as:

   Solutions to x_1 + ... x_n = k
   0 <= x_i <= a_i for one or more i

Alas, the handbook does not provide a formula or algorithm. It refers
to the inclusion/exclusion principle, which I did not see how to turn
into an efficient algorithm.

My recursive memoizing method for ndsums() was initially a shot in the
dark and I was surprised how well it worked. Thinking about it more, I
can argue that it is polynomial-time based on the size of the memo-
table and the work per entry. My prttn() calls ndsums() once for each
digit, so the whole thing is polynomial in the number of digits.


--
--Bryan