Do these questions bear on the sequence generated by Broadway as it cuts across the rectangular grid of Manhattan? (Assuming that the tangent of the angle of Broadway is irrational...) At 01:59 PM 5/29/03 -0700, Marc LeBrun wrote:
=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...