Add iterator method in QQ for Calkin-Wilf sequence

[bgillesp]

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:

• https://www.math.upenn.edu/~wilf/website/recounting.pdf
• https://oeis.org/A002487
• https://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree.

CC: @slel

Component: combinatorics

Keywords: sequence, iterator

Author: Bryan Gillespie

Branch/Commit: u/bgillespie/add_iterator_method_in_qq_for_calkin_wilf_sequence @ 9b82dac

Reviewer: Samuel Lelièvre

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

[bgillesp]

Branch: u/bgillespie/add_iterator_method_in_qq_for_calkin_wilf_sequence

[sagetrac-git]

Commit: 9b82dac

[sagetrac-git]

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

9b82dac

Add literature reference and improve performance

[bgillesp]

Author: Bryan Gillespie

[embray]

comment:4

Ticket retargeted after milestone closed

[mkoeppe]

comment:5

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.

[slel]

comment:6

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

[slel]

Reviewer: Samuel Lelièvre

[nbruin]

comment:7

We've been there already:

sagemath/sagetrac-mirror@45dc1b9/src/sage/rings/rational_field.py

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://github.com/sagemath/sagetrac-mirror/commits/55ad3590cb7d993f38c9104ea87da24b21567009

[slel]

comment:8

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?

[nbruin]

comment:9

Replying to @slel:

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.

[mkoeppe]

comment:11

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

[mkoeppe]

comment:12

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