5
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ Yep, there we go. That's the key discovery. $\endgroup$ – Rand al'Thor May 27 at 12:55
  • $\begingroup$ Did you nip my proof? Well played! $\endgroup$ – El-Guest May 27 at 13:05
  • $\begingroup$ @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. $\endgroup$ – Jaap Scherphuis May 27 at 13:23
  • $\begingroup$ @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 $\endgroup$ – El-Guest May 27 at 13:27
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Ah, you beat me by 37 seconds.... $\endgroup$ – tom May 27 at 12:12
  • 4
    $\begingroup$ Which is a prime number. How suitable. $\endgroup$ – Florian F May 27 at 12:18
  • $\begingroup$ Please see my amended answer having read yours. $\endgroup$ – Weather Vane May 27 at 12:43
  • $\begingroup$ 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!! $\endgroup$ – El-Guest May 27 at 12:45
  • $\begingroup$ Yes, the easy ones $ \lt 2^{64}$. But actually, there is not always just one other prime factor. $\endgroup$ – Weather Vane May 27 at 12:46
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

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.