perfect_power for integers #12116

roed314 · 2011-12-04T04:43:15Z

Currently there are two functions for testing whether an integer is a perfect power:

sage: 8.is_power()
True
sage: 8.is_perfect_power()
True

This patch deprecates is_power.
It implements a new function, perfect_power, wrapping PARI's ispower function, expressing an integer in the form a^b with b maximal.
It adds cross references between is_perfect_power, is_power_of, is_prime_power and perfect_power.

This revealed three bugs in PARI's ispower() function:

Two issues reported and fixed at http://pari.math.u-bordeaux.fr/cgi-bin/bugreport.cgi?bug=1259
One more issue reported and fixed at http://pari.math.u-bordeaux.fr/cgi-bin/bugreport.cgi?bug=1302 (duplicate: http://pari.math.u-bordeaux.fr/cgi-bin/bugreport.cgi?bug=1303)

Apply attachment: trac_12116-rebase4.patch

Depends on #10596
Depends on #12363
Depends on #12638

Upstream: Fixed upstream, but not in a stable release.

CC: @jpflori

Component: basic arithmetic

Author: David Roe

Reviewer: David Loeffler, Aly Deines, Simon Spicer

Merged: sage-5.8.beta3

Issue created by migration from https://trac.sagemath.org/ticket/12116

The text was updated successfully, but these errors were encountered:

roed314 · 2011-12-04T12:44:23Z

comment:1

The bug is being tracked by Pari: their ticket number is 1259.

roed314 · 2011-12-04T12:44:23Z

Changed upstream from Not yet reported upstream; Will do shortly. to Reported upstream. Little or no feedback.

roed314 · 2011-12-05T00:17:59Z

comment:3

Here's the response from the Pari developers:

The 2 problems turned out to be independant. They are now fixed in the
'testing' branch, in the following 2 commits:

