How does this algorithm that multiplies $(1 + x)(1 + x^2)(1 + x^3)(1 + x^4)...$ work?

Question

To multiply polynomials (using a computer) you presented that polynomial as a list or array where the value of a position corresponds to the coefficient of that variable and the index of the position corresponds to the power of that variable.

For example $1+0x+x^2+0x^3+5x^4$ will be represented as $[1, 0, 1, 0, 5]$ and so on.

In a particular case, I had to build an algorithm that multiplies the following:

$(1 + x)(1 + x^2)(1 + x^3)(1 + x^4)...$

I use a function that uses a nested for loop to multiply two polynomials and I call that function on each of the terms in the above expression using another for loop.

That ends up giving a time-complexity of $O(n^3)$ to the algorithm.

However, I saw an algorithm that does the same thing in the time-complexity of $O(n^2)$ and I am not sure if it is specific to the

$(1 + x)(1 + x^2)(1 + x^3)(1 + x^4)...$

series or not?

For example, if I want to find up to the $x^{10}$ then I create an array with $10 + 1$ zeros which starts with $1$.

Then if I repeatedly shift the array by $1$ to the right and add it to itself I get the answer:

[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

   [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

--------------------------------------------

[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]

      [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]

--------------------------------------------

[1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]

         [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]

--------------------------------------------

[1, 1, 1, 2, 1, 1, 1, 0, 0, 0, 0]

            [1, 1, 1, 2, 1, 1, 1, 0, 0, 0, 0]

--------------------------------------------

[1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1]

This translates to:

$1 + x^1 + x^2 + 2x^3 + 2x^4 + 2x^5 + 2x^6 + 2x^7 + x^8 + x^9 + x^{10}$

I see the mechanism, but how exactly does this work? And is it specific to this series?

(For the record, I googled this a lot but to be honest, I do not know how to put it in words exactly.)

Answer 1

Well, if you are interested in finding the coefficient for infinite products as there in your question title $$\prod_{k\ge1}(1+x^k) = (1+x)(1+x^2)(1+x^3)(1+x^4)....$$ then this is the generating function for something very interesting thing coming from number theory or should I say Theory of Partitions of Integers

$$\sum_{n\ge0}q(n)x^n = \prod_{k\ge1}(1+x^k)$$ Where $q(n)$ you can find from $\text{Integer sequences: }A000009$

As commented by @dxiv $\color{blue}{p_k(x) = p_{k-1} + x^kp_{k-1}}$

import numpy as np
def p(k):
    if k == 1:
        return np.array([1, 1])
    else:
        q = p(k-1)
        return add(q, np.append(np.zeros(k, int), q))

    
def add(u, v):
    u = np.append(u, np.zeros(len(v)- len(u), int))
    return np.add(u, v)
print(p(int(input())))