Add iterator method in QQ for Calkin-Wilf sequence

[bgillespie]

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.

[git]

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

​9b82dac

Add literature reference and improve performance

[embray]

Ticket retargeted after milestone closed

[mkoeppe]

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.

[slelievre]

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

[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

[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?

[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.

[mkoeppe]

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

[mkoeppe]

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