8
$\begingroup$

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$.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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) $\endgroup$
    – Eric Naslund
    Feb 12, 2012 at 15:51
  • $\begingroup$ It has 2 votes to undelete at m.se, where only 3 are needed. $\endgroup$
    – Gerry Myerson
    Feb 12, 2012 at 22:31
  • $\begingroup$ The first question is an open in general, and proved true when x divides y. Source: scribd.com/fullscreen/17073697 $\endgroup$
    – LLLLL
    Feb 13, 2012 at 14:12
  • $\begingroup$ 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). $\endgroup$
    – Gerry Myerson
    Feb 13, 2012 at 23:04

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Feb 13, 2012 at 17:04
  • $\begingroup$ 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 $\endgroup$
    – joro
    Feb 14, 2012 at 6:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.