The "?" in "? + Wilf" is Neil Calkin. Jim Propp On Thursday, November 19, 2015, Tom Duff <td@pixar.com> wrote:
On Thu, 19 Nov 2015, Eric Angelini wrote:
I was looking for a way to represent any fraction
with one single integer.
Stern's "diatomic sequence" ( https://oeis.org/A002487 , also called the Stern-Brocot sequence) has the feature that f(n)/f(n+1) includes every rational number exactly once. The sequence is pretty easy to compute:
f(0)=0 f(1)=1 f(2n)=f(n) f(2n+1)=f(n)+f(n+1)
So you can represent rational numbers with indices into the sequence: if you specify n, I compute f(n)/f(n+1).
The first few entries in the sequence are 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3
E.W. Dijkstra wrote a couple of notes about this sequence (EWD570, EWD578, available here: https://www.cs.utexas.edu/users/EWD/transcriptions/EWD05xx/EWD570.html https://www.cs.utexas.edu/users/EWD/transcriptions/EWD05xx/EWD578.html ), which he called fusc(n). Unless I missed it, he never mentioned that it enumerates the rationals.
-- Tom Duff. Form follows malfunction.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun