Partition function seems odd

[bawolk]

Suppose I wish to find the number of partitions of 99 restricted to the summands 1, 5, 10, and 25. I naively try:

$ hops --prec=100 'PARTITION({1,5,10,25})'
{"hops":"PARTITION({1,5,10,25})","seq":[1,1,1,1]}

I first thought that this has to do with your use of Indet as a tool for exploration. However, even if the {1,5,10,25} represents a truncation of a possibly infinite series, any further terms would involve a degree greater than 25. So it would seem that at a minimum the function h in the where clause should use the maximum of cs instead of length cs. Implementing this yields:

$ hops --prec=100 'PARTITION({1,5,10,25})'
{"hops":"PARTITION({1,5,10,25})","seq":[1,1,1,1,2,2,2,2,2,4,4,4,4,4,6,6,6,6,6,9,9,9,9,9,13]}

Better, but there should be some way to get this series to its full precision, so I can determine the coefficient of x^99. Also note what happens if I naively use square brackets:

$ hops --prec=100 'PARTITION([1,5,10,25])'
{"hops":"PARTITION({1,5,10,25})","seq":[]}

This occurs because the square bracket series contains zeros, which causes the empty series to result. We can avoid this by filtering out the zero coefficients. Implementing that yields:

$ hops --prec=100 'PARTITION([1,5,10,25])'
{"hops":"PARTITION({1,5,10,25})","seq":[1,1,1,1,2,2,2,2,2,4,4,4,4,4,6,6,6,6,6,9,9,9,9,9,13]}

Would it make sense to use the full precision if square brackets are used, but keep the current result if curly brackets are used? I think the documentation should be improved even if the current approach is retained.

[akc]

I agree that this is an odd behavior. I don't think I've actually used the PARTITION transform beyond writing one test for it.

In general, HOPS offers an indiscriminate set of of transformations, most of which are taken from the OEIS, https://oeis.org/transforms.txt. I've been thinking of starting over; this time drawing more from the Flajolet and Sedgwick book and less from the OEIS. So if you want to propose changes don't fell that you have to preserve the current functionality.

[bawolk]

The reason I took a look at partition is that I was looking for ways to use your existing transforms to provide the functionality I needed to create the generating functions used in Analytic Combinatorics. Part of the difficulty is that the OEIS transforms sometimes ignore the zeroth coefficient. Thus PARTITION gives a series [P(1), P(2), ... ], where P(n) is the coefficient of x^n. There really should be a zeroth coefficient equal to 1. This came up when I used EULER to create the multiset functionality. I had to do a little tinkering: MSET(B) = RIGHT(EULER(LEFT(B)))

The problem is that some users might want to rely on PARTITION being identical with the OEIS version. I suppose we could warn them. Should I do a pull request to change PARTITION to yield a full precision series starting with P(0)? If you are thinking of starting over, count me in. I have lots of free time.

Also, I would like to add the functionality of pulling out a specific coefficient. We might use a new operator (#) like this:

 $ hops '1/(1-[0,1,1])'
{"hops":"1/(1-[0,1,1])","seq":[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610]}
$ hops '(1/(1-[0,1,1]))#4'
{"hops":"1/(1-[0,1,1])","seq":[5]}

I suppose we could also allow multiple coefficients to be selected:

$ hops '(1/(1-[0,1,1]))#[4, 6]'
{"hops":"1/(1-[0,1,1])","seq":[5, 13]}

Any thoughts?

[bawolk]

I see that the (#) operator won't work since it looks like # is used to denote a comment. I have implemented it with (?) instead:

$ hops '(1/(1-[0,1,1]))?[4, 6]'
{"hops":"1/(1-[0,1,1])","seq":[5, 13]}

If you just want one coefficient, you don't need brackets:

$ hops '(1/(1-[0,1,1]))?4'
{"hops":"1/(1-[0,1,1])","seq":[5]}

[akc]

Very nice. Would it perhaps make sense to allow extracting a potentially infinite number of coefficient as well. That is, if f and g are series and with coefficients of a_0, a_1, ... and b_0, b_1, ..., respectively, and the b_is are integers then the coefficients of f?g are a_(b_0), a_(b_1), ....

I like the uniformity of such an approach. E.g. one could get every 5th coefficient by f?{5*n}. A downside is that the notation for extracting a finite number of coefficients might feel less intuitive than in the case of your implementation. We would need to write (1/(1-[0,1,1]))?{4} and (1/(1-[0,1,1]))?{4, 6}.

On the other hand if we only use the initial increasing segment of (integral) coefficient in g then (1/(1-[0,1,1]))?4 and (1/(1-[0,1,1]))?[4, 6] would work too.

What do you think?

Regarding transformations. I would like to start over and it's great to hear that you have plenty of time. I wish that was true for me as well, but sadly not. (Closer to Christmas I should have more time). If you'd like to start with a proposal for transformations (it doesn't have to be large) that would be great. I'll help out as much as I can. In particular, I agree that a PARTITION function / transformation should yield a full precision series starting with P(0).

[bawolk]

Actually, infinite series are already built in, whether one uses curly brackets or square ones. So for example,

$ hops '(1/(1-[0,1,1]))?[2*n+1]'
{"hops":"(1/(1-[0,1,1]))?[2*n+1]","seq":[1,3,8,21,55,144,377]}
$ hops '(1/(1-[0,1,1]))?{2*n+1}'
{"hops":"(1/(1-[0,1,1]))?{2*n+1}","seq":[1,3,8,21,55,144,377]}

I'll submit a pull request. I'll also work up a pull request for a revised PARTITION and SEQ, PSET, MSET, and CYC, based on Sedgewick.

[akc]

Sounds great. I'm curious, will

$ hops '(1/(1-[0,1,1]))?([1,1]/[1,-2,1])'
{"hops":"(1/(1-[0,1,1]))?([1,1]/[1,-2,1])","seq":[1,3,8,21,55,144,377]}

also work?

[akc]

I see now that you've already submitted that PR, so I'll close this issue.