login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A075175 Prime factorization of n encoded by interleaving successive prime exponents in unary to bit-positions given by columns of A001477. 6
0, 1, 2, 5, 8, 3, 64, 37, 18, 9, 1024, 7, 32768, 65, 10, 549, 2097152, 19, 268435456, 13, 66, 1025, 68719476736, 39, 136, 32769, 274, 69, 35184372088832, 11, 36028797018963968, 16933, 1026, 2097153, 72, 23, 73786976294838206464 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,3
COMMENTS
Here 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 i-1 of A001477 viewed as a table (the exponent of 2 is thus stored to bit positions 0, 2, 5, 9, 14, 20, ..., exponent of 3 to 1, 4, 8, 13, 19, ..., exponent of 5 to 3, 7, 12, 18, 25, ...) using unary 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 power-set lattice P(X) of some set X. With this we can 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
EXAMPLE
a(24) = 39 because 24 = 2^3 * 3^1 so we add the binary words 100101 and 10 to get 100111 in binary = 39 in decimal and a(25) = 136 because 25 = 5^2 so we form a binary word 10001000 = 136 in decimal.
CROSSREFS
Variant: A075173. Inverse: A075176.
A003989(x, y) = A075176(A004198(a(x), a(y))), A003990(x, y) = A075176(A003986(a(x), a(y))).
Sequence in context: A162611 A152248 A248906 * A075173 A163337 A341488
KEYWORD
nonn
AUTHOR
Antti Karttunen, Sep 13 2002
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:56 EDT 2024. Contains 370952 sequences. (Running on oeis4.)