commit f53eb2a7c79922ac51423e75044722628893159e
Author: Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>
Date:   Sun Dec 4 17:43:19 2011 +0100

   46- ispower(1 / n) return a wrong result [#1259]

commit 74aef498d380979211b99d64f4f4c92b8bac853f
Author: Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>
Date:   Sun Dec 4 17:28:14 2011 +0100

   45- ispower(x < 0) could return an even value ! [#1259]

That was quick. :-)

roed314 · 2011-12-05T00:17:59Z

Changed upstream from Reported upstream. Little or no feedback. to Fixed upstream, but not in a stable release.

jasongrout · 2011-12-13T17:56:09Z

comment:4

I'm curious why you didn't use the Sphinx seealso directive: http://sphinx.pocoo.org/markup/para.html#directive-seealso

roed314 · 2011-12-15T05:14:43Z

comment:5

No good reason.

Apply 12116.2.patch only.

loefflerd · 2012-03-11T10:23:23Z

comment:6

Sadly roed's patch conflicts with #10596 and thus doesn't apply to the current Sage beta. I've just uploaded a rebased patch based on 5.0.beta7. This makes no changes to roed's code other than some minor sphinx reformatting (including using the new :trac: directive to point to this ticket). David: if you're happy with my reworking of your patch, you can set this to positive review.

loefflerd · 2012-03-11T10:23:23Z

Dependencies: 10596

loefflerd · 2012-03-11T10:23:23Z

Reviewer: David Loeffler

loefflerd · 2012-03-11T10:24:47Z

Changed dependencies from 10596 to #10596

roed314 · 2012-03-11T17:31:05Z

comment:8

Thanks for rebasing! I looked it over and it looks good to me.

jdemeyer · 2012-03-11T21:35:03Z

Changed upstream from Fixed upstream, but not in a stable release. to Completely fixed; Fix reported upstream

jdemeyer · 2012-03-11T21:35:03Z

comment:9

The upstream fix is in Sage now (#12363). Could you remove the workaround code from the patch?

jdemeyer · 2012-03-11T21:35:03Z

Changed dependencies from #10596 to #10596, #12363

loefflerd · 2012-03-12T15:05:16Z

Changed upstream from Completely fixed; Fix reported upstream to None of the above - read trac for reasoning.

loefflerd · 2012-03-12T15:05:16Z

comment:10

Can we have a new option for the "Report Upstream" menu, "upstream claim to have fixed it but they apparently haven't"? PARI apparently believes that 2^3 = -8:

                                      GP/PARI CALCULATOR Version 2.5.1 (development git-5c5e253)
                                     amd64 running linux (x86-64/GMP-5.0.1 kernel) 64-bit version
                                       compiled: Mar  5 2012, gcc-4.4.3 (Ubuntu 4.4.3-4ubuntu5) 
                                            (readline v6.2 enabled, extended help enabled)

                                                Copyright (C) 2000-2011 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and comes WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.

parisize = 8000000, primelimit = 500509
? ispower(-8, , &n)
%1 = 3
? n
%2 = 2

So I suggest we merge this patch as it is, and send another bug report to PARI -- roed, can you do the honours?

jdemeyer · 2012-03-12T16:34:48Z

comment:11

I reported the new issue upstream. I would postpone merging this patch until we hear from upstream. I prefer to have the issue fixed upstream and not apply a work-around in Sage.

roed314 · 2013-02-27T11:44:22Z

Attachment: trac_12116-rebase.patch.gz

Rebased against 5.8.beta0

roed314 · 2013-02-27T11:45:04Z

comment:24

Alright, fixed.

adeines · 2013-02-28T21:47:38Z

Changed reviewer from David Loeffler to David Loeffler, Aly Deines

haikona · 2013-02-28T22:05:27Z

Attachment: trac_12116_rebase2.patch.gz

Flips order of returned pair in self.perfect_power()

haikona · 2013-02-28T22:16:30Z

comment:26

Everything checks out. Patch applies, tests pass. However:

def perfect_power(self): 
    r""" 	         
    Returns ``(a, b)``, where this integer is `b^a` and `a` is maximal.
    ...

So

sage: a = 11^14
sage: a.perfect_power()
(14, 11)

I know the code just wraps PARI which returns the integers in this order, but this seems an unnatural way to order the returned pair.

I've uploaded a modified version of the patch so that we get

sage: a = 11^14
sage: a.perfect_power()
(11, 14)

which feels a lot more natural.

The new patch also fixes a possible formatting error in the documentation of self.is_perfect_power():

Returns ``True`` if self is a perfect power, ie if there exist integers
a and b, `b > 1` with `\texttt{self} = a^b`.

becomes

Returns ``True`` if ``self`` is a perfect power, ie if there exist integers
`a` and `b`, `b > 1` with ``self`` `= a^b`.

haikona · 2013-02-28T22:17:58Z

Changed reviewer from David Loeffler, Aly Deines to David Loeffler, Aly Deines, Simon Spicer

roed314 · 2013-03-01T01:14:20Z

Attachment: trac_12116-rebase3.patch.gz

roed314 · 2013-03-01T01:14:51Z

comment:29

Looks fine to me. I just updated the deprecated_function_alias.

haikona · 2013-03-01T01:46:04Z

Attachment: trac_12116-rebase4.patch.gz

Changed a line to unbreak factor_aurifeuillian() in factorint.pyx

haikona · 2013-03-01T01:49:49Z

comment:30

We missed another line. In self.factor_aurifeuillian() in factorint.pyx, we have

...
b = n + x
exp, b = b.perfect_power()
if exp > 1:
...

This must now become

...
b = n + x
b, exp = b.perfect_power()
if exp > 1:
...

otherwise this method breaks with the new ordering of values returned by perfect_power(). I've uploaded a new patch that fixes this.

Hopefully that should be it.

roed314 · 2013-03-01T04:11:49Z

comment:31

Looks good to me.

roed314 · 2013-03-02T08:31:42Z

comment:32

For patchbot:

Apply trac_12116-rebase4.patch

jdemeyer · 2013-03-04T07:36:39Z

Merged: sage-5.8.beta3

roed314 added this to the sage-5.8 milestone Dec 4, 2011

roed314 added p: major / 3 labels Dec 4, 2011

roed314 added the c: basic arithmetic label Dec 4, 2011

roed314 assigned aghitza Dec 4, 2011

roed314 added the s: needs review label Dec 4, 2011

roed314 added s: positive review and removed s: needs review labels Mar 11, 2012

This comment has been minimized.

Sign in to view

jdemeyer added s: needs work and removed s: positive review labels Mar 11, 2012

loefflerd mannequin added s: needs review and removed s: needs work labels Mar 12, 2012

roed314 added the s: needs work label Feb 27, 2013

roed314 added s: needs review and removed s: needs work labels Feb 27, 2013

adeines mannequin added s: positive review and removed s: needs review labels Feb 28, 2013

haikona mannequin added s: needs work and removed s: positive review labels Feb 28, 2013

This comment has been minimized.

Sign in to view

roed314 added s: positive review and removed s: needs review labels Mar 1, 2013

jdemeyer removed the s: positive review label Mar 4, 2013

jdemeyer closed this as completed Mar 4, 2013

sagetrac-mvngu mannequin mentioned this issue Mar 6, 2013

function to test whether or not some integer is a primitive root modulo n #6567

Closed

roed314 mentioned this issue Mar 2, 2014

Bugfixes and improvements to Aurifeuillian factorization #12117

Closed

jdemeyer mentioned this issue Apr 2, 2012

Add some patches to the PARI sources #12638

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

perfect_power for integers #12116

perfect_power for integers #12116

roed314 commented Dec 4, 2011

roed314 commented Dec 4, 2011

roed314 commented Dec 4, 2011

roed314 commented Dec 5, 2011

roed314 commented Dec 5, 2011

jasongrout commented Dec 13, 2011

roed314 commented Dec 15, 2011

loefflerd mannequin commented Mar 11, 2012

loefflerd mannequin commented Mar 11, 2012

loefflerd mannequin commented Mar 11, 2012

loefflerd mannequin commented Mar 11, 2012

roed314 commented Mar 11, 2012

This comment has been minimized.

jdemeyer commented Mar 11, 2012

jdemeyer commented Mar 11, 2012

jdemeyer commented Mar 11, 2012

loefflerd mannequin commented Mar 12, 2012

loefflerd mannequin commented Mar 12, 2012

jdemeyer commented Mar 12, 2012

roed314 commented Feb 27, 2013

roed314 commented Feb 27, 2013

adeines mannequin commented Feb 28, 2013

haikona mannequin commented Feb 28, 2013

haikona mannequin commented Feb 28, 2013

haikona mannequin commented Feb 28, 2013

roed314 commented Mar 1, 2013

roed314 commented Mar 1, 2013

haikona mannequin commented Mar 1, 2013

haikona mannequin commented Mar 1, 2013

This comment has been minimized.

roed314 commented Mar 1, 2013

roed314 commented Mar 2, 2013

jdemeyer commented Mar 4, 2013

perfect_power for integers #12116

perfect_power for integers #12116

Comments

roed314 commented Dec 4, 2011

roed314 commented Dec 4, 2011

roed314 commented Dec 4, 2011

roed314 commented Dec 5, 2011

roed314 commented Dec 5, 2011

jasongrout commented Dec 13, 2011

roed314 commented Dec 15, 2011

loefflerd mannequin commented Mar 11, 2012

loefflerd mannequin commented Mar 11, 2012

loefflerd mannequin commented Mar 11, 2012

loefflerd mannequin commented Mar 11, 2012

roed314 commented Mar 11, 2012

This comment has been minimized.

jdemeyer commented Mar 11, 2012

jdemeyer commented Mar 11, 2012

jdemeyer commented Mar 11, 2012

loefflerd mannequin commented Mar 12, 2012

loefflerd mannequin commented Mar 12, 2012

jdemeyer commented Mar 12, 2012

roed314 commented Feb 27, 2013

roed314 commented Feb 27, 2013

adeines mannequin commented Feb 28, 2013

haikona mannequin commented Feb 28, 2013

haikona mannequin commented Feb 28, 2013

haikona mannequin commented Feb 28, 2013

roed314 commented Mar 1, 2013

roed314 commented Mar 1, 2013

haikona mannequin commented Mar 1, 2013

haikona mannequin commented Mar 1, 2013

This comment has been minimized.

roed314 commented Mar 1, 2013

roed314 commented Mar 2, 2013

jdemeyer commented Mar 4, 2013