Opened 3 years ago

Last modified 7 weeks ago

#28282 needs_work enhancement

Add iterator method in QQ for Calkin-Wilf sequence

Reported by: bgillespie Owned by:
Priority: minor Milestone: sage-9.7
Component: combinatorics Keywords: sequence, iterator
Cc: slelievre Merged in:
Authors: Bryan Gillespie Reviewers: Samuel Lelièvre
Report Upstream: N/A Work issues:
Branch: u/bgillespie/add_iterator_method_in_qq_for_calkin_wilf_sequence (Commits, GitHub, GitLab) Commit: 9b82daceade1a4ab1cedbe13d1c1d2cb61aa39ea
Dependencies: Stopgaps:

Status badges

Description

Add a method to the set of rational numbers to produce an iterator for the Calkin-Wilf sequence, an explicit ordering of the positive rationals with some interesting features. Background:

Change History (14)

comment:1 Changed 3 years ago by bgillespie

  • Branch set to u/bgillespie/add_iterator_method_in_qq_for_calkin_wilf_sequence

comment:2 Changed 3 years ago by git

  • Commit set to 9b82daceade1a4ab1cedbe13d1c1d2cb61aa39ea

Branch pushed to git repo; I updated commit sha1. New commits:

9b82dacAdd literature reference and improve performance

comment:3 Changed 3 years ago by bgillespie

  • Authors set to Bryan Gillespie
  • Status changed from new to needs_review

comment:4 Changed 2 years ago by embray

  • Milestone changed from sage-8.9 to sage-9.1

Ticket retargeted after milestone closed

comment:5 Changed 2 years ago by mkoeppe

  • Milestone changed from sage-9.1 to sage-9.2

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

comment:6 Changed 21 months ago by slelievre

  • Cc slelievre added
  • Reviewers set to Samuel Lelièvre
  • Status changed from needs_review to needs_work

That would be a nice addition!

The branch needs rebasing. In addition I suggest considering these minor changes:

-        p, q = ZZ(1), ZZ(1)
+        p = q = ZZ.one()
         if all_rationals:
-            yield self(0)
+            yield self.zero()
             while True:
-                yield self(p / q)
-                yield -self(p / q)
+                yield self((p, q))
+                yield self((-p, q))
                 p, q = q, 2 * (p // q) * q - p + q
         else:
             while True:
-                yield self(p / q)
+                yield self((p, q))
                 p, q = q, 2 * (p // q) * q - p + q

comment:7 Changed 21 months ago by nbruin

We've been there already:

https://git.sagemath.org/sage.git/commit/src/sage/rings/rational_field.py?h=45dc1b94996b609a039531a64a81279892bb7c2d

It's indeed a cute sequence. The generating formula is surprisingly simple, but most problems that require iterating over the rationals are better served by another order (indeed, it's since been replaced by iteration by height):

https://git.sagemath.org/sage.git/commit/?h=55ad3590cb7d993f38c9104ea87da24b21567009

Last edited 21 months ago by nbruin (previous) (diff)

comment:8 follow-up: Changed 21 months ago by slelievre

Thanks @nbruin for pointing out the initial iterator for QQ used this sequence, and for the pointers to the commits implementing it and then replacing it with a better default.

This ticket aims to provide a Calkin-Wilf iterator as distinct from the standard iterator for QQ.

Would you advise against it? Would this Calkin-Wilf iterator better be given as an example in the tutorial on iterators? Maybe with a reference from the documentation of QQ?

comment:9 in reply to: ↑ 8 Changed 21 months ago by nbruin

Replying to slelievre:

Thanks @nbruin for pointing out the initial iterator for QQ used this sequence, and for the pointers to the commits implementing it and then replacing it with a better default.

This ticket aims to provide a Calkin-Wilf iterator as distinct from the standard iterator for QQ.

Would you advise against it? Would this Calkin-Wilf iterator better be given as an example in the tutorial on iterators? Maybe with a reference from the documentation of QQ?

I'd think so. The formula is exceedingly simple: see the original implementation that was essentially a one-liner.

I was originally enthusiastic when I learned about the formula, but I don't think the sequence really has wider applications. Including it would be more of encyclopedic interest, and I think QQ is not the right place for that. We already have OEIS. Interfacing with that makes more sense. There is in fact a (lousy) sage program listed there. It would make a lot more sense if there were an iterator there.

comment:10 Changed 19 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:11 Changed 15 months ago by mkoeppe

  • Milestone changed from sage-9.3 to sage-9.4

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

comment:12 Changed 10 months ago by mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5

Setting a new milestone for this ticket based on a cursory review.

comment:13 Changed 5 months ago by mkoeppe

  • Milestone changed from sage-9.5 to sage-9.6

comment:14 Changed 7 weeks ago by mkoeppe

  • Milestone changed from sage-9.6 to sage-9.7
Note: See TracTickets for help on using tickets.