Inspired by A059884.
Antti Karttunen
karttu at megabaud.fi
Sun Sep 15 19:54:23 CEST 2002
Here is Marc's A059884:
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=059884
ID Number: A059884
Sequence: 0,1,2,4,8,3,128,5,32,9,32768,6,2147483648,129,10,16,
9223372036854775808,33,
170141183460469231731687303715884105728,12,130,32769
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 polyamory.org),
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 well.com), 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.
Yours,
Antti Karttunen
More information about the SeqFan
mailing list