Sieve Algorithms for Perfect Power Testing

Eric Bach; Jonathan P Sorenson

doi:10.1007/BF01228507

Sieve Algorithms for Perfect Power Testing

Eric Bach
, Jonathan P Sorenson

Butler University

Research output: Contribution to journal › Article › peer-review

Original language	American English
Journal	Algorithmica
Volume	9
DOIs	https://doi.org/10.1007/BF01228507
State	Published - Apr 1993

Disciplines

Theory and Algorithms
Number Theory

Access to Document

10.1007/BF01228507License: Unspecified

Cite this

@article{aea9779cf7ac44c6b0d86937bd5e00ee,

title = "Sieve Algorithms for Perfect Power Testing",

author = "Eric Bach and Sorenson, \{Jonathan P\}",

note = "A positive integern is a perfect power if there exist integersx andk, both at least 2, such thatn=x k . The usual algorithm to recognize perfect powers computes approximatekth roots fork≤log 2 n, and runs in time O(log3 n log log logn).First we improve this worst-case running time toO(log3 n) by using a modified Newton's method to compute approximatekth roots.",

year = "1993",

month = apr,

doi = "10.1007/BF01228507",

language = "American English",

volume = "9",

journal = "Algorithmica",

issn = "0178-4617",

}

TY - JOUR

T1 - Sieve Algorithms for Perfect Power Testing

AU - Bach, Eric

AU - Sorenson, Jonathan P

N1 - A positive integern is a perfect power if there exist integersx andk, both at least 2, such thatn=x k . The usual algorithm to recognize perfect powers computes approximatekth roots fork≤log 2 n, and runs in time O(log3 n log log logn).First we improve this worst-case running time toO(log3 n) by using a modified Newton's method to compute approximatekth roots.

PY - 1993/4

Y1 - 1993/4

UR - https://doi.org/10.1007/BF01228507

U2 - 10.1007/BF01228507

DO - 10.1007/BF01228507

M3 - Article

SN - 0178-4617

VL - 9

JO - Algorithmica

JF - Algorithmica

ER -

Sieve Algorithms for Perfect Power Testing

Disciplines

Access to Document

Other files and links

Cite this