6
$\begingroup$

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.

  • 1
    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%)2012-02-11
  • 0
    What are the values of $p$ and $q$ you used to generate the question title?2012-02-12
  • 0
    @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.2012-02-12
  • 0
    @Greg, I think the title sequence is the one with $a_n^2+1$.2012-02-12
  • 0
    @GregMartin: I wasn't necessarily thinking of using $3$, but just some kind of growth condition. For that sequence to go to infinity, we have have a sequence of integers satisfying $P(n)>\frac{n-p}{q}$ infinitely often, and not far from this inequality "most" of the time. There are not _too_ many integers which satisfy this, (the asymptotic density is $\frac{\log q}{\log x}$) so maybe there is a way to take advantage of how $n$ is defined to get a contradiction. Nothing I tried seemed to work, and after thinking about it more, I doubt this approach will work...2012-02-12
  • 2
    Also posted to http://mathoverflow.net/questions/88282/the-sequence-a-n1-the-greatest-prime-factor-of-xa-ny/88304#88304 where a reference has been given to an affirmative answer to the first question in the case $q=1$.2012-02-13

1 Answers 1

1

Since this question has been answered on Mathoverflow by Gerry Myerson, I'm going to post a quote of the answer here for sake of removing this post from the Unanswered Questions queue.

There is a paper on this problem, Mihai Caragiu, Recurrences based on the greatest prime factor function, JP J. Algebra Number Theory Appl. 19 (2010), no. 2, 155–163, MR2796479 (2012a:11010). The summary begins,

We introduce and discuss a generalized ultimate periodicity conjecture for prime sequences $\lbrace q_n\rbrace_{n\ge0}$ in which every term $q_n$ is recursively defined as the maximum element of the finite set $\lbrace P(A_jq_{n-1}+B_j)\mid j=1,\dots,k\rbrace$, where $P(x)$ represents the greatest prime factor of $x$, while $A_j$ and $B_j$ are fixed positive integers for $1\le j\le k$.

I haven't seen the paper, just the summary in Math Reviews.

  • 0
    Maybe you should make this community wiki as it is esentially another answer verbatim?2016-08-20
  • 0
    @LaplacianFourier, ... isn't it community wiki already?2016-08-20