# Asymptotics on prime divisors

Somewhat inspired from the Zsigmondy's theorem is my question. Suppose Let $a_{1}> a_{2}> \cdots > a_{k}$ be nonzero integers, with $k \geq 2$. Let $a(n) : = a_{1}^{n}+\cdots+a_{k}^{n}$ for $n \geq 0$. Let $h(x)$ be the number of primes $\leq x$ which divide at least one $a(n)$. Can someone give me some asymptotics on $h(x)$? My guess is $\mathcal{O}(\log x)$ or $\Omega(\log x)$ but that's just guessing. Can someone verify or disprove it? Thanks.

-
When $k = 2$, we have that $p$ divides some $a(n)$ if and only if $a_{1}/a_{2}$ has even order in $\mathbb{F}_{p}^{\times}$. This will occur for a positive proportion of primes, and hence your conjecture is false. (For example, Hasse showed that if $a_{1} = 2$ and $a_{2} = 1$, then $h(x) \sim \frac{17}{24} \pi(x)$. The ''typical case'' is $h(x) \sim \frac{2}{3} \pi(x)$, though.) The case $k > 2$ is less clear to me. – Jeremy Rouse Aug 25 '14 at 13:24
I forgot to put this in my answer, so will leave it as a comment. You mention Zsigmondy's theorem. It is certainly a very interesting question to ask if all but finitely many $a(n)$ have a primitive prime divisor. I don't know the answer. But since your sequence is not a divisibility sequence, it's behavior may be somewhat different from the Zsigmondy-type results for classical and elliptic divisibility sequences. – Joe Silverman Aug 25 '14 at 15:47

Here is a guess. Let's say some $a_j$ (say $a_1$ for concreteness) is such that a positive proportion of the primes have it as a primitive root (that's not much of a restriction particularly for $k$ big enough). Let's concentrate on one of those primes $p$. For each $n$ we can write $-(a_2^n+\cdots+a_k^n) \equiv a_1^{\beta(n)} \pmod p$. We can expect that $\beta$ is essentially a random bijection of the integers modulo $p-1$ and in that case $\beta$ will have a fixed point with positive probability. This leads me to believe that $h(x) \gg x/\log x$ always.
A quick calculation gives that 69% of the primes up to 30000 divide $3^n+2^n+1$ for some $n$.
An undergraduate here did a project with me this summer and compiled a bunch of data on the support of sequences $\{a^n+b^n-1\}$, where the support of a sequence is the set of primes that divides at least one term. For $2^n+3^n-1$, he got results very much like Felipe Voloch's; the density appears to be around 69%. He also was emboldened to conjecture that Support($\{a^n+b^n-1\}$) always has a positive density for (say) $|a|>|b|>1$. He also looked at the average size of the support for $(a,b)$ in a box. If you want to send me an email (you can get my email address on my homepage, which is listed on my MO user page), I can put you in touch with him.