Let $f(x)=a_0+a_1x+a_2x^2+\dots+a_nx^n$, where $a_i\ge0$ and $a_i$ is integer.

Given $f(1)=p$ and $f(f(1))=q$, we have to find $a_0$, $a_1$, $a_2$, $a_3$, $\dots$, $a_n$, where such $f(x)$ exists. Or we have to confirm if such $f(x)$ exists or if the polynomial is ambiguous e.g. for $p=1$ and $q=2$, no such $f(x)$ exists but for $p=1$ and $q=1$, $f(x)=1$, $f(x)=x^2$ both can be solution.

I have to write a program to do that. What should be my procedure?


The conditions $f(1) = p$ and $f(p) = q$ imply the following two equations: $$ \begin{align} &\sum_{i=0}^n a_i = p, \\ &\sum_{i=0}^n a_i p^i = q. \end{align} $$ When $p < 0$ or $p$ is not an integer, there are no solutions. When $p = 0$, the first equation implies that the polynomial must be $0$ and so $q = 0$. When $p = 1$, the equations imply that $p = q$, and the first equation implies that the solutions are the polynomials $1,x,\ldots,x^n$. From now on, we assume that $p \geq 2$.

Intuitively, the polynomial minimizing $\sum_i a_i$ under the second constraint above is obtained by writing $q$ in base $p$ notation (first $n$ digits) and putting the rest as a coefficient of $a_n$. Denote this solution by $b_0,\ldots,b_n$. If $\sum_i b_i > p$ then there is no solution. If $\sum_i b_i = p$ then we have found the unique solution. From now on, suppose that $\sum_i b_i < p$; this implies that the base $p$ expansion of $q$ has length at most $n+1$.

The given equations imply more constraints. First of all, $q \geq p$. Second, since $p \equiv 1 \pmod{p-1}$, we must have $q \equiv p \pmod{p-1}$. Starting with the polynomial $g(x) = \sum_{i=0}^n b_i x^i$, we can increase $g(1)$ by applying the update $(b'_{i+1},b'_i) \gets (b_{i+1} - \alpha,b_i + p\alpha)$ (when $b_{i+1} \geq \alpha$); this increases $g(1)$ by $\alpha(p-1)$. We can apply these updates systematically, moving the mass all the way to the polynomial $q$. Since $\sum_i b_i < p \leq q$ and $q \equiv p \pmod{p-1}$, somewhere along the way we will find a (unique) polynomial satisfying both requirements above.

How do we perform this process algorithmically? We go over the indices from $b_n$ to $b_1$ in order. At each point, we subtract from $b_i$ the maximal amount $\alpha$ which keeps the invariant $g(1) \leq p$. After processing $b_1$, we should reach the desired polynomial. (We are basically looking at the base $p-1$ expansion of $p - g(1)$.)

  • $\begingroup$ If somebody is intelligent enough, every possible cases of my problem statement is solvable in this technique. $\endgroup$ – Shakib Ahmed Oct 8 '13 at 8:18

If $p=1$, then the constraints are $f(1)=1=q$ which is easily solved depending on the value of $q$. Let's now assume $p \ge 2$. Suppose that $f(x) = \sum_k a_k x^k$ is a solution. Then $q = a_0 + a_1 p + a_2 p^2 + \ldots + a_n p^n$ where $n$ is the degree of $f$ ($a_n \ne 0$).

For any $k \le n$, $a_k \le \dfrac{q}{p^k}$. This gives a bound on each coefficient.

Since $p \gt 1$, this inequation also gives a bound for the degree of $f$: $1 \le a_n \le \dfrac{q}{p^n}$ so $n \le \dfrac{\log(q)}{\log(p)}$.

This shows that there is only a finite number of candidate polynomials. You can then enumerate all possible solutions. First compute the maximum degree $n$ of $f$. Then loop over the possible degrees ($n$ to $0$). For each degree value $m$, loop over the possible values of $a_m$; for each value of $a_m$, loop over the possible values of $a_{m-1}$, and so on. Maintain the partial sums $S_k = a_m p^m + \ldots + a_k p^k$ and $R_k = a_m + \ldots + a_k$; if either of these sums exceeds $q$ or $p$ respectively, abort this branch of the tree. When you get to $k=0$, the constraints on $f$ are $S_1 + a_0 = q$ and $R_1 + a_0 = p$, so check whether $S_1 - R_1 = q - p$.

I have no idea whether this approach is practical — there may be a significantly faster algorithm exploiting divisibility more.

  • $\begingroup$ Is it n<=log(p)/log(q), wasn't it supposed to be log(q)/log(p)? $\endgroup$ – Shakib Ahmed Oct 7 '13 at 22:16

You need a polynomial such that $f(1) = p$ and $f(p) = q$. This can be done as long as $p \neq 1$, $p, q > 0$ and $\frac {q-p} {p-1} > 0$ (or $p = q = 1$). In all cases a polynomial $ax^n+b$ is enough. Here $p^{n+1} > q$. Note that no $n$ is too large.

  • $\begingroup$ What if p=15 and q=58115? f(x)=5+4x+3x^2+2x^3+x^4 $\endgroup$ – Shakib Ahmed Oct 6 '13 at 15:13
  • $\begingroup$ $f(x) = 4150x - 4135$. $\endgroup$ – Karolis Juodelė Oct 6 '13 at 15:47
  • $\begingroup$ ai>=0, read the question properly. $\endgroup$ – Shakib Ahmed Oct 6 '13 at 16:22
  • $\begingroup$ Sorry, fixed now. $f(x) = \frac{58100x^4 + 701260} {50624}$. Unless you wanted integer coefficients... $\endgroup$ – Karolis Juodelė Oct 6 '13 at 17:56
  • $\begingroup$ Well, I am so sorry, I missed to inform. I want integer too. :( or your formula is just nice :D $\endgroup$ – Shakib Ahmed Oct 6 '13 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.