I really liked Keith Lynch's set of related problems:

Subject: [math-fun] Finding a polynomial from an integer sequence From: "Keith F. Lynch" <kfl@KeithLynch.net> Date: 10/27/18, 3:56 PM

To: math-fun@mailman.xmission.com

I was wondering how many strings there are of length n, with no instances of 4 consecutive identical letters, in a b-letter alphabet. If you generalize to prohibiting *r* consecutive identical letters, this can be calculated in O(n * r) time, i.e. quickly. Here's the pattern of the algorithm I used:

For n = 1, r = 4, there are b strings like "c". For n = 2, r = 4, there are b * (b - 1) strings like cd. # (b - 1) ways to pick a different letter. b * 1 strings like cc # one way to pick the same letter. total: b^2 For n = 3, r = 4, b^2 * (b - 1) strings like cde or cce -- e not repeated (b * (b - 1)) * 1 strings like cdd -- d repeated twice b * 1 * 1 strings like ccc -- c repeated three times total: b^3 For n = 4, r = 4, there's a possibility of a repeat-of-four so we get b^3 * (b - 1) strings like cdef, ccdf, cddf, or cccf (b^2 * (b - 1)) * 1 strings like cdeeor ccee (b * (b - 1)) * 1 * 1 strings like cddd zero strings like cccc -- that's not allowed. total: b^4 - b "And so forth" up to strings of length n. For each level you need to remember: [how many end in (just one copy of) a new digit, how many end in two copies of the same digit, how many end in three copies of the same digit] I confirmed your results for the total numbers of allowed strings. I confirmed your sequences of numbers keeping n and r constant and varying b. I confirmed the polynomials you got from those sequences.

So, can anyone think of a better way to come up with polynomials from those sequences, or from sequences in general? Thanks. My favorite way to remember how to fit a polynomial to a sequence of N numbers (or any set of N (x, y) points without repeats of x) is this:

0) If there's only one point, the polynomial is a constant. Else, 1) Fit polynomial L(x) to points 1 .. N-1 2) Fit polynomial R(x) to points 2 .. N 3) Linearly interpolate between L and R: P(x) = ((N - x) * L(x) + (x - 1) * R(x)) / N The rationale is that L and R each cover one end point, and they both go through all the points in between. So interpolating between them (correctly) gives a curve that hits all the points. The algorithm is a nasty recursive O(2^N) if you don't optimize by saving some results, but O(N^3) if you do.

Another issue is that there's no guarantee that the polynomial is even correct. All I really know is that it will reproduce the terms I counted. Of course the more identical differences I get, the more confident I am. For instance for b=9, I counted the first 25 terms, so I actually got 16 copies of 362880. Yes. What I did is calculate the polynomial with n + 1 numbers in the sequence, then with 2n + 2 numbers, and checked that it was the same polynomial. It always was. neither of them constitutes a proof that the polynomial is correct. Or that*any* polynomial is correct-- who says that, except for the first few values of n where it's obvious, the sequence is a polynomial series at all? I looked at my algorithm and asked, "Is there a reason to expect that's a polynomial in b?" Hmm, b is always just a number that goes into the calculations, but it never changes the pattern of the calculations. No loop ranges or IF statements depend on b. Also, there's nothing but multiplying and adding going on.

So, instead of b being a specific number, can I set up an analogous process where all the intermediate values and results are replaced by polynomials (as they are in the examples I work through above)? I was calculating with a Python function, n_strings(n, r, b). Looking at that code, how would I calculate the polynomial in b for a given n and r? Hm, well, I also had a Python class for polynomials. So I set b = a polynomial object, B(b) = 1 * b + 0. Then I plugged that B into my Python function. And it returns the correct polynomial for the answer! The first time I tried it! With no change to the function itself! It's always a kick when code you wrote, instead of digging in its heels resisting change, is out in front anticipating where you're going next. Here are some results of n_strings(n, 4, B) for various n. The polynomial coefficients are shown in the opposite of the usual order, from b^0 through b^n): n = 1 : UniPoly([0, 1]) , order 1 n = 2 : UniPoly([0, 0, 1]) , order 2 n = 3 : UniPoly([0, 0, 0, 1]) , order 3 n = 4 : UniPoly([0, -1, 0, 0, 1]) , order 4 (These up to here duplicate the examples I worked through above.) n = 5 : UniPoly([0, 1, -2, 0, 0, 1]) , order 5 n = 6 : UniPoly([0, 0, 2, -3, 0, 0, 1]) , order 6 n = 7 : UniPoly([0, 0, 0, 3, -4, 0, 0, 1]) , order 7 n = 8 : UniPoly([0, -1, 1, 0, 4, -5, 0, 0, 1]) , order 8 n = 9 : UniPoly([0, 1, -4, 3, 0, 5, -6, 0, 0, 1]) , order 9 n = 10 : UniPoly([0, 0, 3, -9, 6, 0, 6, -7, 0, 0, 1]) , order 10 n = 11 : UniPoly([0, 0, 0, 6, -16, 10, 0, 7, -8, 0, 0, 1]) , order 11 ... Related to n_strings() is a function n_strings_segregated() that returns the r - 1 results for whether the last letter is repeated 1, 2 ... r - 1 times. That also returns polynomials if b is a polynomial. Their sum is the polynomial for the total number of strings, but it might be interesting to look at the patterns of their coefficients, for instance: n_strings(6, 4, B): UniPoly([0, -1, 3, -2, 0, -1, 1]) UniPoly([0, 1, -1, 0, -1, 1]) UniPoly([0, 0, 0, -1, 1]) total: UniPoly([0, 0, 2, -3, 0, 0, 1]) n_strings(16, 4, B): UniPoly([0, 0, 0, -10, 50, -90, 70, -48, 92, -100, 36, -11, 23, -12, 0, -1, 1]) UniPoly([0, 0, -4, 22, -42, 34, -31, 70, -77, 28, -10, 21, -11, 0, -1, 1]) UniPoly([0, -1, 7, -15, 13, -19, 51, -57, 21, -9, 19, -10, 0, -1, 1]) total: UniPoly([0, -1, 3, -3, 21, -75, 90, -35, 36, -81, 45, 0, 12, -13, 0, 0, 1]) --Steve