Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

I denote by $\operatorname{ GPF}(n)$ the greatest prime factor of $n$, eg. $\operatorname{ GPF}(17)=17$, $\operatorname{ GPF}(18)=3$.

Is there a way to prove that the sequence $a_{n+1}=\operatorname{ GPF}(qa_n+p)$, eventually enter a cycle for all initial values of positive integers $q,a_0,p>1$?

Which my simulations seem to indicate - although the sequence $a_{n+1}=\operatorname{ GPF}(a_n^2+1)$ with $a_0=2$ appears to run off into infinity.

share|cite|improve this question
For $q=1$, you can do this because at least one of $a_n$, $a_{n+1}$ and $a_{n+2}$ is divisible by $3$ when $p\neq 3$. This means that the sequence will be cut by at least a factor of $\frac{1}{3}$ on at least every $3$ elements, so that it is bounded. Hence it cycles. Likely a proof of your statement will be based on this form of growth argument. Also, from this we have a good heuristic for why $a_n^2+1$ might not work; it grows too quickly, and there are not enough numbers $n$ with $P(n)\leq \sqrt{n}$ (only about 30%) – Eric Naslund Feb 11 '12 at 17:33
What are the values of $p$ and $q$ you used to generate the question title? – Greg Martin Feb 12 '12 at 9:15
@EricNaslund: if each $qa_n+p$ were prime, then $a_{n+3}$ is more than $q^3$ times as large as $a_n$, so a single factor of $1/3$ won't force the sequence to be bounded. Anyway, getting that factor of 3 depends on the constants: if $q=2$ and $p=5$ and $a_0\equiv 1\pmod 3$, then $qa_0+p$ remains $1\pmod 3$, and in principal we could never get a multiple of 3. – Greg Martin Feb 12 '12 at 9:18
@Greg, I think the title sequence is the one with $a_n^2+1$. – Gerry Myerson Feb 12 '12 at 9:47
Also posted to… where a reference has been given to an affirmative answer to the first question in the case $q=1$. – Gerry Myerson Feb 13 '12 at 23:06

Your Answer


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

Browse other questions tagged or ask your own question.