=Kerry Mitchell <lkmitch@att.net> [...] For a positive irrational number x, form the numbers y = i + j*x, where i and j are both positive integers. Since x is irrational, no 2 y values will be the same for different i and j. Arrange the ys by size... What about the j sequence? ... Why is the signature the i sequence as opposed to the j sequence?
Funny you should mention it, since I just gave a talk that touched on this, but with a twist... Instead of throwing away the js try mapping the pairs 1-1 into integers (i,j)-->n. Many different pair mapping patterns, such as the common "anti-diagonal scan", can be used. My current favorite mapping is n = A(i) + 2 A(j), where A is the Moser-de Bruijn sequence, Sloane's A000695 0 1 4 5 16 17 20 21 64 65... (which I notate 2[n]4, meaning "replace 2 with 4 in the binary expansion of n"). This particular mapping just "interleaves the bits" of i and j. If you visit the pairs in n-order it too traces a nice connected fractal path. Whatever mapping you choose, you can then sort the integers n via the ordering of the y[n] values. The resulting sequence, a permutation of the integers, is a "signature" that's characteristic of x. For example with the above mapping and x = sqrt 2 I get 0 1 2 4 3 8 5 6 9 16... (not yet in OEIS, sorry). I too would be very interested in an efficient algorithm to generate the i+jx in order. (I currently just kludgily generate "enough" pairs to make sure I don't miss any sequence elements, then sort--yuck). Anyway, besides giving signature sequences, this information-conserving pair mapping approach also enables interesting abstract-arithmetic games for quadratic x: just write the "numbrals" [n] for the objects y[n]. For any given mapping scheme the addition table is independent of x while multiplication is characteristic. This generalizes to algebraic x by extending pairs to tuples, and so on...