  Given $k, \ell \in {\bf N}^+$, let $x_{i,j}$ be, for $1 \le i \le k$ and $0
\le j \le \ell$, some fixed integers, and define, for every $n \in {\bf N}^+$,
$s_n := \sum_{i=1}^k \prod_{j=0}^\ell x_{i,j}^{n^j}$. We prove that the
following are equivalent:
  (a) There are a real $\theta > 1$ and infinitely many indices $n$ for which
the number of distinct prime factors of $s_n$ is greater than the
super-logarithm of $n$ to base $\theta$.
  (b) There do not exist non-zero integers $a_0,b_0,\ldots,a_\ell,b_\ell $ such
that $s_{2n}=\prod_{i=0}^\ell a_i^{(2n)^i}$ and $s_{2n-1}=\prod_{i=0}^\ell
b_i^{(2n-1)^i}$ for all $n$.
  We will give two different proofs of this result, one based on a theorem of
Evertse (yielding, for a fixed finite set of primes $\mathcal S$, an effective
bound on the number of non-degenerate solutions of an $\mathcal S$-unit
equation in $k$ variables over the rationals) and the other using only
elementary methods.
  As a corollary, we find that, for fixed $c_1, x_1, \ldots,c_k, x_k \in
\mathbf N^+$, the number of distinct prime factors of $c_1 x_1^n+\cdots+c_k
x_k^n$ is bounded, as $n$ ranges over $\mathbf N^+$, if and only if
$x_1=\cdots=x_k$.

Number Theory