16
$\begingroup$

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!

$\endgroup$
  • $\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
$\begingroup$

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

$\endgroup$
  • 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

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.