Sage: Ticket #13516: prime_powers doesn't work with start very well
https://trac.sagemath.org/ticket/13516
<p>
See <a class="ext-link" href="https://groups.google.com/forum/?fromgroups=#!topic/sage-support/lW_a7ZE3Zf8"><span class="icon"></span>this sage-support thread</a>.
</p>
<pre class="wiki">
In Sage 5.3, the function prime_powers behaves a little strange:
sage: prime_powers(4,10)
[4, 5, 7, 8, 9]
# As expected
sage: prime_powers(5,10)
[7, 8, 9]
# 5 isn't a prime power anymore???
# And now things become even worse:
sage: prime_powers(7,10)
---------------------------------------------------------------------------
IndexError Traceback (most recent call last)
/home/mueller/<ipython console> in <module>()
/home/mueller/local/sage-5.3/local/lib/python2.7/site-packages/sage/rings/arith.pyc in prime_powers(start, stop)
743 i = bisect(v, start)
744 if start > 2:
--> 745 if v[i] == start:
746 i -= 1
747 w = list(v[i:])
IndexError: list index out of range
</pre><p>
Yeah, this seems problematic. The code in question is <em>old</em>, too, so perhaps there is a more efficient way to do it in the meantime...
</p>
<p>
<strong>Apply</strong> to <code>devel/sage</code>: <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/13516/13516_primepowers.2.patch" title="Attachment '13516_primepowers.2.patch' in Ticket #13516">13516_primepowers.2.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/13516/13516_primepowers.2.patch" title="Download"></a>.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/13516
Trac 1.1.6kcrismanFri, 21 Sep 2012 16:37:59 GMTkeywords set
https://trac.sagemath.org/ticket/13516#comment:1
https://trac.sagemath.org/ticket/13516#comment:1
<ul>
<li><strong>keywords</strong>
<em>beginner</em> added
</li>
</ul>
TicketdimpaseThu, 27 Sep 2012 23:59:03 GMT
https://trac.sagemath.org/ticket/13516#comment:2
https://trac.sagemath.org/ticket/13516#comment:2
<p>
as <code>prime_powers(m)</code> works, an easy workaround is to re-implement <code>prime_powers(m,n)</code> as the difference of
<code>prime_powers(n)</code> and <code>prime_powers(m-1)</code>.
</p>
TicketkhalaszTue, 09 Oct 2012 03:52:51 GMTstatus, description changed
https://trac.sagemath.org/ticket/13516#comment:3
https://trac.sagemath.org/ticket/13516#comment:3
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/13516?action=diff&version=3">diff</a>)
</li>
</ul>
TicketkhalaszTue, 09 Oct 2012 03:54:41 GMT
https://trac.sagemath.org/ticket/13516#comment:4
https://trac.sagemath.org/ticket/13516#comment:4
<p>
I found the code to be riddled with errors, so I decided to completely rework it. Also, I have qualms about calling 1 a prime power, but did so because the old function did. If you think its fine to drop this, let me know.
</p>
TicketkcrismanTue, 09 Oct 2012 04:01:36 GMT
https://trac.sagemath.org/ticket/13516#comment:5
https://trac.sagemath.org/ticket/13516#comment:5
<p>
Thanks for your work - hopefully someone will review it soon. You can put your real name in the author area.
</p>
<blockquote class="citation">
<p>
Also, I have qualms about calling 1 a prime power, but did so because the old function did. If you think its fine to drop this, let me know.
</p>
</blockquote>
<p>
Well, John Horton Conway does call -1 a prime, in which case every nonzero integer (not just positive) is a unique product of prime powers - not a unique product of primes, note, nor of the exponents, but of the prime powers themselves (I can't find a link for this right now, my apologies) in which case positives get the power 1 and and negatives -1. I think that's right... anyway, maybe they were thinking this?
</p>
TicketwasTue, 09 Oct 2012 05:04:41 GMT
https://trac.sagemath.org/ticket/13516#comment:6
https://trac.sagemath.org/ticket/13516#comment:6
<p>
I would prefer to leave 1 as a prime power because it is listed in Sloane's tables as a prime power: <a class="ext-link" href="http://oeis.org/A000961"><span class="icon"></span>http://oeis.org/A000961</a>
</p>
<p>
There he says "Since 1 = p<sup>0 does not have a well defined prime base p, it is sometimes not regarded as a prime power.", which might be where your misgivings come from.
</sup></p>
<p>
If by "prime power" one thinks of "power of a prime", the only question is in what set are we considering the prime powers. If we take the natural numbers, then the number 1 is definitely a power of a prime.
</p>
<p>
If by "prime power" one thinks "power of a specific canonical prime", then 1 is not such a thing.
</p>
<p>
In this case, the best thing to do is stick with what is there (to avoid introducing bugs in other people's code!) and clearly document/define what a prime power is in Sage.
</p>
TicketkhalaszFri, 12 Oct 2012 19:21:16 GMTauthor set
https://trac.sagemath.org/ticket/13516#comment:7
https://trac.sagemath.org/ticket/13516#comment:7
<ul>
<li><strong>author</strong>
set to <em>Kevin Halasz</em>
</li>
</ul>
TicketkhalaszThu, 18 Oct 2012 04:50:04 GMT
https://trac.sagemath.org/ticket/13516#comment:8
https://trac.sagemath.org/ticket/13516#comment:8
<p>
I just updated the docstring to make the fact that 1 is a prime power explicit.
</p>
TicketkcrismanThu, 18 Oct 2012 17:55:45 GMT
https://trac.sagemath.org/ticket/13516#comment:9
https://trac.sagemath.org/ticket/13516#comment:9
<p>
Could you speed this up slightly by making <code>s = stop.sqrt()</code> or something so that it's not computed for each prime. In fact, even that is a more expensive comparison each time because <code>stop.sqrt()</code> is likely a symbolic element, so maybe even <code>stop.sqrt().n()</code> would be appropriate... Also, once <code>p >stop.sqrt()</code>, presumably all remaining <code>p</code> are beyond it as well, so maybe there could be some speedup there too. Just some ideas.
</p>
TicketkhalaszThu, 18 Oct 2012 20:55:17 GMT
https://trac.sagemath.org/ticket/13516#comment:10
https://trac.sagemath.org/ticket/13516#comment:10
<p>
I've changed the patch so that s=stop.sqrt() is calculated outside of the for loop. After some tests, I saw that this was faster than setting s=stop.sqrt().n().
</p>
<p>
Also, note that when p>s, the content of that if loop is a break command, meaning that the entire for loop ends. Thus, once a single p>s, no more p values are tried.
</p>
TicketdimpaseSat, 20 Oct 2012 07:35:03 GMTstatus changed
https://trac.sagemath.org/ticket/13516#comment:11
https://trac.sagemath.org/ticket/13516#comment:11
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
The comment on line 708 in <code>sage/rings/arith.py</code> needs to be fixed, too - it talks about primes rather than prime powers.
</p>
<p>
I also think that the following:
</p>
<pre class="wiki"> sage: prime_powers(10,7)
761 Traceback (most recent call last):
762 ...
763 ValueError: the first input must be less than the second input, however, 10 > 7
</pre><p>
i.e. the corresponding implementation logic is not right, in the sense that it should just return empty lists rather than throwing exceptions. And negative <code>start</code> should be allowed too (cf. the semantics of <code>range()</code>).
</p>
<p>
Then, in the following fragment
</p>
<pre class="wiki"> 783 output = prime_range(start,stop)
784 if start == 1:
785 output.append(1)
786
787 s = stop.sqrt()
788 for p in prime_range(stop):
</pre><p>
<code>prime_range()</code>, which is not cheap, is basically called two times instead of one.
One can do with one call to <code>prime_range(stop)</code> just fine.
</p>
TicketkhalaszSun, 21 Oct 2012 01:15:07 GMTstatus changed
https://trac.sagemath.org/ticket/13516#comment:12
https://trac.sagemath.org/ticket/13516#comment:12
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Dimpase, I've addressed all of your suggestions. Let me know what you think of these changes/if you have other suggestions.
</p>
TicketdimpaseSun, 21 Oct 2012 09:57:15 GMTdescription changed
https://trac.sagemath.org/ticket/13516#comment:13
https://trac.sagemath.org/ticket/13516#comment:13
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/13516?action=diff&version=13">diff</a>)
</li>
</ul>
TicketdimpaseSun, 21 Oct 2012 09:58:35 GMTdescription changed
https://trac.sagemath.org/ticket/13516#comment:14
https://trac.sagemath.org/ticket/13516#comment:14
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/13516?action=diff&version=14">diff</a>)
</li>
</ul>
TicketdimpaseSun, 21 Oct 2012 10:12:28 GMTstatus changed
https://trac.sagemath.org/ticket/13516#comment:15
https://trac.sagemath.org/ticket/13516#comment:15
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
You always should coerce <code>stop</code> into Integer. Indeed, currently one gets:
</p>
<pre class="wiki">sage: prime_powers(1,int(9))
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
/usr/local/src/sage/sage-5.4.rc0/devel/sage-main/<ipython console> in <module>()
/usr/local/src/sage/sage-5.4.rc0/local/lib/python2.7/site-packages/sage/rings/arith.pyc in prime_powers(start, stop)
761 from sage.rings.integer import is_Integer
762 if not (is_Integer(start) and (is_Integer(stop) or stop == None)):
--> 763 raise TypeError, "both inputs must be integers, but your inputs were %s and %s"%(start,stop)
764
765 # deal with the case in which only one input is given
TypeError: both inputs must be integers, but your inputs were 1 and 9
</pre><p>
This is because taking <code>sqrt(int(9))</code> does not work too well in Sage...
</p>
<p>
Second issue: the comment <code> # check that all inputs are positive integers</code> on line 760 is misleading!
</p>
TicketppurkaMon, 22 Oct 2012 12:20:45 GMT
https://trac.sagemath.org/ticket/13516#comment:16
https://trac.sagemath.org/ticket/13516#comment:16
<p>
In the documentation please write <code>`start`, `stop`</code> with double backticks. The single backticks will make them be formatted as latex, which is not what is desired.
</p>
TicketkhalaszFri, 26 Oct 2012 06:55:44 GMT
https://trac.sagemath.org/ticket/13516#comment:17
https://trac.sagemath.org/ticket/13516#comment:17
<p>
Dimpase,
</p>
<p>
I'm not sure if I understand what you're suggesting I do. Should I replace the check that the inputs are Integers with a coercion of the inputs into Integers? Once I coerce the elements the check is redundant, as either it raises an error in and of itself (say, if it was passed a string it will raise a <a class="missing wiki">TypeError?</a>), or will fix the problem.
</p>
TicketdimpaseFri, 26 Oct 2012 09:36:56 GMT
https://trac.sagemath.org/ticket/13516#comment:18
https://trac.sagemath.org/ticket/13516#comment:18
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13516#comment:17" title="Comment 17">khalasz</a>:
</p>
<blockquote class="citation">
<p>
Dimpase,
</p>
<p>
I'm not sure if I understand what you're suggesting I do. Should I replace the check that the inputs are Integers with a coercion of the inputs into Integers? Once I coerce the elements the check is redundant, as either it raises an error in and of itself (say, if it was passed a string it will raise a <a class="missing wiki">TypeError?</a>), or will fix the problem.
</p>
</blockquote>
<p>
I think I would prefer the input of type <code>int</code> to be coerced into <code>Integer</code>, and throw an error if it's neither <code>int</code> nor <code>Integer</code>. The reason is that one could potentially try to apply this function to different from <code>ZZ</code> rings, with strange results, if one just blindly coerces stuff into <code>Integer</code>.
</p>
TicketppurkaFri, 26 Oct 2012 11:28:41 GMT
https://trac.sagemath.org/ticket/13516#comment:19
https://trac.sagemath.org/ticket/13516#comment:19
<p>
I think you can write it like this
</p>
<pre class="wiki">from sage.rings.integer import Integer
if not isinstance(start, (int, Integer)):
raise TypeError("start must be an integer")
if stop is not None and not isinstance(stop, (int, Integer)):
raise TypeError("stop must be an integer")
</pre>
TicketkhalaszTue, 30 Oct 2012 01:36:47 GMTstatus changed
https://trac.sagemath.org/ticket/13516#comment:20
https://trac.sagemath.org/ticket/13516#comment:20
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
I've made the changes. Let me know what you think!
</p>
TicketdimpaseTue, 30 Oct 2012 10:33:40 GMTstatus changed
https://trac.sagemath.org/ticket/13516#comment:21
https://trac.sagemath.org/ticket/13516#comment:21
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13516#comment:20" title="Comment 20">khalasz</a>:
</p>
<blockquote class="citation">
<p>
I've made the changes. Let me know what you think!
</p>
</blockquote>
<p>
I think there is a bug in the code, coming from the fact that
</p>
<pre class="wiki">sage: Integer(None)==None
False
</pre><p>
You also should have test cases (doctests) for all the different combinations of start/stop, and test them, too. You know that you can run Sage so that it tests doctests in a particular file, right?
E.g. the bug above would have been caught by the proper doctest.
Also, for some reason you removed the test <code>sage: v = prime_powers(10)</code>, but it was there for good reason.
</p>
TicketkhalaszFri, 02 Nov 2012 06:21:56 GMT
https://trac.sagemath.org/ticket/13516#comment:22
https://trac.sagemath.org/ticket/13516#comment:22
<p>
I forgot to rebuild sage before doctesting before posting this patch. Sorry for putting it up with such a stupid mistake. I've fixed it, and added back the test <code>sage: v = prime_powers(1)</code>.
</p>
<p>
I think I've covered all the possible basic scenarios in the doctests, in both the EXAMPLES and the TESTS, do you disagree?
</p>
TicketkhalaszFri, 02 Nov 2012 06:23:20 GMTstatus changed
https://trac.sagemath.org/ticket/13516#comment:23
https://trac.sagemath.org/ticket/13516#comment:23
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketppurkaFri, 02 Nov 2012 06:46:28 GMT
https://trac.sagemath.org/ticket/13516#comment:24
https://trac.sagemath.org/ticket/13516#comment:24
<p>
Some more nitpicks. :)
</p>
<ol><li>Don't use <code>==</code> or <code>!=</code> when comparing against <code>None</code>. See <a class="ext-link" href="http://www.python.org/dev/peps/pep-0008/#programming-recommendations"><span class="icon"></span>PEP 8</a>.
</li><li>When you describe the arguments <code>start</code> and <code>stop</code>, then describe the default value too.
<pre class="wiki"> - ``start`` - an integer. If two inputs are given, ....
- ``stop`` - an integer (default: ``None``). An upper bound for ....
</pre></li><li>Please don't remove the trac numbers from the examples. They were put there after someone fixed some bug.
<pre class="wiki"> sage: type(v[0]) # trac #922
</pre></li><li>Can you write the <code>TypeError</code> in python 3 style? Every small bit will help in the migration to python 3 later.
<pre class="wiki"> raise TypeError("start must be an integer, %s is not an integer"%start)
raise TypeError("stop must be an integer, %s is not an integer"%stop)
</pre></li></ol>
TicketkhalaszThu, 22 Nov 2012 05:26:36 GMT
https://trac.sagemath.org/ticket/13516#comment:25
https://trac.sagemath.org/ticket/13516#comment:25
<p>
Sorry for the delay. I've addressed the small comments.
</p>
TicketppurkaThu, 22 Nov 2012 06:19:29 GMTdescription changed; reviewer set
https://trac.sagemath.org/ticket/13516#comment:26
https://trac.sagemath.org/ticket/13516#comment:26
<ul>
<li><strong>reviewer</strong>
set to <em>Punarbasu Purkayastha</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/13516?action=diff&version=26">diff</a>)
</li>
</ul>
<p>
Thanks a lot for addressing my concerns. I have made some changes to your patch.
</p>
<ol><li>Fixed trailing whitespaces.
</li><li>Made sure <code>prime_powers(-1, positive integer)</code> works.
</li><li>Fixed <code>TypeError</code>.
</li></ol><p>
The changes can be seen in <a class="missing attachment">13516_reviewer.patch</a>. All these changes have been merged with your patch and the new patch is now <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/13516/13516_primepowers.2.patch" title="Attachment '13516_primepowers.2.patch' in Ticket #13516">13516_primepowers.2.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/13516/13516_primepowers.2.patch" title="Download"></a>.
</p>
<p>
Aside from the above corrections, the changes introduced by your patch has positive review from my side. If you think my changes are ok, feel free to change the ticket to positive review.
</p>
TicketppurkaThu, 22 Nov 2012 06:21:02 GMTreviewer changed
https://trac.sagemath.org/ticket/13516#comment:27
https://trac.sagemath.org/ticket/13516#comment:27
<ul>
<li><strong>reviewer</strong>
changed from <em>Punarbasu Purkayastha</em> to <em>Dmitrii Pasechnik, Punarbasu Purkayastha</em>
</li>
</ul>
TicketppurkaThu, 22 Nov 2012 06:23:35 GMTdescription changed
https://trac.sagemath.org/ticket/13516#comment:28
https://trac.sagemath.org/ticket/13516#comment:28
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/13516?action=diff&version=28">diff</a>)
</li>
</ul>
<p>
Argggh! Uploaded the wrong patch earlier X(
</p>
<p>
Patchbot: apply 13516_primepowers.2.patch
</p>
TicketkhalaszWed, 12 Dec 2012 02:03:00 GMTstatus changed
https://trac.sagemath.org/ticket/13516#comment:29
https://trac.sagemath.org/ticket/13516#comment:29
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Looks good to me. Thanks for your help/review!
</p>
TicketkcrismanWed, 12 Dec 2012 02:35:23 GMT
https://trac.sagemath.org/ticket/13516#comment:30
https://trac.sagemath.org/ticket/13516#comment:30
<p>
Nice work. Below, things almost certainly not worth addressing now that ppurka and khalasz have worked so hard to get this in, but I'll still point them out if ppurka is really bored and wants to fix them:
</p>
<ul><li>Typo
<pre class="wiki"># inserted to prevent an error from occuring
</pre></li><li>Might be worth using Python 3 string formatting in the error messages
</li><li>Conceivable to replace the reference to <a class="closed ticket" href="https://trac.sagemath.org/ticket/922" title="defect: [with patch] bug in prime_powers (closed: fixed)">#922</a> with a nice new <code>:trac:</code> thingie
</li></ul>
TicketppurkaWed, 12 Dec 2012 06:38:26 GMT
https://trac.sagemath.org/ticket/13516#comment:31
https://trac.sagemath.org/ticket/13516#comment:31
<p>
@kcrisman - fixed. Thanks. :)
</p>
TicketkcrismanWed, 12 Dec 2012 13:19:48 GMT
https://trac.sagemath.org/ticket/13516#comment:32
https://trac.sagemath.org/ticket/13516#comment:32
<p>
Ah, I knew I shouldn't have asked about this, because now of course I have to keep following up... you can't do
</p>
<pre class="wiki">sage: type(v[0]) # :trac:`922`
</pre><p>
and have it formatted, because it's in a literal block, it would have to be
</p>
<pre class="wiki">TESTS:
Check :trac:`922`is fixed::
sage: v = prime_powers(10)
sage: type(v[0])
<type 'sage.rings.integer.Integer'>
</pre><p>
or something like that. But I don't know if that's worth it...
</p>
TicketppurkaThu, 13 Dec 2012 03:44:31 GMTattachment set
https://trac.sagemath.org/ticket/13516
https://trac.sagemath.org/ticket/13516
<ul>
<li><strong>attachment</strong>
set to <em>13516_primepowers.2.patch</em>
</li>
</ul>
<p>
apply only this to devel/sage
</p>
TicketppurkaThu, 13 Dec 2012 03:44:50 GMT
https://trac.sagemath.org/ticket/13516#comment:33
https://trac.sagemath.org/ticket/13516#comment:33
<p>
Yes, you are right. I have reverted the last change.
</p>
TicketkcrismanThu, 13 Dec 2012 03:52:40 GMT
https://trac.sagemath.org/ticket/13516#comment:34
https://trac.sagemath.org/ticket/13516#comment:34
<blockquote class="citation">
<p>
Yes, you are right. I have reverted the last change.
</p>
</blockquote>
<p>
Sorry to be so picky, anyway nice work by both of you!
</p>
TicketppurkaThu, 13 Dec 2012 04:52:30 GMTreviewer changed
https://trac.sagemath.org/ticket/13516#comment:35
https://trac.sagemath.org/ticket/13516#comment:35
<ul>
<li><strong>reviewer</strong>
changed from <em>Dmitrii Pasechnik, Punarbasu Purkayastha</em> to <em>Dmitrii Pasechnik, Punarbasu Purkayastha, Karl-Dieter Crisman</em>
</li>
</ul>
<blockquote class="citation">
<p>
Sorry to be so picky, anyway nice work by both of you!
</p>
</blockquote>
<p>
No problem. But you do deserve to be in the reviewers list! ;)
</p>
TicketjdemeyerFri, 21 Dec 2012 09:31:49 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/13516#comment:36
https://trac.sagemath.org/ticket/13516#comment:36
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-5.6.beta1</em>
</li>
</ul>
Ticket