Opened 3 years ago
Closed 2 years ago
#25983 closed enhancement (fixed)
Document that divisors are returned sorted in increasing order
Reported by:  zimmerma  Owned by:  

Priority:  trivial  Milestone:  sage8.7 
Component:  basic arithmetic  Keywords:  divisors, sorted 
Cc:  slelievre  Merged in:  
Authors:  Samuel Lelièvre  Reviewers:  Jeroen Demeyer 
Report Upstream:  N/A  Work issues:  
Branch:  580b9a1 (Commits, GitHub, GitLab)  Commit:  580b9a1c22bd6eee8ede915730d5875306480964 
Dependencies:  Stopgaps: 
Description (last modified by )
Initial report:
The output of
divisors(n)
for integern
appears to be sorted.If true, this should be documented, so users don't unnecessarily call
sorted(divisors(n))
.Same for
prime_divisors
andsquarefree_divisors
.
It turns out that for integer n
, both divisors(n)
and prime_divisors(n)
are sorted in increasing order.
On the other hand, for squarefree_divisors(n)
the order comes from
using powerset of the list of prime divisors of n
and in general will
not coincide with the increasing order.
This ticket makes sure the documentation documents that.
Change History (23)
comment:1 Changed 3 years ago by
 Branch set to u/slelievre/enhance_documentation_of_divisors
comment:2 Changed 3 years ago by
 Commit set to 7fe6d3243d8ddd52272a8abc9a083f005960405f
 Description modified (diff)
 Keywords divisors sorted added
 Status changed from new to needs_review
 Summary changed from enhance documentation of divisors to Document that divisors are returned sorted in increasing order
comment:3 Changed 3 years ago by
 Description modified (diff)
comment:4 Changed 3 years ago by
Question: Should we sort them? I understand the purpose of sorting them for doctest output, but how often is it useful to go through them in sorted order? In the same vein, would it be useful to have a pure iterator variant?
comment:5 Changed 3 years ago by
I strongly support adding an iterator variant, either here or in a separate ticket.
comment:6 Changed 3 years ago by
About iterators, see also this Ask Sage question:
comment:7 Changed 3 years ago by
 Status changed from needs_review to needs_work
I suggest removing the sorting in the generic case.
comment:8 Changed 3 years ago by
I agree some applications don't need the divisors sorted, and those that need it can easily use sorted(divisors(...))
.
comment:9 followups: ↓ 10 ↓ 11 Changed 3 years ago by
How about an optional argument sorted
defaulting to False
?
comment:10 in reply to: ↑ 9 Changed 3 years ago by
Replying to slelievre:
How about an optional argument
sorted
defaulting toFalse
?
that would be a good solution.
comment:11 in reply to: ↑ 9 Changed 3 years ago by
Replying to slelievre:
How about an optional argument
sorted
defaulting toFalse
?
I wonder to what purpose? Is there any advantage over sorting afterwards?
comment:12 Changed 3 years ago by
 Cc slelievre added
 Milestone changed from sage8.4 to sage8.5
 Status changed from needs_work to needs_review
This ticket was opened to document that divisors are returned sorted in increasing order.
Should we review that, and open one (ore more) followup ticket(s) to
 make
divisors
andprime_divisors
return unsorted output by default  provide an iterator variant for
divisors
andprime_divisors
I'm also happy if this ticket is repurposed to something more useful... but I would not know where to start for that, and I'm afraid this stays stalled.
comment:14 Changed 2 years ago by
 Description modified (diff)
 Milestone changed from sage8.5 to sagewishlist
comment:15 Changed 2 years ago by
 Branch changed from u/slelievre/enhance_documentation_of_divisors to u/slelievre/t25983saydivisorsaresorted
 Commit changed from 7fe6d3243d8ddd52272a8abc9a083f005960405f to 6e1c2f79aa97a98b1148e77d94b0d7ffcb09774f
 Status changed from needs_work to needs_review
Rebased on SageMath 8.6.rc0. Please review.
New commits:
6e1c2f7  #25983 Say divisors are returned sorted

comment:16 Changed 2 years ago by
This is wrong:
Return the list of all divisors (up to units) of this element of a unique factorization domain, sorted in increasing order.
In general, there is no guarantee of sorting (it wouldn't make sense either: how would you sort elements of an arbitrary ring?). It is sorted for integers.
comment:17 Changed 2 years ago by
 Status changed from needs_review to needs_work
Same issue in the other changed documentation: the generic functions don't guarantee any kind of sorting. Only specific implementations like for Integer
do sort.
comment:18 Changed 2 years ago by
 Commit changed from 6e1c2f79aa97a98b1148e77d94b0d7ffcb09774f to 580b9a1c22bd6eee8ede915730d5875306480964
Branch pushed to git repo; I updated commit sha1. New commits:
580b9a1  #25983 Squarefree divisors not in increasing order

comment:19 followup: ↓ 20 Changed 2 years ago by
 Description modified (diff)
 Milestone changed from sagewishlist to sage8.7
 Status changed from needs_work to needs_review
Thanks for these comments. I took them into account.
For squarefree_divisors(n)
the order comes from using powerset of
the list of prime divisors of n
and in general will not coincide with
the increasing order.
For example, the list of prime divisors of 30 is [2, 3, 5], and the
powers can be [0, 0, 0], [1, 0, 0], [0, 1, 0], [1, 1, 0], [0, 0, 1], [1, 0, 1],
[0, 1, 1], [1, 1, 1], giving the squarefree divisors 1, 2, 3, 6, 5, 10, 15, 30.
The order that squarefree divisors of an integer are returned in can be described as follows.
Denote by p
the list of prime divisors of n
sorted in increasing order,
and let k = len(p)
; then there are 2^k
squarefree divisors of n
to list.
Let s
be their list, so that these divisors are s[j]
for j
ranging from
0
to 2^k  1
.
If b
is the bit sequence corresponding to j
,
so that j = sum(2^b[i] for i in range(k))
,
then s[j] = prod(p[i]^b[i] for i in range(k))
.
Should this be stated in the documentation?
New commits:
580b9a1  #25983 Squarefree divisors not in increasing order

comment:20 in reply to: ↑ 19 Changed 2 years ago by
Replying to slelievre:
Should this be stated in the documentation?
Please no. If we document it, it means that we cannot change the order in the future.
comment:21 Changed 2 years ago by
 Reviewers set to Jeroen Demeyer
 Status changed from needs_review to positive_review
comment:22 Changed 2 years ago by
Thanks for the review!
In the current implementation, squarefree divisors of n
are
yielded in increasing order exactly when each prime divisor of n
is greater than the product of the smaller prime divisors of n
.
comment:23 Changed 2 years ago by
 Branch changed from u/slelievre/t25983saydivisorsaresorted to 580b9a1c22bd6eee8ede915730d5875306480964
 Resolution set to fixed
 Status changed from positive_review to closed
Tentative documentation improvement. Please review.
New commits:
Document that divisors are returned ordered