Method to test if a number is a perfect power?Detecting perfect squares faster than by extracting square rooteffective way to get the integer sequence A181392 from oeisA rarely mentioned fact about perfect powersHow many numbers such $n$ are there that $n<100,lfloorsqrtn rfloor mid n$Check perfect squareness by modulo division against multiple basesFor what pair of integers $(a,b)$ is $3^a + 7^b$ a perfect square.Do there exist any positive integers $n$ such that $lfloore^nrfloor$ is a perfect power? What is the probability that one exists?finding perfect power factors of an integerProve that the sequence contains a perfect square for any natural number $m $ in the domain of $f$ .Counting Perfect Powers
Is the destination of a commercial flight important for the pilot?
I'm in charge of equipment buying but no one's ever happy with what I choose. How to fix this?
How does buying out courses with grant money work?
Is this version of a gravity generator feasible?
Avoiding estate tax by giving multiple gifts
How to safely derail a train during transit?
How easy is it to start Magic from scratch?
What is the opposite of 'gravitas'?
How to be diplomatic in refusing to write code that breaches the privacy of our users
Why Were Madagascar and New Zealand Discovered So Late?
What is the difference between "behavior" and "behaviour"?
What does "I’d sit this one out, Cap," imply or mean in the context?
What can we do to stop prior company from asking us questions?
Is `x >> pure y` equivalent to `liftM (const y) x`
What is the best translation for "slot" in the context of multiplayer video games?
Did Dumbledore lie to Harry about how long he had James Potter's invisibility cloak when he was examining it? If so, why?
Anatomically Correct Strange Women In Ponds Distributing Swords
What Brexit proposals are on the table in the indicative votes on the 27th of March 2019?
Opposite of a diet
Short story about space worker geeks who zone out by 'listening' to radiation from stars
Implement the Thanos sorting algorithm
Do all network devices need to make routing decisions, regardless of communication across networks or within a network?
Integer addition + constant, is it a group?
CREATE opcode: what does it really do?
Method to test if a number is a perfect power?
Detecting perfect squares faster than by extracting square rooteffective way to get the integer sequence A181392 from oeisA rarely mentioned fact about perfect powersHow many numbers such $n$ are there that $n<100,lfloorsqrtn rfloor mid n$Check perfect squareness by modulo division against multiple basesFor what pair of integers $(a,b)$ is $3^a + 7^b$ a perfect square.Do there exist any positive integers $n$ such that $lfloore^nrfloor$ is a perfect power? What is the probability that one exists?finding perfect power factors of an integerProve that the sequence contains a perfect square for any natural number $m $ in the domain of $f$ .Counting Perfect Powers
$begingroup$
Is there a general method for testing numbers to see if they are perfect $n$th powers?
For example, suppose that I did not know that $121$ was a perfect square. A naive test in a code might be to see if
$$lfloorsqrt121rfloor=sqrt121$$
But I imagine there are much more efficient ways of doing this (if I'm working with numbers with many digits).
number-theory perfect-powers
$endgroup$
|
show 1 more comment
$begingroup$
Is there a general method for testing numbers to see if they are perfect $n$th powers?
For example, suppose that I did not know that $121$ was a perfect square. A naive test in a code might be to see if
$$lfloorsqrt121rfloor=sqrt121$$
But I imagine there are much more efficient ways of doing this (if I'm working with numbers with many digits).
number-theory perfect-powers
$endgroup$
1
$begingroup$
One very cheap, necessary condition is that $x^2pmod 4equiv 0,1$.
$endgroup$
– Alex R.
1 hour ago
$begingroup$
Are you given numbers $k$ and $n$ and asked to check whether $k$ is an $n$-th power? Or are you given just $k$ and asked to check whether $k$ is a perfect power?
$endgroup$
– Servaes
1 hour ago
$begingroup$
@Servaes, I was considering the first case, where I know both k and n and trying to see if $k = a^n,$ a a positive integer.
$endgroup$
– D.B.
1 hour ago
$begingroup$
Wait, @Alex R. Looking at your first comment, what about $x^2 = 40 = 0 (mod 4)$. Yet, $40$ is not a perfect square.
$endgroup$
– D.B.
1 hour ago
2
$begingroup$
@D.B.: Hence it's a necessary condition: if $x^2$ is a perfect square, then $x^2equiv 0,1pmod4$. The other direction gives: if $yequiv 2,3pmod4$, then $y$ cannot be a perfect square.
$endgroup$
– Alex R.
1 hour ago
|
show 1 more comment
$begingroup$
Is there a general method for testing numbers to see if they are perfect $n$th powers?
For example, suppose that I did not know that $121$ was a perfect square. A naive test in a code might be to see if
$$lfloorsqrt121rfloor=sqrt121$$
But I imagine there are much more efficient ways of doing this (if I'm working with numbers with many digits).
number-theory perfect-powers
$endgroup$
Is there a general method for testing numbers to see if they are perfect $n$th powers?
For example, suppose that I did not know that $121$ was a perfect square. A naive test in a code might be to see if
$$lfloorsqrt121rfloor=sqrt121$$
But I imagine there are much more efficient ways of doing this (if I'm working with numbers with many digits).
number-theory perfect-powers
number-theory perfect-powers
edited 1 hour ago
Chase Ryan Taylor
4,45021531
4,45021531
asked 1 hour ago
D.B.D.B.
1,29518
1,29518
1
$begingroup$
One very cheap, necessary condition is that $x^2pmod 4equiv 0,1$.
$endgroup$
– Alex R.
1 hour ago
$begingroup$
Are you given numbers $k$ and $n$ and asked to check whether $k$ is an $n$-th power? Or are you given just $k$ and asked to check whether $k$ is a perfect power?
$endgroup$
– Servaes
1 hour ago
$begingroup$
@Servaes, I was considering the first case, where I know both k and n and trying to see if $k = a^n,$ a a positive integer.
$endgroup$
– D.B.
1 hour ago
$begingroup$
Wait, @Alex R. Looking at your first comment, what about $x^2 = 40 = 0 (mod 4)$. Yet, $40$ is not a perfect square.
$endgroup$
– D.B.
1 hour ago
2
$begingroup$
@D.B.: Hence it's a necessary condition: if $x^2$ is a perfect square, then $x^2equiv 0,1pmod4$. The other direction gives: if $yequiv 2,3pmod4$, then $y$ cannot be a perfect square.
$endgroup$
– Alex R.
1 hour ago
|
show 1 more comment
1
$begingroup$
One very cheap, necessary condition is that $x^2pmod 4equiv 0,1$.
$endgroup$
– Alex R.
1 hour ago
$begingroup$
Are you given numbers $k$ and $n$ and asked to check whether $k$ is an $n$-th power? Or are you given just $k$ and asked to check whether $k$ is a perfect power?
$endgroup$
– Servaes
1 hour ago
$begingroup$
@Servaes, I was considering the first case, where I know both k and n and trying to see if $k = a^n,$ a a positive integer.
$endgroup$
– D.B.
1 hour ago
$begingroup$
Wait, @Alex R. Looking at your first comment, what about $x^2 = 40 = 0 (mod 4)$. Yet, $40$ is not a perfect square.
$endgroup$
– D.B.
1 hour ago
2
$begingroup$
@D.B.: Hence it's a necessary condition: if $x^2$ is a perfect square, then $x^2equiv 0,1pmod4$. The other direction gives: if $yequiv 2,3pmod4$, then $y$ cannot be a perfect square.
$endgroup$
– Alex R.
1 hour ago
1
1
$begingroup$
One very cheap, necessary condition is that $x^2pmod 4equiv 0,1$.
$endgroup$
– Alex R.
1 hour ago
$begingroup$
One very cheap, necessary condition is that $x^2pmod 4equiv 0,1$.
$endgroup$
– Alex R.
1 hour ago
$begingroup$
Are you given numbers $k$ and $n$ and asked to check whether $k$ is an $n$-th power? Or are you given just $k$ and asked to check whether $k$ is a perfect power?
$endgroup$
– Servaes
1 hour ago
$begingroup$
Are you given numbers $k$ and $n$ and asked to check whether $k$ is an $n$-th power? Or are you given just $k$ and asked to check whether $k$ is a perfect power?
$endgroup$
– Servaes
1 hour ago
$begingroup$
@Servaes, I was considering the first case, where I know both k and n and trying to see if $k = a^n,$ a a positive integer.
$endgroup$
– D.B.
1 hour ago
$begingroup$
@Servaes, I was considering the first case, where I know both k and n and trying to see if $k = a^n,$ a a positive integer.
$endgroup$
– D.B.
1 hour ago
$begingroup$
Wait, @Alex R. Looking at your first comment, what about $x^2 = 40 = 0 (mod 4)$. Yet, $40$ is not a perfect square.
$endgroup$
– D.B.
1 hour ago
$begingroup$
Wait, @Alex R. Looking at your first comment, what about $x^2 = 40 = 0 (mod 4)$. Yet, $40$ is not a perfect square.
$endgroup$
– D.B.
1 hour ago
2
2
$begingroup$
@D.B.: Hence it's a necessary condition: if $x^2$ is a perfect square, then $x^2equiv 0,1pmod4$. The other direction gives: if $yequiv 2,3pmod4$, then $y$ cannot be a perfect square.
$endgroup$
– Alex R.
1 hour ago
$begingroup$
@D.B.: Hence it's a necessary condition: if $x^2$ is a perfect square, then $x^2equiv 0,1pmod4$. The other direction gives: if $yequiv 2,3pmod4$, then $y$ cannot be a perfect square.
$endgroup$
– Alex R.
1 hour ago
|
show 1 more comment
5 Answers
5
active
oldest
votes
$begingroup$
See Detecting perfect powers in essentially linear time - Daniel J. Bernstein:
https://cr.yp.to/papers/powers-ams.pdf
$endgroup$
add a comment |
$begingroup$
My suggestion on a computer is to run a root finder.
Given a value $y$, one way is to hard-code the first couple and then use an integer-valued binary search starting with $y/2$, which is logarithmic in $y$ and thus linear (since input takes $ln y$.
You can also write down the Newton's method recurrence and see if it converges to an integer or not, should become clear after the first couple of steps, once the error becomes small enough.
$endgroup$
$begingroup$
I don't think it's linear, given that you need to square the proposed number at every split.
$endgroup$
– Alex R.
1 hour ago
add a comment |
$begingroup$
In the specific case where you already know not only the number being checked but also the power, as the question's comment by the OP to Servaes states, then you have something like
$$k = a^n tag1labeleq1$$
where $k$ and $n$ are known integers, but with $a$ being an unknown value to check whether or not it's an integer. In this case, taking natural logarithms of both sides (you could use any base, but I suspect that implementation wise $e$ will likely at least be the fastest one, if not also the most accurate) gives
$$ln(k) = nln(a) ; Rightarrow ; ln(a) = fracln(k)n ; Rightarrow ; a = e^fracln(k)n tag2labeleq2$$
On a computer, this will give a floating point value that would be, even for large values of $k$, relatively close to the correct value of $a$.
You can now use any number of algorithms to relatively quickly & easily determine $a$ if it's an integer, or show it's not an integer. For example, you can start with the integer part obtained in eqrefeq2, call it $a_1$, to determine $k_1$. If $k_1$ is not correct, then if it's less than $k$, check $a_2 = a_1 + 1$, else check $a_2 = a_1 - 1$, and call the new result $k_2$. If $k_2$ is still not correct, add or subtract the integer amount (making sure it's at least 1) of $left|frack -k_2k_1 - k_2right|$ to $a_2$ to get a new $a_1$ value to check. Then repeat these steps as many times as needed. In almost all cases, I believe it should take very loops to find the correct value. However, note you should also include checks in case there is no such integer $a$, with this usually being seen when one integer value gives a lower result & the next higher gives a higher result (or higher result & next lower integer gives a lower result).
$endgroup$
add a comment |
$begingroup$
There are many powerful codes that factorize a number to its prime factors in a non-polynomial time (for more information you can refer to Integer Factorization on Wikipedia) . Once an integer was factorized as follows$$n=p_1^alpha_1times p_2^alpha_2timescdots times p_m^alpha_m$$then by defining $d=gcd(alpha_1,alpha_2,cdots ,alpha_m)$ we can say that $n$ is a full $d$-th power.
$endgroup$
$begingroup$
not sure about efficient, I believe it's an NP-complete problem. But surely checking if it is a perfect square would be doable more efficiently that doing the full prime factorization?!
$endgroup$
– gt6989b
1 hour ago
2
$begingroup$
For algorithms, "efficiently and fast" usually means being both deterministic and polynomial time in the length of the input; there is no known polynomial time deterministic algorithm for factoring integers, so I would absolutely quibble with your use of "efficiently and fast".
$endgroup$
– Arturo Magidin
1 hour ago
$begingroup$
This is orders-of-magnitude slower than just computing the square-root even by classical methods.
$endgroup$
– Alex R.
1 hour ago
$begingroup$
I was going to suggest that if you factorize $n>1$ as you have shown, with all of the $p_i$ distinct and all of the $alpha_i>0$, then $n$ is a perfect power if and only if all of the $alpha_i$ are equal.
$endgroup$
– MPW
1 hour ago
$begingroup$
I mean the most efficient that is possible so far
$endgroup$
– Mostafa Ayaz
1 hour ago
|
show 5 more comments
$begingroup$
It is at least possible to do this in polynomial time. Assume $n$ is a $k$-bit number and you want to find positive integers $a$ and $b$ such that $$a^b=ntag1$$ or prove that such numbers don't exists.
We have $$n<2^k$$ because $n$ is a $k$-bit number and so $$blt k$$
We can simply check for all possible $b$ if there is an $a$ such that $(1)$ holds. For given $b$ we can try to find $a$ by bisection. This bisection checks $O(log n)=O(k)$ different $a$. A check is the calculation of $a^b$. This can be achieved by multiplying powers of $a$ by $a$. These powers of $a$ are smaller than $n$. So we multiply $k$-bit numbers at most $b(lt k)$ times. A multiplication of two $k$-bit numbers needs $O(k^2)$ time. So all in all the algorithm needs $O(k^2)$ multiplications o $k$-bit numbers, which means $O(k^4)$ time.
$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%2f3165146%2fmethod-to-test-if-a-number-is-a-perfect-power%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
See Detecting perfect powers in essentially linear time - Daniel J. Bernstein:
https://cr.yp.to/papers/powers-ams.pdf
$endgroup$
add a comment |
$begingroup$
See Detecting perfect powers in essentially linear time - Daniel J. Bernstein:
https://cr.yp.to/papers/powers-ams.pdf
$endgroup$
add a comment |
$begingroup$
See Detecting perfect powers in essentially linear time - Daniel J. Bernstein:
https://cr.yp.to/papers/powers-ams.pdf
$endgroup$
See Detecting perfect powers in essentially linear time - Daniel J. Bernstein:
https://cr.yp.to/papers/powers-ams.pdf
answered 1 hour ago
Alex J BestAlex J Best
2,32611226
2,32611226
add a comment |
add a comment |
$begingroup$
My suggestion on a computer is to run a root finder.
Given a value $y$, one way is to hard-code the first couple and then use an integer-valued binary search starting with $y/2$, which is logarithmic in $y$ and thus linear (since input takes $ln y$.
You can also write down the Newton's method recurrence and see if it converges to an integer or not, should become clear after the first couple of steps, once the error becomes small enough.
$endgroup$
$begingroup$
I don't think it's linear, given that you need to square the proposed number at every split.
$endgroup$
– Alex R.
1 hour ago
add a comment |
$begingroup$
My suggestion on a computer is to run a root finder.
Given a value $y$, one way is to hard-code the first couple and then use an integer-valued binary search starting with $y/2$, which is logarithmic in $y$ and thus linear (since input takes $ln y$.
You can also write down the Newton's method recurrence and see if it converges to an integer or not, should become clear after the first couple of steps, once the error becomes small enough.
$endgroup$
$begingroup$
I don't think it's linear, given that you need to square the proposed number at every split.
$endgroup$
– Alex R.
1 hour ago
add a comment |
$begingroup$
My suggestion on a computer is to run a root finder.
Given a value $y$, one way is to hard-code the first couple and then use an integer-valued binary search starting with $y/2$, which is logarithmic in $y$ and thus linear (since input takes $ln y$.
You can also write down the Newton's method recurrence and see if it converges to an integer or not, should become clear after the first couple of steps, once the error becomes small enough.
$endgroup$
My suggestion on a computer is to run a root finder.
Given a value $y$, one way is to hard-code the first couple and then use an integer-valued binary search starting with $y/2$, which is logarithmic in $y$ and thus linear (since input takes $ln y$.
You can also write down the Newton's method recurrence and see if it converges to an integer or not, should become clear after the first couple of steps, once the error becomes small enough.
answered 1 hour ago
gt6989bgt6989b
35.1k22557
35.1k22557
$begingroup$
I don't think it's linear, given that you need to square the proposed number at every split.
$endgroup$
– Alex R.
1 hour ago
add a comment |
$begingroup$
I don't think it's linear, given that you need to square the proposed number at every split.
$endgroup$
– Alex R.
1 hour ago
$begingroup$
I don't think it's linear, given that you need to square the proposed number at every split.
$endgroup$
– Alex R.
1 hour ago
$begingroup$
I don't think it's linear, given that you need to square the proposed number at every split.
$endgroup$
– Alex R.
1 hour ago
add a comment |
$begingroup$
In the specific case where you already know not only the number being checked but also the power, as the question's comment by the OP to Servaes states, then you have something like
$$k = a^n tag1labeleq1$$
where $k$ and $n$ are known integers, but with $a$ being an unknown value to check whether or not it's an integer. In this case, taking natural logarithms of both sides (you could use any base, but I suspect that implementation wise $e$ will likely at least be the fastest one, if not also the most accurate) gives
$$ln(k) = nln(a) ; Rightarrow ; ln(a) = fracln(k)n ; Rightarrow ; a = e^fracln(k)n tag2labeleq2$$
On a computer, this will give a floating point value that would be, even for large values of $k$, relatively close to the correct value of $a$.
You can now use any number of algorithms to relatively quickly & easily determine $a$ if it's an integer, or show it's not an integer. For example, you can start with the integer part obtained in eqrefeq2, call it $a_1$, to determine $k_1$. If $k_1$ is not correct, then if it's less than $k$, check $a_2 = a_1 + 1$, else check $a_2 = a_1 - 1$, and call the new result $k_2$. If $k_2$ is still not correct, add or subtract the integer amount (making sure it's at least 1) of $left|frack -k_2k_1 - k_2right|$ to $a_2$ to get a new $a_1$ value to check. Then repeat these steps as many times as needed. In almost all cases, I believe it should take very loops to find the correct value. However, note you should also include checks in case there is no such integer $a$, with this usually being seen when one integer value gives a lower result & the next higher gives a higher result (or higher result & next lower integer gives a lower result).
$endgroup$
add a comment |
$begingroup$
In the specific case where you already know not only the number being checked but also the power, as the question's comment by the OP to Servaes states, then you have something like
$$k = a^n tag1labeleq1$$
where $k$ and $n$ are known integers, but with $a$ being an unknown value to check whether or not it's an integer. In this case, taking natural logarithms of both sides (you could use any base, but I suspect that implementation wise $e$ will likely at least be the fastest one, if not also the most accurate) gives
$$ln(k) = nln(a) ; Rightarrow ; ln(a) = fracln(k)n ; Rightarrow ; a = e^fracln(k)n tag2labeleq2$$
On a computer, this will give a floating point value that would be, even for large values of $k$, relatively close to the correct value of $a$.
You can now use any number of algorithms to relatively quickly & easily determine $a$ if it's an integer, or show it's not an integer. For example, you can start with the integer part obtained in eqrefeq2, call it $a_1$, to determine $k_1$. If $k_1$ is not correct, then if it's less than $k$, check $a_2 = a_1 + 1$, else check $a_2 = a_1 - 1$, and call the new result $k_2$. If $k_2$ is still not correct, add or subtract the integer amount (making sure it's at least 1) of $left|frack -k_2k_1 - k_2right|$ to $a_2$ to get a new $a_1$ value to check. Then repeat these steps as many times as needed. In almost all cases, I believe it should take very loops to find the correct value. However, note you should also include checks in case there is no such integer $a$, with this usually being seen when one integer value gives a lower result & the next higher gives a higher result (or higher result & next lower integer gives a lower result).
$endgroup$
add a comment |
$begingroup$
In the specific case where you already know not only the number being checked but also the power, as the question's comment by the OP to Servaes states, then you have something like
$$k = a^n tag1labeleq1$$
where $k$ and $n$ are known integers, but with $a$ being an unknown value to check whether or not it's an integer. In this case, taking natural logarithms of both sides (you could use any base, but I suspect that implementation wise $e$ will likely at least be the fastest one, if not also the most accurate) gives
$$ln(k) = nln(a) ; Rightarrow ; ln(a) = fracln(k)n ; Rightarrow ; a = e^fracln(k)n tag2labeleq2$$
On a computer, this will give a floating point value that would be, even for large values of $k$, relatively close to the correct value of $a$.
You can now use any number of algorithms to relatively quickly & easily determine $a$ if it's an integer, or show it's not an integer. For example, you can start with the integer part obtained in eqrefeq2, call it $a_1$, to determine $k_1$. If $k_1$ is not correct, then if it's less than $k$, check $a_2 = a_1 + 1$, else check $a_2 = a_1 - 1$, and call the new result $k_2$. If $k_2$ is still not correct, add or subtract the integer amount (making sure it's at least 1) of $left|frack -k_2k_1 - k_2right|$ to $a_2$ to get a new $a_1$ value to check. Then repeat these steps as many times as needed. In almost all cases, I believe it should take very loops to find the correct value. However, note you should also include checks in case there is no such integer $a$, with this usually being seen when one integer value gives a lower result & the next higher gives a higher result (or higher result & next lower integer gives a lower result).
$endgroup$
In the specific case where you already know not only the number being checked but also the power, as the question's comment by the OP to Servaes states, then you have something like
$$k = a^n tag1labeleq1$$
where $k$ and $n$ are known integers, but with $a$ being an unknown value to check whether or not it's an integer. In this case, taking natural logarithms of both sides (you could use any base, but I suspect that implementation wise $e$ will likely at least be the fastest one, if not also the most accurate) gives
$$ln(k) = nln(a) ; Rightarrow ; ln(a) = fracln(k)n ; Rightarrow ; a = e^fracln(k)n tag2labeleq2$$
On a computer, this will give a floating point value that would be, even for large values of $k$, relatively close to the correct value of $a$.
You can now use any number of algorithms to relatively quickly & easily determine $a$ if it's an integer, or show it's not an integer. For example, you can start with the integer part obtained in eqrefeq2, call it $a_1$, to determine $k_1$. If $k_1$ is not correct, then if it's less than $k$, check $a_2 = a_1 + 1$, else check $a_2 = a_1 - 1$, and call the new result $k_2$. If $k_2$ is still not correct, add or subtract the integer amount (making sure it's at least 1) of $left|frack -k_2k_1 - k_2right|$ to $a_2$ to get a new $a_1$ value to check. Then repeat these steps as many times as needed. In almost all cases, I believe it should take very loops to find the correct value. However, note you should also include checks in case there is no such integer $a$, with this usually being seen when one integer value gives a lower result & the next higher gives a higher result (or higher result & next lower integer gives a lower result).
edited 19 mins ago
answered 27 mins ago
John OmielanJohn Omielan
4,2062215
4,2062215
add a comment |
add a comment |
$begingroup$
There are many powerful codes that factorize a number to its prime factors in a non-polynomial time (for more information you can refer to Integer Factorization on Wikipedia) . Once an integer was factorized as follows$$n=p_1^alpha_1times p_2^alpha_2timescdots times p_m^alpha_m$$then by defining $d=gcd(alpha_1,alpha_2,cdots ,alpha_m)$ we can say that $n$ is a full $d$-th power.
$endgroup$
$begingroup$
not sure about efficient, I believe it's an NP-complete problem. But surely checking if it is a perfect square would be doable more efficiently that doing the full prime factorization?!
$endgroup$
– gt6989b
1 hour ago
2
$begingroup$
For algorithms, "efficiently and fast" usually means being both deterministic and polynomial time in the length of the input; there is no known polynomial time deterministic algorithm for factoring integers, so I would absolutely quibble with your use of "efficiently and fast".
$endgroup$
– Arturo Magidin
1 hour ago
$begingroup$
This is orders-of-magnitude slower than just computing the square-root even by classical methods.
$endgroup$
– Alex R.
1 hour ago
$begingroup$
I was going to suggest that if you factorize $n>1$ as you have shown, with all of the $p_i$ distinct and all of the $alpha_i>0$, then $n$ is a perfect power if and only if all of the $alpha_i$ are equal.
$endgroup$
– MPW
1 hour ago
$begingroup$
I mean the most efficient that is possible so far
$endgroup$
– Mostafa Ayaz
1 hour ago
|
show 5 more comments
$begingroup$
There are many powerful codes that factorize a number to its prime factors in a non-polynomial time (for more information you can refer to Integer Factorization on Wikipedia) . Once an integer was factorized as follows$$n=p_1^alpha_1times p_2^alpha_2timescdots times p_m^alpha_m$$then by defining $d=gcd(alpha_1,alpha_2,cdots ,alpha_m)$ we can say that $n$ is a full $d$-th power.
$endgroup$
$begingroup$
not sure about efficient, I believe it's an NP-complete problem. But surely checking if it is a perfect square would be doable more efficiently that doing the full prime factorization?!
$endgroup$
– gt6989b
1 hour ago
2
$begingroup$
For algorithms, "efficiently and fast" usually means being both deterministic and polynomial time in the length of the input; there is no known polynomial time deterministic algorithm for factoring integers, so I would absolutely quibble with your use of "efficiently and fast".
$endgroup$
– Arturo Magidin
1 hour ago
$begingroup$
This is orders-of-magnitude slower than just computing the square-root even by classical methods.
$endgroup$
– Alex R.
1 hour ago
$begingroup$
I was going to suggest that if you factorize $n>1$ as you have shown, with all of the $p_i$ distinct and all of the $alpha_i>0$, then $n$ is a perfect power if and only if all of the $alpha_i$ are equal.
$endgroup$
– MPW
1 hour ago
$begingroup$
I mean the most efficient that is possible so far
$endgroup$
– Mostafa Ayaz
1 hour ago
|
show 5 more comments
$begingroup$
There are many powerful codes that factorize a number to its prime factors in a non-polynomial time (for more information you can refer to Integer Factorization on Wikipedia) . Once an integer was factorized as follows$$n=p_1^alpha_1times p_2^alpha_2timescdots times p_m^alpha_m$$then by defining $d=gcd(alpha_1,alpha_2,cdots ,alpha_m)$ we can say that $n$ is a full $d$-th power.
$endgroup$
There are many powerful codes that factorize a number to its prime factors in a non-polynomial time (for more information you can refer to Integer Factorization on Wikipedia) . Once an integer was factorized as follows$$n=p_1^alpha_1times p_2^alpha_2timescdots times p_m^alpha_m$$then by defining $d=gcd(alpha_1,alpha_2,cdots ,alpha_m)$ we can say that $n$ is a full $d$-th power.
edited 19 mins ago
answered 1 hour ago
Mostafa AyazMostafa Ayaz
18.1k31040
18.1k31040
$begingroup$
not sure about efficient, I believe it's an NP-complete problem. But surely checking if it is a perfect square would be doable more efficiently that doing the full prime factorization?!
$endgroup$
– gt6989b
1 hour ago
2
$begingroup$
For algorithms, "efficiently and fast" usually means being both deterministic and polynomial time in the length of the input; there is no known polynomial time deterministic algorithm for factoring integers, so I would absolutely quibble with your use of "efficiently and fast".
$endgroup$
– Arturo Magidin
1 hour ago
$begingroup$
This is orders-of-magnitude slower than just computing the square-root even by classical methods.
$endgroup$
– Alex R.
1 hour ago
$begingroup$
I was going to suggest that if you factorize $n>1$ as you have shown, with all of the $p_i$ distinct and all of the $alpha_i>0$, then $n$ is a perfect power if and only if all of the $alpha_i$ are equal.
$endgroup$
– MPW
1 hour ago
$begingroup$
I mean the most efficient that is possible so far
$endgroup$
– Mostafa Ayaz
1 hour ago
|
show 5 more comments
$begingroup$
not sure about efficient, I believe it's an NP-complete problem. But surely checking if it is a perfect square would be doable more efficiently that doing the full prime factorization?!
$endgroup$
– gt6989b
1 hour ago
2
$begingroup$
For algorithms, "efficiently and fast" usually means being both deterministic and polynomial time in the length of the input; there is no known polynomial time deterministic algorithm for factoring integers, so I would absolutely quibble with your use of "efficiently and fast".
$endgroup$
– Arturo Magidin
1 hour ago
$begingroup$
This is orders-of-magnitude slower than just computing the square-root even by classical methods.
$endgroup$
– Alex R.
1 hour ago
$begingroup$
I was going to suggest that if you factorize $n>1$ as you have shown, with all of the $p_i$ distinct and all of the $alpha_i>0$, then $n$ is a perfect power if and only if all of the $alpha_i$ are equal.
$endgroup$
– MPW
1 hour ago
$begingroup$
I mean the most efficient that is possible so far
$endgroup$
– Mostafa Ayaz
1 hour ago
$begingroup$
not sure about efficient, I believe it's an NP-complete problem. But surely checking if it is a perfect square would be doable more efficiently that doing the full prime factorization?!
$endgroup$
– gt6989b
1 hour ago
$begingroup$
not sure about efficient, I believe it's an NP-complete problem. But surely checking if it is a perfect square would be doable more efficiently that doing the full prime factorization?!
$endgroup$
– gt6989b
1 hour ago
2
2
$begingroup$
For algorithms, "efficiently and fast" usually means being both deterministic and polynomial time in the length of the input; there is no known polynomial time deterministic algorithm for factoring integers, so I would absolutely quibble with your use of "efficiently and fast".
$endgroup$
– Arturo Magidin
1 hour ago
$begingroup$
For algorithms, "efficiently and fast" usually means being both deterministic and polynomial time in the length of the input; there is no known polynomial time deterministic algorithm for factoring integers, so I would absolutely quibble with your use of "efficiently and fast".
$endgroup$
– Arturo Magidin
1 hour ago
$begingroup$
This is orders-of-magnitude slower than just computing the square-root even by classical methods.
$endgroup$
– Alex R.
1 hour ago
$begingroup$
This is orders-of-magnitude slower than just computing the square-root even by classical methods.
$endgroup$
– Alex R.
1 hour ago
$begingroup$
I was going to suggest that if you factorize $n>1$ as you have shown, with all of the $p_i$ distinct and all of the $alpha_i>0$, then $n$ is a perfect power if and only if all of the $alpha_i$ are equal.
$endgroup$
– MPW
1 hour ago
$begingroup$
I was going to suggest that if you factorize $n>1$ as you have shown, with all of the $p_i$ distinct and all of the $alpha_i>0$, then $n$ is a perfect power if and only if all of the $alpha_i$ are equal.
$endgroup$
– MPW
1 hour ago
$begingroup$
I mean the most efficient that is possible so far
$endgroup$
– Mostafa Ayaz
1 hour ago
$begingroup$
I mean the most efficient that is possible so far
$endgroup$
– Mostafa Ayaz
1 hour ago
|
show 5 more comments
$begingroup$
It is at least possible to do this in polynomial time. Assume $n$ is a $k$-bit number and you want to find positive integers $a$ and $b$ such that $$a^b=ntag1$$ or prove that such numbers don't exists.
We have $$n<2^k$$ because $n$ is a $k$-bit number and so $$blt k$$
We can simply check for all possible $b$ if there is an $a$ such that $(1)$ holds. For given $b$ we can try to find $a$ by bisection. This bisection checks $O(log n)=O(k)$ different $a$. A check is the calculation of $a^b$. This can be achieved by multiplying powers of $a$ by $a$. These powers of $a$ are smaller than $n$. So we multiply $k$-bit numbers at most $b(lt k)$ times. A multiplication of two $k$-bit numbers needs $O(k^2)$ time. So all in all the algorithm needs $O(k^2)$ multiplications o $k$-bit numbers, which means $O(k^4)$ time.
$endgroup$
add a comment |
$begingroup$
It is at least possible to do this in polynomial time. Assume $n$ is a $k$-bit number and you want to find positive integers $a$ and $b$ such that $$a^b=ntag1$$ or prove that such numbers don't exists.
We have $$n<2^k$$ because $n$ is a $k$-bit number and so $$blt k$$
We can simply check for all possible $b$ if there is an $a$ such that $(1)$ holds. For given $b$ we can try to find $a$ by bisection. This bisection checks $O(log n)=O(k)$ different $a$. A check is the calculation of $a^b$. This can be achieved by multiplying powers of $a$ by $a$. These powers of $a$ are smaller than $n$. So we multiply $k$-bit numbers at most $b(lt k)$ times. A multiplication of two $k$-bit numbers needs $O(k^2)$ time. So all in all the algorithm needs $O(k^2)$ multiplications o $k$-bit numbers, which means $O(k^4)$ time.
$endgroup$
add a comment |
$begingroup$
It is at least possible to do this in polynomial time. Assume $n$ is a $k$-bit number and you want to find positive integers $a$ and $b$ such that $$a^b=ntag1$$ or prove that such numbers don't exists.
We have $$n<2^k$$ because $n$ is a $k$-bit number and so $$blt k$$
We can simply check for all possible $b$ if there is an $a$ such that $(1)$ holds. For given $b$ we can try to find $a$ by bisection. This bisection checks $O(log n)=O(k)$ different $a$. A check is the calculation of $a^b$. This can be achieved by multiplying powers of $a$ by $a$. These powers of $a$ are smaller than $n$. So we multiply $k$-bit numbers at most $b(lt k)$ times. A multiplication of two $k$-bit numbers needs $O(k^2)$ time. So all in all the algorithm needs $O(k^2)$ multiplications o $k$-bit numbers, which means $O(k^4)$ time.
$endgroup$
It is at least possible to do this in polynomial time. Assume $n$ is a $k$-bit number and you want to find positive integers $a$ and $b$ such that $$a^b=ntag1$$ or prove that such numbers don't exists.
We have $$n<2^k$$ because $n$ is a $k$-bit number and so $$blt k$$
We can simply check for all possible $b$ if there is an $a$ such that $(1)$ holds. For given $b$ we can try to find $a$ by bisection. This bisection checks $O(log n)=O(k)$ different $a$. A check is the calculation of $a^b$. This can be achieved by multiplying powers of $a$ by $a$. These powers of $a$ are smaller than $n$. So we multiply $k$-bit numbers at most $b(lt k)$ times. A multiplication of two $k$-bit numbers needs $O(k^2)$ time. So all in all the algorithm needs $O(k^2)$ multiplications o $k$-bit numbers, which means $O(k^4)$ time.
answered 17 mins ago
miracle173miracle173
7,38022247
7,38022247
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%2f3165146%2fmethod-to-test-if-a-number-is-a-perfect-power%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
1
$begingroup$
One very cheap, necessary condition is that $x^2pmod 4equiv 0,1$.
$endgroup$
– Alex R.
1 hour ago
$begingroup$
Are you given numbers $k$ and $n$ and asked to check whether $k$ is an $n$-th power? Or are you given just $k$ and asked to check whether $k$ is a perfect power?
$endgroup$
– Servaes
1 hour ago
$begingroup$
@Servaes, I was considering the first case, where I know both k and n and trying to see if $k = a^n,$ a a positive integer.
$endgroup$
– D.B.
1 hour ago
$begingroup$
Wait, @Alex R. Looking at your first comment, what about $x^2 = 40 = 0 (mod 4)$. Yet, $40$ is not a perfect square.
$endgroup$
– D.B.
1 hour ago
2
$begingroup$
@D.B.: Hence it's a necessary condition: if $x^2$ is a perfect square, then $x^2equiv 0,1pmod4$. The other direction gives: if $yequiv 2,3pmod4$, then $y$ cannot be a perfect square.
$endgroup$
– Alex R.
1 hour ago