

A075173


Prime factorization of n encoded by interleaving successive prime exponents in unary to bitpositions given by columns of A075300.


10



0, 1, 2, 5, 8, 3, 128, 21, 34, 9, 32768, 7, 2147483648, 129, 10, 85, 9223372036854775808, 35, 170141183460469231731687303715884105728, 13, 130, 32769
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

As in A059884, here also we store the exponent e_i of p_i (p1=2, p2=3, p3=5, ...) in the factorization of n to the bit positions given by the column i1 of A075300 (the exponent of 2 is thus stored to bit positions 0, 2, 4, ..., exponent of 3 to 1, 5, 9, 13, ..., exponent of 5 to 3, 11, 19, 27, 35, ...), but using unary instead of binary system, i.e. we actually store 2^(e_i)  1 in binary.
This injective mapping from N to N offers an example of the proof given in Cameron's book that any distributive lattice can be represented as a sublattice of the powerset lattice P(X) of some set X. This allows us to implement GCD (A003989) with bitwise AND (A004198) and LCM (A003990) with bitwise OR (A003986). Also, to test whether x divides y, it is enough to check that ((a(x) OR a(y)) XOR a(y)) = A003987(A003986(a(x),a(y)),a(y)) is zero.


REFERENCES

P. J. Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1998, page 191. (12.3. Distributive lattices)


LINKS

Table of n, a(n) for n=1..22.


EXAMPLE

a(24) = 23 because 24 = 2^3 * 3^1 so we add the binary words 10101 and 10 to get 10111 in binary = 23 in decimal and a(25) = 2056 because 25 = 5^2 so we form a binary word 100000001000 = 2056 in decimal.


CROSSREFS

Variant: A075175. Inverse: A075174. Cf. A059884.
A003989(x, y) = A075174(A004198(a(x), a(y))), A003990(x, y) = A075174(A003986(a(x), a(y))).
Sequence in context: A152248 A248906 A075175 * A163337 A341488 A114550
Adjacent sequences: A075170 A075171 A075172 * A075174 A075175 A075176


KEYWORD

nonn


AUTHOR

Antti Karttunen, Sep 13 2002


STATUS

approved



