On Mon, Jun 14, 2010 at 11:17 PM, Dan Drake <[email protected]> wrote: > On Tue, 15 Jun 2010 at 10:58AM +0530, Santanu Sarkar wrote: >> Is there any function by which we can decide a positive integer X, >> is a perfect cube or not i.e., weather there is an integer Y such that >> >> Y^3=X? > > There is probably a much better way, but you can get the exponents of > the prime factorization and check if they're divisible by 3:
That has complexity "issues", at least if X is large. Better would be to factor the polynomial y^3 - x: sage: y = polygen(ZZ,'y') sage: (y^3 - 27).roots() [(3, 1)] sage: len((y^3 - 27).roots()) > 0 True sage: len((y^3 - 997^3).roots()) > 0 True sage: len((y^3 - 997^3*17).roots()) > 0 False At least this is polynomial time and trivial to implement. One can probably do better by just computing explicitly the cube root of y to sufficiently large precision numerically, and checking if the result is an integer, e.g., sage: s = numerical_approx(997^3, 500)^(1/3); (s-s.floor()) < 1e-100 True sage: s = numerical_approx(997^3*17, 500)^(1/3); (s-s.floor()) < 1e-100 False > > sage: x = 8 > sage: list(x.factor()) > [(2, 3)] > sage: all(e % 3 == 0 for p, e in x.factor()) > True > sage: x = 10 > sage: all(e % 3 == 0 for p, e in x.factor()) > False > > > > Dan > > -- > --- Dan Drake > ----- http://mathsci.kaist.ac.kr/~drake > ------- > > -----BEGIN PGP SIGNATURE----- > Version: GnuPG v1.4.10 (GNU/Linux) > > iEYEARECAAYFAkwXGxAACgkQr4V8SljC5Lo6VQCgjyyFYfreEhh9aDGVNl9RZ7Qc > HYkAn2CUj31hydEYCJsF4mr7fGwrgvqW > =DrmM > -----END PGP SIGNATURE----- > > -- William Stein Professor of Mathematics University of Washington http://wstein.org -- To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
