Why did this prime-sequence puzzle not work?
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{
margin-bottom:0;
}
.everyonelovesstackoverflow{position:absolute;height:1px;width:1px;opacity:0;top:0;left:0;pointer-events:none;}
$begingroup$
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?
mathematics puzzle-creation number-theory
$endgroup$
add a comment
|
$begingroup$
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?
mathematics puzzle-creation number-theory
$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
add a comment
|
$begingroup$
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?
mathematics puzzle-creation number-theory
$endgroup$
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?
mathematics puzzle-creation number-theory
mathematics puzzle-creation number-theory
asked May 27 at 12:00
Rand al'ThorRand al'Thor
76.5k15 gold badges252 silver badges505 bronze badges
76.5k15 gold badges252 silver badges505 bronze badges
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
add a comment
|
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
2
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
$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
add a comment
|
4 Answers
4
active
oldest
votes
$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 = 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.
$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
add a comment
|
$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
|
show 3 more comments
$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$
add a comment
|
$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$
add a comment
|
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "559"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/4.0/"u003ecc by-sa 4.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f84415%2fwhy-did-this-prime-sequence-puzzle-not-work%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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 = 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.
$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
add a comment
|
$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 = 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.
$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
add a comment
|
$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 = 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.
$endgroup$
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.
edited May 27 at 13:24
answered May 27 at 12:54
Jaap ScherphuisJaap Scherphuis
19.4k1 gold badge34 silver badges84 bronze badges
19.4k1 gold badge34 silver badges84 bronze badges
$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
add a comment
|
$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
$begingroup$
Yep, there we go. That's the key discovery.
$endgroup$
– Rand al'Thor
May 27 at 12:55
$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$
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$
@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
$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
add a comment
|
$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
|
show 3 more comments
$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
|
show 3 more comments
$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$
$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$
edited May 27 at 13:04
answered May 27 at 12:10
El-GuestEl-Guest
26.4k3 gold badges63 silver badges109 bronze badges
26.4k3 gold badges63 silver badges109 bronze badges
$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
|
show 3 more comments
$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
$begingroup$
Ah, you beat me by 37 seconds....
$endgroup$
– tom
May 27 at 12:12
$begingroup$
Ah, you beat me by 37 seconds....
$endgroup$
– tom
May 27 at 12:12
4
4
$begingroup$
Which is a prime number. How suitable.
$endgroup$
– Florian F
May 27 at 12:18
$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$
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$
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
$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
|
show 3 more comments
$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$
add a comment
|
$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$
add a comment
|
$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$
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
answered May 27 at 12:10
tomtom
2,1481 gold badge7 silver badges30 bronze badges
2,1481 gold badge7 silver badges30 bronze badges
add a comment
|
add a comment
|
$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$
add a comment
|
$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$
add a comment
|
$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$
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$.
edited May 27 at 12:49
answered May 27 at 12:10
Weather VaneWeather Vane
6,4061 gold badge4 silver badges26 bronze badges
6,4061 gold badge4 silver badges26 bronze badges
add a comment
|
add a comment
|
Thanks for contributing an answer to Puzzling Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f84415%2fwhy-did-this-prime-sequence-puzzle-not-work%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
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