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!

  • $\begingroup$ Why was there a downvote? What have I done wrong? $\endgroup$ – Culver Kwan Aug 14 at 11:05
  • 3
    $\begingroup$ 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)$ $\endgroup$ – Peter Aug 14 at 11:17
  • 2
    $\begingroup$ A very interesting question indeed. $\endgroup$ – Klangen Aug 14 at 11:23
  • 8
    $\begingroup$ @CulverKwan Questions about prime numbers almost always receive at least one downvote. We will never find out why. $\endgroup$ – Peter Aug 14 at 11:27
  • 2
    $\begingroup$ Also, I edited the question as I found something wrong. $1$ has no prime factor. $\endgroup$ – 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$.

  • 1
    $\begingroup$ 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. $\endgroup$ – Peter Košinár Aug 20 at 1:50
  • $\begingroup$ 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. $\endgroup$ – Gabe Aug 21 at 20:20

Your Answer

