Opened 15 months ago

Closed 9 months ago

#25983 closed enhancement (fixed)

Document that divisors are returned sorted in increasing order

Reported by: zimmerma Owned by:
Priority: trivial Milestone: sage-8.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) Commit: 580b9a1c22bd6eee8ede915730d5875306480964
Dependencies: Stopgaps:

Description (last modified by slelievre)

Initial report:

The output of divisors(n) for integer n appears to be sorted.

If true, this should be documented, so users don't unnecessarily call sorted(divisors(n)).

Same for prime_divisors and squarefree_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 14 months ago by slelievre

  • Branch set to u/slelievre/enhance_documentation_of_divisors

comment:2 Changed 14 months ago by slelievre

  • 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

Tentative documentation improvement. Please review.


New commits:

7fe6d32Document that divisors are returned ordered

comment:3 Changed 14 months ago by slelievre

  • Authors set to Samuel Lelièvre
  • Description modified (diff)

comment:4 Changed 14 months ago by tscrim

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 14 months ago by slelievre

I strongly support adding an iterator variant, either here or in a separate ticket.

comment:6 Changed 14 months ago by slelievre

About iterators, see also this Ask Sage question:

comment:7 Changed 14 months ago by jdemeyer

  • Status changed from needs_review to needs_work

I suggest removing the sorting in the generic case.

Last edited 14 months ago by jdemeyer (previous) (diff)

comment:8 Changed 14 months ago by zimmerma

I agree some applications don't need the divisors sorted, and those that need it can easily use sorted(divisors(...)).

comment:9 follow-ups: Changed 12 months ago by slelievre

How about an optional argument sorted defaulting to False?

comment:10 in reply to: ↑ 9 Changed 12 months ago by zimmerma

Replying to slelievre:

How about an optional argument sorted defaulting to False?

that would be a good solution.

comment:11 in reply to: ↑ 9 Changed 12 months ago by mantepse

Replying to slelievre:

How about an optional argument sorted defaulting to False?

I wonder to what purpose? Is there any advantage over sorting afterwards?

comment:12 Changed 12 months ago by slelievre

  • Cc slelievre added
  • Milestone changed from sage-8.4 to sage-8.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) follow-up ticket(s) to

  • make divisors and prime_divisors return unsorted output by default
  • provide an iterator variant for divisors and prime_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.

Last edited 9 months ago by slelievre (previous) (diff)

comment:13 Changed 9 months ago by jdemeyer

  • Status changed from needs_review to needs_work

Merge failure

comment:14 Changed 9 months ago by slelievre

  • Description modified (diff)
  • Milestone changed from sage-8.5 to sage-wishlist

comment:15 Changed 9 months ago by slelievre

  • Branch changed from u/slelievre/enhance_documentation_of_divisors to u/slelievre/t-25983-say-divisors-are-sorted
  • 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
Last edited 9 months ago by slelievre (previous) (diff)

comment:16 Changed 9 months ago by jdemeyer

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 9 months ago by jdemeyer

  • 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 9 months ago by git

  • 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 follow-up: Changed 9 months ago by slelievre

  • Description modified (diff)
  • Milestone changed from sage-wishlist to sage-8.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 9 months ago by jdemeyer

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 9 months ago by jdemeyer

  • Reviewers set to Jeroen Demeyer
  • Status changed from needs_review to positive_review

comment:22 Changed 9 months ago by slelievre

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 9 months ago by vbraun

  • Branch changed from u/slelievre/t-25983-say-divisors-are-sorted to 580b9a1c22bd6eee8ede915730d5875306480964
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.