Expanding A Tetration Expression!

This is my favorite problem personally.

$\displaystyle A(x) := \prod_{k=1}^{N}{\left(1 + f(k)x^{b^k}\right)} = 1 + a_1 x^{m_1} + a_2 x^{m_2} + \cdots$

Now what actually is happening on the LHS - $\displaystyle (1 + f(1)x^b)(1 + f(2)x^{b^2})(1 + f(3)x^{b^3}) \cdots$

Let's move our focus to what will the power of $x$ be for $a_n$ and then all we need to do is to multiply the corresponding $f(m)$ 's that it would have been made of.

One can see that $\displaystyle b + b^2 + b^3 + \cdots + b^{p-1} < b^p ; \forall b\geq 2$

So the powers of $x$ on RHS will be like

$\displaystyle b, b^2, b + b^2, b^3, b + b^3, b^2 + b^3, \cdots$

Or to say that before $x^{b^p}$ comes, all the combinations of $\displaystyle {b, b^2, b^3, b^4, \cdots, b^{p-1}}$ would have already come.

In other words, index at which $\displaystyle x^{b^p}$ comes is $\displaystyle \binom{p-1}{1} + \binom{p-1}{2} + \cdots + \binom{p-1}{p-1} + 1 = 2^{p-1}$

$\displaystyle a_{2^{p-1}} = [x^{b^p}]{A(x)}$

In fact, now one can imagine that after this index the same $p-1$ combinations will come so as to say :

$\displaystyle \large a_{2^{p-1} + 2^{p_1-1} + 2^{p_2-1} + \cdots + 2^{p_n -1}} = [\displaystyle x^{b^p + b^{p_1} + b^{p_2} + \cdots + b^{p_n}}]{A(x)}$

And since we know what all terms of LHS had had been multiplied to make up that power of $x$ , we can easily formulate :

$\displaystyle \large a_{2^{p-1} + 2^{p_1-1} + 2^{p_2-1} + \cdots + 2^{p_n -1}} = \displaystyle f(p)f(p_1)f(p_2)f(p_3) \cdots f(p_n)$

We can in fact make steps to find $a_n$ in such a polynomial :

• Step 1 : Write $n$ in binary .

• Step 2 : Note down the indices ${n_i}$ at which $1$ comes starting from right starting from $1$ st index .

• Step 3 : Multiply all the $f(n_i)$ .

$$

Now for our given problem,

$\displaystyle 2017 = (11111100001)_2$

$\displaystyle a_{2017} = z_{11} z_{10} z_9 z_8 z_7 z_6 z_1$

$\displaystyle \boxed{a_{2017} = z_8}$

Maybe you had to specify "find the minimum n".