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

Marc LeBrun mlb at fxpt.com
Thu May 29 22:59:21 CEST 2003

``` >=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...

```