Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $\operatorname{ GPF}(n)$ be 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}(xa_n+y)$, eventually enter a cycle for all positive integers $x,a_0,y>0$?

Is there any set of positive integers $x,a_0,y>0$ such that $a_{n+1}=\operatorname{ GPF}(xa_n+y)\operatorname{ LPF}(xa_n+y)$ diverges?

Where $\operatorname{ LPF}(n)\geq2$ is the least prime factor of $n$.

share|improve this question
This question was on math stack exchange for about 22 hours, but received no answers: math.stackexchange.com/questions/108178/… (Link requires 10k+ reputation on MSE) –  Eric Naslund Feb 12 '12 at 15:51
It has 2 votes to undelete at m.se, where only 3 are needed. –  Gerry Myerson Feb 12 '12 at 22:31
The first question is an open in general, and proved true when x divides y. Source: scribd.com/fullscreen/17073697 –  LLLLL Feb 13 '12 at 14:12
The scridb page just has the assertion, and the reference. The proof is in Mihai Caragiu and Lisa Scheckelhoff, The greatest prime factor and related sequences, JP J. Algebra Number Theory Appl. 6 (2006), no. 2, 403–409, MR2283947 (2007h:11017). –  Gerry Myerson Feb 13 '12 at 23:04
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
add comment

Not a full answer, but one can construct arbitrary long increasing $a_n$.

Since the primes contain arbitrary long arithmetic progressions, one can construct arbitrary long increasing $a_n$ - set $a_0$ to the first prime in the progression, $x=1$ and $y$ the difference of the progression.

So $a_n = \operatorname{GPF}(a_0 + n y)$ and for $n$ term prime AP $a_n$ is an increasing sequence of primes.

share|improve this answer
Another open problem is regarding Cunningham chains, which involve generating primes using 2p+1 as the iterate. It would be of interest to me if one could find x > 1 and y that produce longer chains than the known chains and progressions (22 if memory serves). Gerhard "Ask Me About System Design" Paseman, 2012.02.13 –  Gerhard Paseman Feb 13 '12 at 17:04
Gerhard, web search showed that the longest prime AP is 26 and the Cunningham chain (of second kind 2p-1) is 17. For the AP a distributed project was used - Primegrid, so CPU time spent might have influenced the records: en.wikipedia.org/wiki/Primes_in_arithmetic_progression –  joro Feb 14 '12 at 6:30
add comment

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.