# 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 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!

• Why was there a downvote? What have I done wrong? – Culver Kwan Aug 14 at 11:05
• I think, it will be out of reach to find out all primes in the sequence $(p_n)$, therefore I see little hope to solve $(3)$ – Peter Aug 14 at 11:17
• A very interesting question indeed. – Klangen Aug 14 at 11:23
• @CulverKwan Questions about prime numbers almost always receive at least one downvote. We will never find out why. – Peter Aug 14 at 11:27
• Also, I edited the question as I found something wrong. $1$ has no prime factor. – Culver Kwan Aug 14 at 12:07

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

• I share your feeling that $p_n$ contains all primes apart from a finite set of them (which then indeed trivially implies that $\gcd(a,b)=1$ is both necessary and sufficient condition in question 3), but it is certainly not true that this must happen with $p_2'$ already. Consider $a_1=2420$. The sequence $\{p'\}$ starts as $11, 17, 29, 43, 59$ before reaching the "all subsequent primes are included" moment. If you want a smaller example, $a_1=81$ or $a_1=600$ would do as well. – Peter Košinár Aug 20 at 1:50
• Yes, I see my error in the second half of my part 3 proof. I am curious as to if my observation holds or not, for large numbers. – Gabe Aug 21 at 20:20