[math-fun] [seqfan] Signatures of irrational numbers

[Marc LeBrun]

 >=Kerry Mitchell <lkmitch at 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...