MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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$.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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