[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...
More information about the SeqFan
mailing list