Hcfyk

While attacking a recent puzzle (whose solution ended up being entirely different from what I was trying), I was inspired to create a number-sequence puzzle with a sequence $(p_n)$ of primes where the secret rule is

$p_{n+1}$ is defined as the lowest prime factor of the number $2^{p_n}+1$.

Unfortunately, I couldn't turn this into a reasonable puzzle. So I'm posting a meta-puzzle about it instead: can you see why this wouldn't make a good puzzle? Specifically, why couldn't I generate a good sequence to put in the question?

Theorem: The number $2^n+1$ is divisible by $3$ for any odd number $n$.
Proof: Set $n=2k+1$. Then modulo $3$ we have $$2^n+1 = 2^{2k+1}+1 = 2cdot 4^k+1 equiv 2cdot1^k+1 equiv 0 mod 3$$

which proves the theorem.


Since $2^n+1$ is odd for $n>0$, its lowest factor will be an odd prime. The sequence therefore will become 3 at the second step, and then remain $3$ afterwards.

$p_{n+1}$ is defined as the lowest prime factor of the number $2^{p_n}+1$.

Let’s try something:

Let $p_0 = 2$. Then $p_1$ is the lowest prime factor of $2^2 + 1 = 5$, so 5. Then $p_2$ is the lowest prime factor of $2^5 +!1 = 33$, so 3. Then $p_3$ is the lowest prime factor of $2^3 + 1 = 9$....which is 3 again! Looks like this sequence has an infinite repetition and converges to 3...

The question is,

Is this true for any $p_0$? The fact of the matter is that we have a countable set of $p_n$, because the number of $p_n$ must be less than the number of integers $2^x + 1$ there are — and this is one-to-one with the natural numbers $mathbb{N}$. It seems logical that at some point in the sequence of $p_n$, you’ll find a number divisible by 3. To avoid this, you’d essentially need to find a series of primes — quasi-Mersenne — where each continuing $2^{p_n} + 1$ is also prime. I don’t think that such a sequence exists...

Sample starting points:

$p_0 = 2$. 2, 5, 3, 3, 3, ...

(My favourite) $p_0 = 3$. 3, 3, 3, 3, 3, ...
$p_0 = 5$. 5, 3, 3, 3, 3, ...
$p_0 = 7$. 7, 3, 3, 3, 3, ... (because of 129)
$p_0 = 11$. 11, 3, 3, 3, 3, ... (because of 2049)....

Hmm....

Does every $p_0 > 2$ converge to 3 within one step? @WeatherVane found that this is at least the case for $3 leq p_0 leq 61$. This is essentially saying for prime $p$, does $3 | 2^p + 1$? Further, for any odd natural number 2m+1, does $3 | 2^{2m+1} + 1$? Let’s see...this is true iff $3 | 2^{2m+1} - 2 = 2( 2^{2m} - 1)$ iff $3 | 2^{2m} - 1$ iff $3 | 2^{2m} - 4$.... commences rambling...

Let’s use

Induction. We seem to have exhaustively proved base cases above. Then, assume that for some odd integer $n = 2m + 1$, $3 | 2^n + 1$. Then consider $p$ = 2m + 3, the next odd integer. Does $3 | 2^p + 1 = 2^{2m+3} + 1 = 4(2^{2m+1}) + 1$? Well, if $3 | 2^n + 1 = 2^{2m+1} + 1$, then $3 | 4(2^{2m+1} + 1)$. So $3 | 4(2^{2m+1}) + 4$. It must therefore also divide 3 less than that, and so $3 | 4(2^{2m+1}) + 1 = 2^{2m+3} + 1 = 2^p + 1$. We have therefore shown that the inductive hypothesis does indeed imply the inductive conclusion. By induction, therefore, $3|2^n+1$ for any positive odd integer $n$.

It naturally follows that

Any starting prime number greater than 2 is a positive odd integer, and so for any $p_0 > 2$, we must have $p_n = 3 forall n in mathbb{N}$. Since we have shown that $p_0 = 2$ converges to 3 within 2 steps, for any prime $p_0$, $p_n = 3 forall n geq 2$. This is why there is no sequence (not even the hypothetical prime ladder postulated above) which is suitable for puzzling, because every prime sequence (without restriction) converges to 3 infinitely. $square$

I think

It looks as if you would get stuck at the number 3

because

often 3 is going to be the lowest prime factor and $2^3+1=9$ which again gives 3

Unsure... partial

Because some $2^{x} + 1$ are prime numbers: no factors.

For example $x = 8$

Edit:

The above wasn't well thought, because $8$ cannot be a lowest factor.


But from @El-Guest's answer, I found that


For every prime $3 le x le 61$, $2^{x} + 1$ is divisible by $3$.