# Why did this prime-sequence puzzle not work?

While attacking a recent puzzle (whose solution ended up being entirely different from what I was trying), I was inspired to create a 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?

• It was great to see the teamwork on this one, as people inched closer to the full realisation/solution in successive answers :-) – Rand al'Thor May 27 at 12:57

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 = 2\cdot 4^k+1 \equiv 2\cdot1^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.

• Yep, there we go. That's the key discovery. – Rand al'Thor May 27 at 12:55
• Did you nip my proof? Well played! – El-Guest May 27 at 13:05
• @El-Guest When I started writing my proof, I don't think you had cottoned on to the fact that the factor 3 occurs at all odd exponents, but by the time I submitted you had and were working on a proof yourself. – Jaap Scherphuis May 27 at 13:23
• @JaapScherphuis I would’ve beaten you if I wasn’t so hell-bent on using induction haha! Well done on the modular arithmetic, your proof is much cleaner than mine. +1 – El-Guest May 27 at 13:27

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

• Ah, you beat me by 37 seconds.... – tom May 27 at 12:12
• Which is a prime number. How suitable. – Florian F May 27 at 12:18
• Did you just throw it into a computer? Thanks for the computation — good to see that the hypothesis appears correct so far, at least @WeatherVane! Thanks!! – El-Guest May 27 at 12:45
• Yes, the easy ones $\lt 2^{64}$. But actually, there is not always just one other prime factor. – Weather Vane May 27 at 12:46

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