How long does it take for this sequence to obtain this loop?
$begingroup$
For positive integers $m,n$, define a sequence $S_m(n)$ so that $S_m(1)=m$, $S_m(n+1)=S_m(n)^2-1$ if $S_m(n)$ is prime, and $S_m(n+1)$ is the greatest prime factor of $S_m(n)$ otherwise. It is clear that, regardless of $m$, this sequence always gets caught in the infinite loop $2,3,8,2,3,dots$, because for any prime $p$, $p^2-1=(p+1)(p-1)$ and if $pneq 2$ then the greatest prime factor of this term is at most $lceil p/2rceil<p$.
What is less clear, is the rate at which the sequence becomes stuck into that loop. If we define $t(m)$ to be the smallest integer $n$ so that $S_m(n)=2$, then how does $t(m)$ grow? By some numerical testing I've found that $t(m)<20$ for all $m<10000$, which seems to suggest a logarithmic growth speed. In addition, for any positive integer $N$, is it always true that there exists an $m$ so that $t(m)>N$? Any thoughts are appreciated!
sequences-and-series elementary-number-theory
asked Dec 20 '18 at 10:31
YiFanYiFan
4,3241627
$endgroup$
add a comment |
$begingroup$
For positive integers $m,n$, define a sequence $S_m(n)$ so that $S_m(1)=m$, $S_m(n+1)=S_m(n)^2-1$ if $S_m(n)$ is prime, and $S_m(n+1)$ is the greatest prime factor of $S_m(n)$ otherwise. It is clear that, regardless of $m$, this sequence always gets caught in the infinite loop $2,3,8,2,3,dots$, because for any prime $p$, $p^2-1=(p+1)(p-1)$ and if $pneq 2$ then the greatest prime factor of this term is at most $lceil p/2rceil<p$.
What is less clear, is the rate at which the sequence becomes stuck into that loop. If we define $t(m)$ to be the smallest integer $n$ so that $S_m(n)=2$, then how does $t(m)$ grow? By some numerical testing I've found that $t(m)<20$ for all $m<10000$, which seems to suggest a logarithmic growth speed. In addition, for any positive integer $N$, is it always true that there exists an $m$ so that $t(m)>N$? Any thoughts are appreciated!
sequences-and-series elementary-number-theory
asked Dec 20 '18 at 10:31
YiFanYiFan
4,3241627
$endgroup$
add a comment |
$begingroup$
For positive integers $m,n$, define a sequence $S_m(n)$ so that $S_m(1)=m$, $S_m(n+1)=S_m(n)^2-1$ if $S_m(n)$ is prime, and $S_m(n+1)$ is the greatest prime factor of $S_m(n)$ otherwise. It is clear that, regardless of $m$, this sequence always gets caught in the infinite loop $2,3,8,2,3,dots$, because for any prime $p$, $p^2-1=(p+1)(p-1)$ and if $pneq 2$ then the greatest prime factor of this term is at most $lceil p/2rceil<p$.
What is less clear, is the rate at which the sequence becomes stuck into that loop. If we define $t(m)$ to be the smallest integer $n$ so that $S_m(n)=2$, then how does $t(m)$ grow? By some numerical testing I've found that $t(m)<20$ for all $m<10000$, which seems to suggest a logarithmic growth speed. In addition, for any positive integer $N$, is it always true that there exists an $m$ so that $t(m)>N$? Any thoughts are appreciated!
sequences-and-series elementary-number-theory
asked Dec 20 '18 at 10:31
YiFanYiFan
4,3241627
$endgroup$
For positive integers $m,n$, define a sequence $S_m(n)$ so that $S_m(1)=m$, $S_m(n+1)=S_m(n)^2-1$ if $S_m(n)$ is prime, and $S_m(n+1)$ is the greatest prime factor of $S_m(n)$ otherwise. It is clear that, regardless of $m$, this sequence always gets caught in the infinite loop $2,3,8,2,3,dots$, because for any prime $p$, $p^2-1=(p+1)(p-1)$ and if $pneq 2$ then the greatest prime factor of this term is at most $lceil p/2rceil<p$.
What is less clear, is the rate at which the sequence becomes stuck into that loop. If we define $t(m)$ to be the smallest integer $n$ so that $S_m(n)=2$, then how does $t(m)$ grow? By some numerical testing I've found that $t(m)<20$ for all $m<10000$, which seems to suggest a logarithmic growth speed. In addition, for any positive integer $N$, is it always true that there exists an $m$ so that $t(m)>N$? Any thoughts are appreciated!
sequences-and-series elementary-number-theory
sequences-and-series elementary-number-theory
asked Dec 20 '18 at 10:31
YiFanYiFan
4,3241627
asked Dec 20 '18 at 10:31
YiFanYiFan
4,3241627
asked Dec 20 '18 at 10:31
YiFanYiFan
4,3241627
asked Dec 20 '18 at 10:31
YiFanYiFan
4,3241627
asked Dec 20 '18 at 10:31
YiFanYiFan
4,3241627
4,3241627
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Recording the following observation to get the ball rolling.
Assume that $ell>2$ is a Sophie Germain prime, in other words, a prime such that $p=2ell+1$ is also a prime. In that case
$$
(p+1)(p-1)=(2ell+2)cdot2ell=2^3cdotfrac{ell+1}2ell
$$
implying that $ell$ is the largest prime factor of $p^2-1$. So if $S_m(n)=p$ then $S_m(n+2)=ell$.
A Cunningham chain of length $k$ is a sequence of iterated Sophie Germain primes
$$p_1<p_2<p_3<cdots<p_k$$
such that $p_{i+1}=2p_i+1$ for all $i$. For example, $5<11<23<47$ is Cunningham sequence of length $4$. Iterating the argument of the previous paragraph tells us that if $S_m(n)=p_k$ for some $m,n$, then $S_m(n+2(k-1))=p_1$. This implies that if a Cunngham chain of length $k$ exists, then it takes about $2k$ steps for your sequence to come down to $p_1$.
According to the cited Wikipedia page it is an open conjucture that arbitrarily long Cunningham chains exist. In light of the above that conjecture would imply that the function $t$ is unbounded.
Of course, there is no need to have longer and longer Cunningham chains for $t$ to be unbounded. I just felt that this connection may be interesting. It is, of course, easy to show that the set of prime factors of numbers of the form $p^2-1$ is unbounded, but I couldn't see how unboundedness of $t$ would follow from such a simple fact.
answered Dec 20 '18 at 14:43
Jyrki LahtonenJyrki Lahtonen
109k13170376
$endgroup$
$begingroup$
Very interesting, thanks. I haven't thought of the connection to Cunningham chains before.
$endgroup$
– YiFan
Dec 21 '18 at 5:20
1
$begingroup$
To be honest, I'm a bit disappointed about my inability to prove that $t$ is undounded. It should (?) be possible to prove that a large enough class of primes appears as values of $S_m(3)$, inductively argue that the set of values of $S_m(2k+1)$ is not bounded for any $k$, but... no cigar.
$endgroup$
– Jyrki Lahtonen
Dec 21 '18 at 5:36
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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/3.0/"u003ecc by-sa 3.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%2fmath.stackexchange.com%2fquestions%2f3047386%2fhow-long-does-it-take-for-this-sequence-to-obtain-this-loop%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Recording the following observation to get the ball rolling.
Assume that $ell>2$ is a Sophie Germain prime, in other words, a prime such that $p=2ell+1$ is also a prime. In that case
$$
(p+1)(p-1)=(2ell+2)cdot2ell=2^3cdotfrac{ell+1}2ell
$$
implying that $ell$ is the largest prime factor of $p^2-1$. So if $S_m(n)=p$ then $S_m(n+2)=ell$.
A Cunningham chain of length $k$ is a sequence of iterated Sophie Germain primes
$$p_1<p_2<p_3<cdots<p_k$$
such that $p_{i+1}=2p_i+1$ for all $i$. For example, $5<11<23<47$ is Cunningham sequence of length $4$. Iterating the argument of the previous paragraph tells us that if $S_m(n)=p_k$ for some $m,n$, then $S_m(n+2(k-1))=p_1$. This implies that if a Cunngham chain of length $k$ exists, then it takes about $2k$ steps for your sequence to come down to $p_1$.
According to the cited Wikipedia page it is an open conjucture that arbitrarily long Cunningham chains exist. In light of the above that conjecture would imply that the function $t$ is unbounded.
Of course, there is no need to have longer and longer Cunningham chains for $t$ to be unbounded. I just felt that this connection may be interesting. It is, of course, easy to show that the set of prime factors of numbers of the form $p^2-1$ is unbounded, but I couldn't see how unboundedness of $t$ would follow from such a simple fact.
answered Dec 20 '18 at 14:43
Jyrki LahtonenJyrki Lahtonen
109k13170376
$endgroup$
$begingroup$
Very interesting, thanks. I haven't thought of the connection to Cunningham chains before.
$endgroup$
– YiFan
Dec 21 '18 at 5:20
1
$begingroup$
To be honest, I'm a bit disappointed about my inability to prove that $t$ is undounded. It should (?) be possible to prove that a large enough class of primes appears as values of $S_m(3)$, inductively argue that the set of values of $S_m(2k+1)$ is not bounded for any $k$, but... no cigar.
$endgroup$
– Jyrki Lahtonen
Dec 21 '18 at 5:36
add a comment |
$begingroup$
Recording the following observation to get the ball rolling.
Assume that $ell>2$ is a Sophie Germain prime, in other words, a prime such that $p=2ell+1$ is also a prime. In that case
$$
(p+1)(p-1)=(2ell+2)cdot2ell=2^3cdotfrac{ell+1}2ell
$$
implying that $ell$ is the largest prime factor of $p^2-1$. So if $S_m(n)=p$ then $S_m(n+2)=ell$.
A Cunningham chain of length $k$ is a sequence of iterated Sophie Germain primes
$$p_1<p_2<p_3<cdots<p_k$$
such that $p_{i+1}=2p_i+1$ for all $i$. For example, $5<11<23<47$ is Cunningham sequence of length $4$. Iterating the argument of the previous paragraph tells us that if $S_m(n)=p_k$ for some $m,n$, then $S_m(n+2(k-1))=p_1$. This implies that if a Cunngham chain of length $k$ exists, then it takes about $2k$ steps for your sequence to come down to $p_1$.
According to the cited Wikipedia page it is an open conjucture that arbitrarily long Cunningham chains exist. In light of the above that conjecture would imply that the function $t$ is unbounded.
Of course, there is no need to have longer and longer Cunningham chains for $t$ to be unbounded. I just felt that this connection may be interesting. It is, of course, easy to show that the set of prime factors of numbers of the form $p^2-1$ is unbounded, but I couldn't see how unboundedness of $t$ would follow from such a simple fact.
answered Dec 20 '18 at 14:43
Jyrki LahtonenJyrki Lahtonen
109k13170376
$endgroup$
$begingroup$
Very interesting, thanks. I haven't thought of the connection to Cunningham chains before.
$endgroup$
– YiFan
Dec 21 '18 at 5:20
1
$begingroup$
To be honest, I'm a bit disappointed about my inability to prove that $t$ is undounded. It should (?) be possible to prove that a large enough class of primes appears as values of $S_m(3)$, inductively argue that the set of values of $S_m(2k+1)$ is not bounded for any $k$, but... no cigar.
$endgroup$
– Jyrki Lahtonen
Dec 21 '18 at 5:36
add a comment |
$begingroup$
Recording the following observation to get the ball rolling.
Assume that $ell>2$ is a Sophie Germain prime, in other words, a prime such that $p=2ell+1$ is also a prime. In that case
$$
(p+1)(p-1)=(2ell+2)cdot2ell=2^3cdotfrac{ell+1}2ell
$$
implying that $ell$ is the largest prime factor of $p^2-1$. So if $S_m(n)=p$ then $S_m(n+2)=ell$.
A Cunningham chain of length $k$ is a sequence of iterated Sophie Germain primes
$$p_1<p_2<p_3<cdots<p_k$$
such that $p_{i+1}=2p_i+1$ for all $i$. For example, $5<11<23<47$ is Cunningham sequence of length $4$. Iterating the argument of the previous paragraph tells us that if $S_m(n)=p_k$ for some $m,n$, then $S_m(n+2(k-1))=p_1$. This implies that if a Cunngham chain of length $k$ exists, then it takes about $2k$ steps for your sequence to come down to $p_1$.
According to the cited Wikipedia page it is an open conjucture that arbitrarily long Cunningham chains exist. In light of the above that conjecture would imply that the function $t$ is unbounded.
Of course, there is no need to have longer and longer Cunningham chains for $t$ to be unbounded. I just felt that this connection may be interesting. It is, of course, easy to show that the set of prime factors of numbers of the form $p^2-1$ is unbounded, but I couldn't see how unboundedness of $t$ would follow from such a simple fact.
answered Dec 20 '18 at 14:43
Jyrki LahtonenJyrki Lahtonen
109k13170376
$endgroup$
Recording the following observation to get the ball rolling.
Assume that $ell>2$ is a Sophie Germain prime, in other words, a prime such that $p=2ell+1$ is also a prime. In that case
$$
(p+1)(p-1)=(2ell+2)cdot2ell=2^3cdotfrac{ell+1}2ell
$$
implying that $ell$ is the largest prime factor of $p^2-1$. So if $S_m(n)=p$ then $S_m(n+2)=ell$.
A Cunningham chain of length $k$ is a sequence of iterated Sophie Germain primes
$$p_1<p_2<p_3<cdots<p_k$$
such that $p_{i+1}=2p_i+1$ for all $i$. For example, $5<11<23<47$ is Cunningham sequence of length $4$. Iterating the argument of the previous paragraph tells us that if $S_m(n)=p_k$ for some $m,n$, then $S_m(n+2(k-1))=p_1$. This implies that if a Cunngham chain of length $k$ exists, then it takes about $2k$ steps for your sequence to come down to $p_1$.
According to the cited Wikipedia page it is an open conjucture that arbitrarily long Cunningham chains exist. In light of the above that conjecture would imply that the function $t$ is unbounded.
Of course, there is no need to have longer and longer Cunningham chains for $t$ to be unbounded. I just felt that this connection may be interesting. It is, of course, easy to show that the set of prime factors of numbers of the form $p^2-1$ is unbounded, but I couldn't see how unboundedness of $t$ would follow from such a simple fact.
answered Dec 20 '18 at 14:43
Jyrki LahtonenJyrki Lahtonen
109k13170376
answered Dec 20 '18 at 14:43
Jyrki LahtonenJyrki Lahtonen
109k13170376
answered Dec 20 '18 at 14:43
Jyrki LahtonenJyrki Lahtonen
109k13170376
answered Dec 20 '18 at 14:43
Jyrki LahtonenJyrki Lahtonen
109k13170376
109k13170376
$begingroup$
Very interesting, thanks. I haven't thought of the connection to Cunningham chains before.
$endgroup$
– YiFan
Dec 21 '18 at 5:20
1
$begingroup$
To be honest, I'm a bit disappointed about my inability to prove that $t$ is undounded. It should (?) be possible to prove that a large enough class of primes appears as values of $S_m(3)$, inductively argue that the set of values of $S_m(2k+1)$ is not bounded for any $k$, but... no cigar.
$endgroup$
– Jyrki Lahtonen
Dec 21 '18 at 5:36
add a comment |
$begingroup$
Very interesting, thanks. I haven't thought of the connection to Cunningham chains before.
$endgroup$
– YiFan
Dec 21 '18 at 5:20
1
$begingroup$
To be honest, I'm a bit disappointed about my inability to prove that $t$ is undounded. It should (?) be possible to prove that a large enough class of primes appears as values of $S_m(3)$, inductively argue that the set of values of $S_m(2k+1)$ is not bounded for any $k$, but... no cigar.
$endgroup$
– Jyrki Lahtonen
Dec 21 '18 at 5:36
$begingroup$
Very interesting, thanks. I haven't thought of the connection to Cunningham chains before.
$endgroup$
– YiFan
Dec 21 '18 at 5:20
$begingroup$
Very interesting, thanks. I haven't thought of the connection to Cunningham chains before.
$endgroup$
– YiFan
Dec 21 '18 at 5:20
1
1
$begingroup$
To be honest, I'm a bit disappointed about my inability to prove that $t$ is undounded. It should (?) be possible to prove that a large enough class of primes appears as values of $S_m(3)$, inductively argue that the set of values of $S_m(2k+1)$ is not bounded for any $k$, but... no cigar.
$endgroup$
– Jyrki Lahtonen
Dec 21 '18 at 5:36
$begingroup$
To be honest, I'm a bit disappointed about my inability to prove that $t$ is undounded. It should (?) be possible to prove that a large enough class of primes appears as values of $S_m(3)$, inductively argue that the set of values of $S_m(2k+1)$ is not bounded for any $k$, but... no cigar.
$endgroup$
– Jyrki Lahtonen
Dec 21 '18 at 5:36
add a comment |
Thanks for contributing an answer to Mathematics 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%2fmath.stackexchange.com%2fquestions%2f3047386%2fhow-long-does-it-take-for-this-sequence-to-obtain-this-loop%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
