How many repetitions does the loop
$begingroup$
Here is the following algorithm:
for(k=2; k<n; k=k^k)
I understand that I need to check when
$n=k^k$.
But I'm stuck on $k=log_k(n)$
How many repetitions are performed by the loop?
calculus computational-complexity
edited Jan 8 at 21:04
the_candyman
8,94132145
asked Jan 8 at 19:25
shayshay
103
$endgroup$
add a comment |
$begingroup$
Here is the following algorithm:
for(k=2; k<n; k=k^k)
I understand that I need to check when
$n=k^k$.
But I'm stuck on $k=log_k(n)$
How many repetitions are performed by the loop?
calculus computational-complexity
edited Jan 8 at 21:04
the_candyman
8,94132145
asked Jan 8 at 19:25
shayshay
103
$endgroup$
$begingroup$
Have you computed what $k$ is the first few passes through the loop? It grows very rapidly. I doubt there is a nice formula, but for any reasonable $n$ it will be no more than $3$
$endgroup$
– Ross Millikan
Jan 8 at 19:44
$begingroup$
I know it grow very rapidly, but it's depends on "n", i guess that's will be log(log(n)) but i still don't know how to show it.
$endgroup$
– shay
Jan 8 at 20:35
add a comment |
$begingroup$
Here is the following algorithm:
for(k=2; k<n; k=k^k)
I understand that I need to check when
$n=k^k$.
But I'm stuck on $k=log_k(n)$
How many repetitions are performed by the loop?
calculus computational-complexity
edited Jan 8 at 21:04
the_candyman
8,94132145
asked Jan 8 at 19:25
shayshay
103
$endgroup$
Here is the following algorithm:
for(k=2; k<n; k=k^k)
I understand that I need to check when
$n=k^k$.
But I'm stuck on $k=log_k(n)$
How many repetitions are performed by the loop?
calculus computational-complexity
calculus computational-complexity
edited Jan 8 at 21:04
the_candyman
8,94132145
asked Jan 8 at 19:25
shayshay
103
edited Jan 8 at 21:04
the_candyman
8,94132145
asked Jan 8 at 19:25
shayshay
103
edited Jan 8 at 21:04
the_candyman
8,94132145
edited Jan 8 at 21:04
the_candyman
8,94132145
edited Jan 8 at 21:04
the_candyman
8,94132145
8,94132145
asked Jan 8 at 19:25
shayshay
103
asked Jan 8 at 19:25
shayshay
103
asked Jan 8 at 19:25
shayshay
103
103
$begingroup$
Have you computed what $k$ is the first few passes through the loop? It grows very rapidly. I doubt there is a nice formula, but for any reasonable $n$ it will be no more than $3$
$endgroup$
– Ross Millikan
Jan 8 at 19:44
$begingroup$
I know it grow very rapidly, but it's depends on "n", i guess that's will be log(log(n)) but i still don't know how to show it.
$endgroup$
– shay
Jan 8 at 20:35
add a comment |
$begingroup$
Have you computed what $k$ is the first few passes through the loop? It grows very rapidly. I doubt there is a nice formula, but for any reasonable $n$ it will be no more than $3$
$endgroup$
– Ross Millikan
Jan 8 at 19:44
$begingroup$
I know it grow very rapidly, but it's depends on "n", i guess that's will be log(log(n)) but i still don't know how to show it.
$endgroup$
– shay
Jan 8 at 20:35
$begingroup$
Have you computed what $k$ is the first few passes through the loop? It grows very rapidly. I doubt there is a nice formula, but for any reasonable $n$ it will be no more than $3$
$endgroup$
– Ross Millikan
Jan 8 at 19:44
$begingroup$
Have you computed what $k$ is the first few passes through the loop? It grows very rapidly. I doubt there is a nice formula, but for any reasonable $n$ it will be no more than $3$
$endgroup$
– Ross Millikan
Jan 8 at 19:44
$begingroup$
I know it grow very rapidly, but it's depends on "n", i guess that's will be log(log(n)) but i still don't know how to show it.
$endgroup$
– shay
Jan 8 at 20:35
$begingroup$
I know it grow very rapidly, but it's depends on "n", i guess that's will be log(log(n)) but i still don't know how to show it.
$endgroup$
– shay
Jan 8 at 20:35
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
After the first pass we have $k=2^2=4$ If $n$ is $3$ or $4$ there will be only one pass.
After the second pass we have $k=4^4=256$. If $4 lt n le 256$ there will be two passes.
After the third we have $k=256^{256}$, which is enormous-about $600$ digits. Only if $n$ is larger than this will there be a fourth pass.
I don't know of a nice function that can take $n$ and give back the number of passes.
answered Jan 8 at 21:02
Ross MillikanRoss Millikan
297k23198371
$endgroup$
add a comment |
$begingroup$
Notice that
$$2^2=4,4^4=256,256^{256}approx3.2317cdot10^{616}.$$
Needless to say, the next term is astronomical.
So you take little risk by saying zero to three iterations. (If $n$ is a 32 bits integer uniformly drawn, say three and you'll be right with probability $0.999999940$)
answered Jan 8 at 21:57
Yves DaoustYves Daoust
128k675227
$endgroup$
add a comment |
$begingroup$
We start with $k=2$. Since it is the first, let's call it $k_0$. We observe that:
$$k_0 = 2 = 2^1 = 2^{2^0}.$$
The next element of the sequence is:
$$k_1 = k_0^{k_0} = 2^2 = 2^{2^1}.$$
By continuing...
$$k_2 = k_3^{k_3} = (2^2)^{2^2} = 2^{2^3}.$$
$$k_3 = k_4^{k_4} = (2^{2^3})^{2^{2^3}} = 2^{2^{11}}.$$
$$k_4 = k_5^{k_5} = (2^{2^{11}})^{2^{2^{11}}} = 2^{2^{2059}}.$$
Let's introduce
$s_i = log_2 log_2 k_i$ (i.e. $k_i = 2^{2^{s_i}})$. In our case, $s_0 = 0$, $s_1 = 1$, $s_2 = 3$, $s_3=11$, $s_4 = 2059$, ...
After a deep analysis of the showed calculation, it turns out that the $s$ sequence satisfies the following:
$$s_{i+1} = s_i + 2^{s_i},$$
with $s_0 = 0.$
answered Jan 8 at 21:31
the_candymanthe_candyman
8,94132145
$endgroup$
add a comment |
$begingroup$
I looked for the number of repetitions, here is the answer I thought of:
$$
2^(2^k) = n
$$
$$
log(2^(2^k)) = log(n)
$$
$$
2^klog(2)=log(n)
$$
$$
2^k=log(n)
$$
$$
k=log(log(n))
$$
answered Jan 13 at 16:11
shayshay
103
$endgroup$
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%2f3066612%2fhow-many-repetitions-does-the-loop%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$
After the first pass we have $k=2^2=4$ If $n$ is $3$ or $4$ there will be only one pass.
After the second pass we have $k=4^4=256$. If $4 lt n le 256$ there will be two passes.
After the third we have $k=256^{256}$, which is enormous-about $600$ digits. Only if $n$ is larger than this will there be a fourth pass.
I don't know of a nice function that can take $n$ and give back the number of passes.
answered Jan 8 at 21:02
Ross MillikanRoss Millikan
297k23198371
$endgroup$
add a comment |
$begingroup$
After the first pass we have $k=2^2=4$ If $n$ is $3$ or $4$ there will be only one pass.
After the second pass we have $k=4^4=256$. If $4 lt n le 256$ there will be two passes.
After the third we have $k=256^{256}$, which is enormous-about $600$ digits. Only if $n$ is larger than this will there be a fourth pass.
I don't know of a nice function that can take $n$ and give back the number of passes.
answered Jan 8 at 21:02
Ross MillikanRoss Millikan
297k23198371
$endgroup$
add a comment |
$begingroup$
After the first pass we have $k=2^2=4$ If $n$ is $3$ or $4$ there will be only one pass.
After the second pass we have $k=4^4=256$. If $4 lt n le 256$ there will be two passes.
After the third we have $k=256^{256}$, which is enormous-about $600$ digits. Only if $n$ is larger than this will there be a fourth pass.
I don't know of a nice function that can take $n$ and give back the number of passes.
answered Jan 8 at 21:02
Ross MillikanRoss Millikan
297k23198371
$endgroup$
After the first pass we have $k=2^2=4$ If $n$ is $3$ or $4$ there will be only one pass.
After the second pass we have $k=4^4=256$. If $4 lt n le 256$ there will be two passes.
After the third we have $k=256^{256}$, which is enormous-about $600$ digits. Only if $n$ is larger than this will there be a fourth pass.
I don't know of a nice function that can take $n$ and give back the number of passes.
answered Jan 8 at 21:02
Ross MillikanRoss Millikan
297k23198371
answered Jan 8 at 21:02
Ross MillikanRoss Millikan
297k23198371
answered Jan 8 at 21:02
Ross MillikanRoss Millikan
297k23198371
answered Jan 8 at 21:02
Ross MillikanRoss Millikan
297k23198371
297k23198371
add a comment |
add a comment |
$begingroup$
Notice that
$$2^2=4,4^4=256,256^{256}approx3.2317cdot10^{616}.$$
Needless to say, the next term is astronomical.
So you take little risk by saying zero to three iterations. (If $n$ is a 32 bits integer uniformly drawn, say three and you'll be right with probability $0.999999940$)
answered Jan 8 at 21:57
Yves DaoustYves Daoust
128k675227
$endgroup$
add a comment |
$begingroup$
Notice that
$$2^2=4,4^4=256,256^{256}approx3.2317cdot10^{616}.$$
Needless to say, the next term is astronomical.
So you take little risk by saying zero to three iterations. (If $n$ is a 32 bits integer uniformly drawn, say three and you'll be right with probability $0.999999940$)
answered Jan 8 at 21:57
Yves DaoustYves Daoust
128k675227
$endgroup$
add a comment |
$begingroup$
Notice that
$$2^2=4,4^4=256,256^{256}approx3.2317cdot10^{616}.$$
Needless to say, the next term is astronomical.
So you take little risk by saying zero to three iterations. (If $n$ is a 32 bits integer uniformly drawn, say three and you'll be right with probability $0.999999940$)
answered Jan 8 at 21:57
Yves DaoustYves Daoust
128k675227
$endgroup$
Notice that
$$2^2=4,4^4=256,256^{256}approx3.2317cdot10^{616}.$$
Needless to say, the next term is astronomical.
So you take little risk by saying zero to three iterations. (If $n$ is a 32 bits integer uniformly drawn, say three and you'll be right with probability $0.999999940$)
answered Jan 8 at 21:57
Yves DaoustYves Daoust
128k675227
edited Jan 8 at 22:02
answered Jan 8 at 21:57
Yves DaoustYves Daoust
128k675227
answered Jan 8 at 21:57
Yves DaoustYves Daoust
128k675227
answered Jan 8 at 21:57
Yves DaoustYves Daoust
128k675227
128k675227
add a comment |
add a comment |
$begingroup$
We start with $k=2$. Since it is the first, let's call it $k_0$. We observe that:
$$k_0 = 2 = 2^1 = 2^{2^0}.$$
The next element of the sequence is:
$$k_1 = k_0^{k_0} = 2^2 = 2^{2^1}.$$
By continuing...
$$k_2 = k_3^{k_3} = (2^2)^{2^2} = 2^{2^3}.$$
$$k_3 = k_4^{k_4} = (2^{2^3})^{2^{2^3}} = 2^{2^{11}}.$$
$$k_4 = k_5^{k_5} = (2^{2^{11}})^{2^{2^{11}}} = 2^{2^{2059}}.$$
Let's introduce
$s_i = log_2 log_2 k_i$ (i.e. $k_i = 2^{2^{s_i}})$. In our case, $s_0 = 0$, $s_1 = 1$, $s_2 = 3$, $s_3=11$, $s_4 = 2059$, ...
After a deep analysis of the showed calculation, it turns out that the $s$ sequence satisfies the following:
$$s_{i+1} = s_i + 2^{s_i},$$
with $s_0 = 0.$
answered Jan 8 at 21:31
the_candymanthe_candyman
8,94132145
$endgroup$
add a comment |
$begingroup$
We start with $k=2$. Since it is the first, let's call it $k_0$. We observe that:
$$k_0 = 2 = 2^1 = 2^{2^0}.$$
The next element of the sequence is:
$$k_1 = k_0^{k_0} = 2^2 = 2^{2^1}.$$
By continuing...
$$k_2 = k_3^{k_3} = (2^2)^{2^2} = 2^{2^3}.$$
$$k_3 = k_4^{k_4} = (2^{2^3})^{2^{2^3}} = 2^{2^{11}}.$$
$$k_4 = k_5^{k_5} = (2^{2^{11}})^{2^{2^{11}}} = 2^{2^{2059}}.$$
Let's introduce
$s_i = log_2 log_2 k_i$ (i.e. $k_i = 2^{2^{s_i}})$. In our case, $s_0 = 0$, $s_1 = 1$, $s_2 = 3$, $s_3=11$, $s_4 = 2059$, ...
After a deep analysis of the showed calculation, it turns out that the $s$ sequence satisfies the following:
$$s_{i+1} = s_i + 2^{s_i},$$
with $s_0 = 0.$
answered Jan 8 at 21:31
the_candymanthe_candyman
8,94132145
$endgroup$
add a comment |
$begingroup$
We start with $k=2$. Since it is the first, let's call it $k_0$. We observe that:
$$k_0 = 2 = 2^1 = 2^{2^0}.$$
The next element of the sequence is:
$$k_1 = k_0^{k_0} = 2^2 = 2^{2^1}.$$
By continuing...
$$k_2 = k_3^{k_3} = (2^2)^{2^2} = 2^{2^3}.$$
$$k_3 = k_4^{k_4} = (2^{2^3})^{2^{2^3}} = 2^{2^{11}}.$$
$$k_4 = k_5^{k_5} = (2^{2^{11}})^{2^{2^{11}}} = 2^{2^{2059}}.$$
Let's introduce
$s_i = log_2 log_2 k_i$ (i.e. $k_i = 2^{2^{s_i}})$. In our case, $s_0 = 0$, $s_1 = 1$, $s_2 = 3$, $s_3=11$, $s_4 = 2059$, ...
After a deep analysis of the showed calculation, it turns out that the $s$ sequence satisfies the following:
$$s_{i+1} = s_i + 2^{s_i},$$
with $s_0 = 0.$
answered Jan 8 at 21:31
the_candymanthe_candyman
8,94132145
$endgroup$
We start with $k=2$. Since it is the first, let's call it $k_0$. We observe that:
$$k_0 = 2 = 2^1 = 2^{2^0}.$$
The next element of the sequence is:
$$k_1 = k_0^{k_0} = 2^2 = 2^{2^1}.$$
By continuing...
$$k_2 = k_3^{k_3} = (2^2)^{2^2} = 2^{2^3}.$$
$$k_3 = k_4^{k_4} = (2^{2^3})^{2^{2^3}} = 2^{2^{11}}.$$
$$k_4 = k_5^{k_5} = (2^{2^{11}})^{2^{2^{11}}} = 2^{2^{2059}}.$$
Let's introduce
$s_i = log_2 log_2 k_i$ (i.e. $k_i = 2^{2^{s_i}})$. In our case, $s_0 = 0$, $s_1 = 1$, $s_2 = 3$, $s_3=11$, $s_4 = 2059$, ...
After a deep analysis of the showed calculation, it turns out that the $s$ sequence satisfies the following:
$$s_{i+1} = s_i + 2^{s_i},$$
with $s_0 = 0.$
answered Jan 8 at 21:31
the_candymanthe_candyman
8,94132145
edited Jan 8 at 21:47
answered Jan 8 at 21:31
the_candymanthe_candyman
8,94132145
answered Jan 8 at 21:31
the_candymanthe_candyman
8,94132145
answered Jan 8 at 21:31
the_candymanthe_candyman
8,94132145
8,94132145
add a comment |
add a comment |
$begingroup$
I looked for the number of repetitions, here is the answer I thought of:
$$
2^(2^k) = n
$$
$$
log(2^(2^k)) = log(n)
$$
$$
2^klog(2)=log(n)
$$
$$
2^k=log(n)
$$
$$
k=log(log(n))
$$
answered Jan 13 at 16:11
shayshay
103
$endgroup$
add a comment |
$begingroup$
I looked for the number of repetitions, here is the answer I thought of:
$$
2^(2^k) = n
$$
$$
log(2^(2^k)) = log(n)
$$
$$
2^klog(2)=log(n)
$$
$$
2^k=log(n)
$$
$$
k=log(log(n))
$$
answered Jan 13 at 16:11
shayshay
103
$endgroup$
add a comment |
$begingroup$
I looked for the number of repetitions, here is the answer I thought of:
$$
2^(2^k) = n
$$
$$
log(2^(2^k)) = log(n)
$$
$$
2^klog(2)=log(n)
$$
$$
2^k=log(n)
$$
$$
k=log(log(n))
$$
answered Jan 13 at 16:11
shayshay
103
$endgroup$
I looked for the number of repetitions, here is the answer I thought of:
$$
2^(2^k) = n
$$
$$
log(2^(2^k)) = log(n)
$$
$$
2^klog(2)=log(n)
$$
$$
2^k=log(n)
$$
$$
k=log(log(n))
$$
answered Jan 13 at 16:11
shayshay
103
answered Jan 13 at 16:11
shayshay
103
answered Jan 13 at 16:11
shayshay
103
answered Jan 13 at 16:11
shayshay
103
103
add a comment |
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%2f3066612%2fhow-many-repetitions-does-the-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
$begingroup$
Have you computed what $k$ is the first few passes through the loop? It grows very rapidly. I doubt there is a nice formula, but for any reasonable $n$ it will be no more than $3$
$endgroup$
– Ross Millikan
Jan 8 at 19:44
$begingroup$
I know it grow very rapidly, but it's depends on "n", i guess that's will be log(log(n)) but i still don't know how to show it.
$endgroup$
– shay
Jan 8 at 20:35