Inspired by A059884.

Antti Karttunen karttu at
Sun Sep 15 19:54:23 CEST 2002

Here is Marc's A059884:

ID Number: A059884
Sequence:  0,1,2,4,8,3,128,5,32,9,32768,6,2147483648,129,10,16,
Name:      Prime factorization of n encoded by recursively interleaving bits of
              successive prime exponents.
Comments:  For n=2^e0*3^e1*5^e2... the alternate (i.e. 2^0,2,4...) bit
              positions of a(n) give e0, the alternate *remaining* bit positions
              (i.e. 2^1,5,9...) give e1, the *remaining* alternates (i.e.
              2^3,11,19...) give e2, and so on. (Any finite vector of nonnegative
              integers can be uniquely encoded this way.) Every nonnegative integer
              appears exactly once in this sequence-despite its outlandish
              behavior: the next term, a(29) is 2^511 (which has 153 digits),
              followed by a(30)=11...
           Inverse of sequence A059900 considered as a permutation of the
              nonnegative integers. - Howard A. Landman (howard at,
              Sep 25 2001
Links:     Index entries for sequences that are permutations of the natural numbers
Example:   a(360)=a(2^3 * 3^2 * 5^1)=45 thus: ...0 0 0 0 0 0 1 1 -> 3 from 2^3 ...0 0 1 0
              -> 2 from 3^2 ...0 1 -> 1 from 5^1 ...00000101101 == 45.
See also:  Cf. A075173, A075300, A075302.
Keywords:  easy,nonn
Offset:    1
Author(s): Marc LeBrun (mlb at, Feb 06 2001

A quiz: Why it is better to use unary, instead of the binary encoding
here, when exponents are stored to their respective interleaved
bit positions? (Of course we lose the one-to-one mapping then,
but we gain something else...)

The answer is in A075173, and A075175 is a variant that shows
that there's actually nothing magical about just those bit positions,
but instead, any NxN <-> N bijection can be used for selecting
them. I don't know how this idea can be developed further, e.g.
regarding the Moebius inversion formula (on various lattices),
and what's the connection with Marc's MASK transform, and other ideas.


Antti Karttunen

More information about the SeqFan mailing list