An interesting algorithm about prime numbers that I thought today

I thought up the following algorithm today:

Choose $a_1\in\mathbb{Z}^+\setminus\{1\}$. Then let $a_{n+1}=a_n+p_n$, where $p_n$ is the largest prime factor of $a_n$.

The algorithm is easy, but I have the following questions:

$1)$ Is the sequence $\{p_n\}$ monotonically increasing?

$2)$ Are there infinitely many primes in the sequence $\{p_n\}$?

$3)$ Find all $a,b\in\mathbb Z^+$ such that there are infinitely many primes of the form $ak+b$ where $k$ is a nonnegative integer in the sequence $\{p_n\}$.

I thought up a solution for $1)$ and $2)$, as follows:

$1)$Assume the contrary, i.e. $p_n>p_{n+1}$ for some $n$.

As $p_n|a_n$, $p_n|a_n+p_n\iff p_n|a_{n+1}$. So $p_n\le p_{n+1}$. A contradiction rises.

$2)$ Yes.

Assume the contrary, there are finitely many primes in the sequence $\{p_n\}$.

Then as $\{p_n\}$ is monotonically increasing, So there exist an $m$ such that $\forall i\ge m, p_i=p_m$. So $a_i=a_m+(i-m)p_m$. Also, we let the smallest prime larger than $p_m$ be $p$. But as $(p, p_m)=1$, $\exists i<p+m$ such that $p|a_i$. A contradiction rises.

I think the above solutions seems correct, but can you help to verify?

Also, can someone help me to do $3)$?

Any help is appreciated!

Solution 1:

1) Depending on your definition of monotonically increasing, being $p_{n} > p_{n-1}$ or $p_{n} ≥ p_{n-1}$. The first case is easily disprovable, just pick $a_{n} = 2$, and $p_{1}$ and $p_{2}$ are both 2. For the second case, since $p_{n}|a_{n} \rightarrow p_{n}|a_{n} + p_{n} \rightarrow p_{n}|a_{n+1}$, so $p_{n+1}$ is at least $p_{n}$. So depending on your definition, your solution to part 1 is right or wrong. Considering I did it the same way you did, I would say you are correct.

2) Following what we have proven in part one, we just need to prove that $p_{n}$ isn't a constant eventually. One way to prove this is to assume $p_{n}$ is constant and prove that it must increase no matter the size of $p_{n}$. Call the sequence $r_{n} = \frac{a_{k+n}}{p_{k}}$ where $r_{n}$ ends when a new value of p arises (or doesn't, but we are proving that it does). $r_{n+1} = r_{n} + 1$ since $a_{k+n} + p_{k} = a_{k+n+1}$. So as long as $\{r_{n}\}$ continues, it will eventually reach a prime after $p_{k}$, proving that the sequence is infinite.

3) Considering that proving infinite primes of the form 11k+2 exist, for example, is already a hard mathematical problem, doing it for infinite cases seems quite out of our reach. Maybe someone on Math.SE can find a solution but I can only give a hypothesis, which is that any pair (a, b) works as long as gcd(b, a) = 1. Call a new sequence $p'_n$, which is just the distinct terms in $p_n$. I have made an interesting observation however, I ran a few trials with maybe 10 or so different starting $a_{1}$, and n = 10,000, and I can prove that $p'_{2}$ to $p'_{n}$ are all consecutive primes.

Split it up into two cases: (a) $a_{1} = p'_{1} * k$, where k is less than the next consecutive prime after $p'_{1}$. Then, $a_{2} = p'_{1} * (k+1)$, etc. and eventually $p'_{2}$ is the consecutive prime after $p'_1$. Call $a'_n$ to be the corresponding term in $\{p'_n\}$. Therefore, $a'_2 = p'_1*p'_2$. This can be extended to n, since $\frac{a'_n}{p'_n} = p'_{n-1} < {p'_n}$, $p'_{n+1}$ is the consecutive prime after $p'_n$.

(b) k is greater than the next consecutive prime after $p'_1$. Then, $p'_2$ is the next prime after k, and yet again, $\frac{a'_n}{p'_n} = p'_{n-1} < {p'_n}$, so by the same idea as case (a), $p'_{n+1}$ must be the consecutive prime after $p'_n$.

Hopefully someone can help you with part 3, considering all arbitrarily large primes are in $p_n$.