Cheers, 20 new pre-numbered sequences A075157 - A075176
follow, and nothing else.
Note: I did add "nice" to A075166 by myself.
(Of course it is inspired by Jon Awbrey's Riff & Rotes thread).
I leave it upto you whether A075173 and A075175 are also nice.
Yours,
Antti
%I A075157
%S A075157 0,1,2,3,5,4,8,7,11,14,6,9,17,24,26,15,23,44,34,29,13,10,20,19,35,74,48,49,53,124,80,31,47,
%T A075157 134,174,89,69,76,104,59,27,32,12,21,41,54,62,39,71,224,244,149,97,120,146,99,107,374,342,249,
%U A075157 161,624,242,63,95,404,874,269,349,538,524,179,139,230,142,153,209,384,314,119,55,98,64,65
%N A075157 Run lengths in the binary expansion of n gives the vector of exponents in prime factorization of a(n)+1, with the least significant run corresponding to the exponent of the least prime, 2.
%C A075157 To make this a permutation of non-negative integers, we subtract one from each run count except for the most significant run, e.g. a(11) = 9, as 11 = 1011, and 9+1 = 10 = 5^1 * 3^(1-1) * 2^(2-1).
%R A075157
%H A075157 Index entries for sequences that are permutations of the natural numbers
%O A075157 0,3
%K A075157 nonn,new
%A A075157 Antti Karttunen (my_firstname.my_surname@iki.fi) Sep 13 2002
%Y A075157 Inverse of A075158. a(n) = A075159(n+1)-1. a(A000975(n)) = A006093(n) = A000040(n)-1. Cf. A008578, A056539, A059900, A075162.
%D A075157
%o A075157 (MIT Scheme with Aubrey Jaffer's SLIB library:)
%o A075157 (require 'factor)
%o A075157 (define (A075157 n) (-1+ (binruns->primefactorization n)))
%o A075157 (define (binruns->primefactorization n) (let loop ((n n) (i 0) (p (modulo (1+ n) 2)) (z 1)) (cond ((zero? n) (* z (A008578 i))) ((= (modulo n 2) p) (loop (floor->exact (/ n 2)) i (modulo n 2) (* z (A008578 i)))) (else (loop (floor->exact (/ n 2)) (1+ i) (modulo n 2) z)))))
%o A075157 (define (A008578 n) (cond ((< n 3) (1+ n)) (else (list-ref (primes> 0 n) (-1+ n)))))
%I A075158
%S A075158 0,1,2,3,5,4,10,7,6,11,21,8,42,20,9,15,85,12,170,23,22,43,341,16,13,84,14,40,682,19,1365,31,
%T A075158 41,171,18,24,2730,340,86,47,5461,44,10922,87,17,683,21845,32,26,27,169,168,43690,28,45,80,
%U A075158 342,1364,87381,39,174762,2731,46,63,82,83,349525,343,681,36,699050,48,1398101,5460,25,680
%N A075158 Prime factorization of n+1 encoded with the run lengths of binary expansion.
%e A075158 a(1) = 1 as 2 = 2^1, a(2) = 2 (10 in binary) as 3 = 3^1 * 2^0, a(3) = 3 (11) as 4 = 2^2, a(4) = 5 (101) as 5 = 5^1 * 3^0 * 2^0, a(5) = 4 (100) as 6 = 3^1 * 2^1, a(8) = 6 (110) as 9 = 3^2 * 2^0, a(11) = 8 (1000) as 12 = 3^1 * 2^2, a(89) = 35 (100011) as 90 = 5^1 * 3^2 * 2^1, a(90) = 90 (1011010) as 91 = 13^1 * 11^0 * 7^1 * 5^0 * 3^0 * 2^0.
%e A075158 The binary expansion of a(n) begins from the left with as many 1's as is the exponent of the largest prime present in the factorization of n+1, and from then on follows runs of ej+1 zeros and ones alternatively, where ej are the corresponding exponents of the successively lesser primes (0 if that prime does not divide n+1).
%C A075158 a(2n) = 1 or 2 mod 4 and a(2n+1) = 0 or 3 mod 4 for all n > 1
%R A075158
%H A075158 Index entries for sequences that are permutations of the natural numbers
%O A075158 0,3
%K A075158 nonn,new
%A A075158 Antti Karttunen (my_firstname.my_surname@iki.fi) Sep 13 2002
%Y A075158 Inverse of A075157. a(n) = A075160(n+1)-1. a(A006093(n)) = A000975(n). Cf. A059884.
%D A075158
%p A075158
%I A075159
%S A075159 1,2,3,4,6,5,9,8,12,15,7,10,18,25,27,16,24,45,35,30,14,11,21,20,36,75,49,50,54,125,81,32,48,
%T A075159 135,175,90,70,77,105,60,28,33,13,22,42,55,63,40,72,225,245,150,98,121,147,100,108,375,343,
%U A075159 250,162,625,243,64,96,405,875,270,350,539,525,180,140,231,143,154,210,385,315,120,56,99,65
%N A075159 Run lengths in the binary expansion of n-1 gives the vector of exponents in prime factorization of a(n), with the least significant run corresponding to the exponent of the least prime, 2.
%C A075159 To make this a permutation of non-negative integers, we subtract one from each run count except for the most significant run, e.g. a(12) = 10, as 12-1 = 11 = 1011, and 10 = 5^1 * 3^(1-1) * 2^(2-1).
%R A075159
%H A075159 Index entries for sequences that are permutations of the natural numbers
%O A075159 1,2
%K A075159 nonn,new
%A A075159 Antti Karttunen (my_firstname.my_surname@iki.fi) Sep 13 2002
%Y A075159 Inverse of A075160. a(n) = A075157(n-1)+1.
%D A075159
%p A075159
%I A075160
%S A075160 1,2,3,4,6,5,11,8,7,12,22,9,43,21,10,16,86,13,171,24,23,44,342,17,14,85,15,41,683,20,1366,32,
%T A075160 42,172,19,25,2731,341,87,48,5462,45,10923,88,18,684,21846,33,27,28,170,169,43691,29,46,81,
%U A075160 343,1365,87382,40,174763,2732,47,64,83,84,349526,344,682,37,699051,49,1398102,5461,26,681
%N A075160 Prime factorization of n encoded with the run lengths of binary expansion + 1.
%e A075160 a(9) = 7 = 1+6 (1 + 110) as 9 = 3^2 * 2^(1-1). (The run lengths of 6, 110 in binary are 2 and 1).
%C A075160 See the comment at A075158.
%R A075160
%H A075160 Index entries for sequences that are permutations of the natural numbers
%O A075160 1,2
%K A075160 nonn,new
%A A075160 Antti Karttunen (my_firstname.my_surname@iki.fi) Sep 13 2002
%Y A075160 Inverse of A075159. a(n) = A075158(n-1)+1.
%D A075160
%p A075160
%I A075161
%S A075161 0,1,2,3,4,5,9,7,6,10,23,12,65,24,11,8,197,15,626,26,25,66,2056,13,14,198,16,68,6918,29,23714,
%T A075161 17,67,627,28,40,82500,2057,199,27,290512,71,1033412,200,30,6919,3707852,31,37,38,628,629,13402697,
%U A075161 43,70,69,2058,23715,48760367,82,178405157,82501,72,18,202,203,656043857,2059,6920,80,2423307047
%N A075161 Position of A075165(n+1) in A014486.
%C A075161 See A075166.
%R A075161
%H A075161 A. Karttunen, Alternative Catalan Orderings (With the complete Scheme source)
%H A075161 Index entries for sequences that are permutations of the natural numbers
%O A075161 0,3
%K A075161 nonn,new
%A A075161 Antti Karttunen (my_firstname.my_surname@iki.fi) Sep 13 2002
%Y A075161 Inverse of A075162. a(n) = A075163(n+1)-1. Cf. A075168.
%D A075161
%o A075161 (Scheme functions showing the essential idea. For the complete source, follow the "Alternative Catalan Orderings" link:)
%o A075161 (define (A075161 n) (CatalanRankGlobal (parenthesization->binexp (primefactorization->parenthesization (1+ n)))))
%o A075161 (define (primefactorization->parenthesization n) (map primefactorization->parenthesization (explist->Nvector! (primefactorization->explist n))))
%o A075161 ;; Function primefactorization->explist maps 1 to (), 2 to (1), 3 to (1 0), 4 to (2), 12 to (1 2), etc.
%o A075161 (define (explist->Nvector! el) (cond ((pair? el) (let loop ((el (cdr el))) (cond ((pair? el) (set-car! el (1+ (car el))) (loop (cdr el))))))) el)
%I A075162
%S A075162 0,1,2,3,4,5,8,7,15,6,9,14,11,23,24,17,26,31,63,80,511,255,65535,10,13,20,19,39,34,29,44,47,
%T A075162 95,134,767,383,98303,48,49,74,35,71,124,53,242,127,1023,728,32767,4095,16777215,624,161,19682,
%U A075162 33554431,262143,6560,134217727,4294967295,18446744073709551615,43046720,2417851639229258349412351
%N A075162 Position of A014486(n) in A075165, minus one.
%C A075162 See A075166.
%R A075162
%H A075162 A. Karttunen, Alternative Catalan Orderings (With the complete Scheme source)
%H A075162 Index entries for sequences that are permutations of the natural numbers
%O A075162 0,3
%K A075162 nonn,new
%A A075162 Antti Karttunen (my_firstname.my_surname@iki.fi) Sep 13 2002
%Y A075162 Inverse of A075161. a(n) = A075164(n+1)-1. Cf. A075157, A075169.
%D A075162
%o A075162 (Scheme functions showing the essential idea. For the complete source, follow the "Alternative Catalan Orderings" link:)
%o A075162 (define (A075162 n) (-1+ (parenthesization->primefactorization (binexp->parenthesization (A014486 n)))))
%o A075162 (define (parenthesization->primefactorization p) (Nvector->primefactorization! (map parenthesization->primefactorization p)))
%o A075162 (define (Nvector->primefactorization! el) (let loop ((el (reverse! el)) (i 1) (z 1)) (cond ((null? el) z) ((null? (cdr el)) (* (expt (A008578 i) (car el)) z)) (else (loop (cdr el) (1+ i) (* (expt (A008578 i) (-1+ (car el))) z))))))
%I A075163
%S A075163 1,2,3,4,5,6,10,8,7,11,24,13,66,25,12,9,198,16,627,27,26,67,2057,14,15,199,17,69,6919,30,23715,
%T A075163 18,68,628,29,41,82501,2058,200,28,290513,72,1033413,201,31,6920,3707853,32,38,39,629,630,13402698,
%U A075163 44,71,70,2059,23716,48760368,83,178405158,82502,73,19,203,204,656043858,2060,6921,81,2423307048
%N A075163 Position of A075165(n) in A014486 plus one.
%C A075163 See A075166.
%R A075163
%H A075163 Index entries for sequences that are permutations of the natural numbers
%O A075163 1,2
%K A075163 nonn,new
%A A075163 Antti Karttunen (my_firstname.my_surname@iki.fi) Sep 13 2002
%Y A075163 Inverse of A075164. a(n) = A075161(n-1)+1.
%D A075163
%p A075163
%I A075164
%S A075164 1,2,3,4,5,6,9,8,16,7,10,15,12,24,25,18,27,32,64,81,512,256,65536,11,14,21,20,40,35,30,45,48,
%T A075164 96,135,768,384,98304,49,50,75,36,72,125,54,243,128,1024,729,32768,4096,16777216,625,162,19683,
%U A075164 33554432,262144,6561,134217728,4294967296,18446744073709551616,43046721,2417851639229258349412352
%N A075164 Position of A014486(n-1) in A075165.
%C A075164 See A075166.
%R A075164
%H A075164 Index entries for sequences that are permutations of the natural numbers
%O A075164 1,2
%K A075164 nonn,new
%A A075164 Antti Karttunen (my_firstname.my_surname@iki.fi) Sep 13 2002
%Y A075164 Inverse of A075163. a(n) = A075162(n-1)+1.
%D A075164
%p A075164
%I A075165
%S A075165 0,2,10,12,42,44,170,52,50,172,682,180,2730,684,178,56,10922,204,43690,692,690,2732,174762,
%T A075165 184,202,10924,210,2740,699050,716,2796202,212,2738,43692,714,820,11184810,174764,10930,696,
%U A075165 44739242,2764,178956970,10932,722,699052,715827882,724,810,812,43698,43700,2863311530,844
%N A075165 Sequence A075166 interpreted as binary numbers and converted to decimal.
%R A075165
%O A075165 1,2
%K A075165 nonn,new
%A A075165 Antti Karttunen (my_firstname.my_surname@iki.fi) Sep 13 2002
%Y A075165 Permutation of A014486. Same sequence shown in binary: A075166. The binary width of each term / 2 is given by A075167.
%D A075165
%p A075165
%I A075166
%S A075166 0,10,1010,1100,101010,101100,10101010,110100,110010,10101100,1010101010,10110100,101010101010,
%T A075166 1010101100,10110010,111000,10101010101010,11001100,1010101010101010,1010110100,1010110010,
%U A075166 101010101100,101010101010101010,10111000,11001010,10101010101100,11010010,101010110100,10101010101010101010
%N A075166 Natural numbers mapped to Dyck path encodings of the rooted plane trees obtained by recursing on the exponents of the prime factorization of n.
%e A075166 The rooted plane trees encoded here are:
%e A075166 .....................o...............o.........o...o..o.......
%e A075166 .....................|...............|..........\./...|.......
%e A075166 .......o....o...o....o....o.o.o..o...o.o.o.o.o...o....o...o...
%e A075166 .......|.....\./.....|.....\|/....\./...\|.|/....|.....\./....
%e A075166 @......@......@......@......@......@......@......@......@.....
%e A075166 1......2......3......4......5......6......7......8......9.....
%C A075166 Note that we recurse on the exponent + 1 for all other primes except the largest one in the factorization. Thus for 6 = 3^1 * 2^1 we construct a tree by joining trees 1 and 2 with a new root node, for 7 = 7^1 * 5^0 * 3^0 * 2^0 we join four 1-trees (single leaves) with a new root node, for 8 = 2^3 we add a single edge below tree 3, and for 9 = 3^2 * 2^0 we join trees 2 and 1, to get the mirror image of tree 6. Compare to Matula/Göbel numbering of (unoriented) rooted trees as explained in A061773.
%R A075166
%H A075166 A. Karttunen, Alternative Catalan Orderings (With the complete Scheme source)
%O A075166 1,2
%K A075166 nonn,nice,new
%A A075166 Antti Karttunen (my_firstname.my_surname@iki.fi) Sep 13 2002
%Y A075166 Permutation of A063171. Same sequence shown in decimal: A075165. The digital length of each term / 2 (the number of o-nodes in the corresponding trees) is given by A075167. Cf. A075171, A007088.
%D A075166
%o A075166 (Scheme functions showing the essential idea. For the complete source, follow the "Alternative Catalan Orderings" link:)
%o A075166 (define (A075166 n) (A007088 (parenthesization->binexp (primefactorization->parenthesization n))))
%o A075166 (define (primefactorization->parenthesization n) (map primefactorization->parenthesization (explist->Nvector! (primefactorization->explist n))))
%o A075166 ;; Function primefactorization->explist maps 1 to (), 2 to (1), 3 to (1 0), 4 to (2), 12 to (1 2), etc.
%o A075166 (define (explist->Nvector! el) (cond ((pair? el) (let loop ((el (cdr el))) (cond ((pair? el) (set-car! el (1+ (car el))) (loop (cdr el))))))) el)
%I A075167
%S A075167 0,1,2,2,3,3,4,3,3,4,5,4,6,5,4,3,7,4,8,5,5,6,9,4,4,7,4,6,10,5,11,4,6,8,5,5,12,9,7,5,
%T A075167 13,6,14,7,5,10,15,5,5,5,8,8,16,5,6,6,9,11,17,6,18,12,6,4,7,7,19,9,10,6,20,5,21,13,5,10,6,8,
%U A075167 22,6,4,14,23,7,8,15,11,7,24,6,7,11,12,16,9,5,25,6,7,6,26,9,27,8,6,17,28,6,29,7,13,7,30,10
%N A075167 The number of edges in each rooted plane tree produced with the prime factorization unranking algorithm presented in A075166.
%C A075167 Also the digital length of A075166(n)/ 2. Each value v occurs A000108(v) times.
%R A075167
%O A075167 1,3
%K A075167 nonn,new
%A A075167 Antti Karttunen (my_firstname.my_surname@iki.fi) Sep 13 2002
%Y A075167 Permutation of A072643.
%D A075167
%p A075167
%I A075168
%S A075168 0,1,2,3,5,4,6,7,12,11,9,10,15,14,16,8,13,30,28,29,24,23,25,26,40,39,37,38,43,42,19,18,32,33,
%T A075168 84,85,80,79,81,82,68,67,65,66,71,70,72,27,41,114,112,113,108,107,109,110,124,123,121,122,52,
%U A075168 51,47,17,31,89,93,94,254,253,255,256,242,241,239,240,245,244,246,83,69,204,202,203,198,197
%N A075168 Position of A075170(n) in A014486.
%C A075168 See A075171.
%R A075168
%O A075168 0,3
%K A075168 nonn,new
%A A075168 Antti Karttunen (my_firstname.my_surname@iki.fi) Sep 13 2002
%Y A075168 Inverse of A075169.
%D A075168
%o A075168 (define (A075168 n) (CatalanRankGlobal (parenthesization->binexp (binruns->parenthesization n))))
%I A075169
%S A075169 0,1,2,3,5,4,6,7,15,10,11,9,8,16,13,12,14,63,31,30,127,255,65535,21,20,22,23,47,18,19,17,64,
%T A075169 32,33,128,256,65536,26,27,25,24,48,29,28,126,2047,4095,62,1023,511,131071,61,60,254,16383,
%U A075169 8191,510,32767,18446744073709551615,4294967295,131070,2147483647,340282366920938463463374607431768211455
%N A075169 Position of A014486(n) in A075170.
%C A075169 See A075171.
%R A075169
%O A075169 0,3
%K A075169 nonn,new
%A A075169 Antti Karttunen (my_firstname.my_surname@iki.fi) Sep 13 2002
%Y A075169 Inverse of A075168.
%D A075169
%o A075169 (define (A075169 n) (parenthesization->binruns (binexp->parenthesization (A014486 n))))
%I A075170
%S A075170 0,2,10,12,44,42,50,52,180,178,170,172,204,202,210,56,184,722,714,716,684,682,690,692,820,818,
%T A075170 810,812,844,842,226,216,728,738,2890,2892,2860,2858,2866,2868,2740,2738,2730,2732,2764,2762,
%U A075170 2770,696,824,3282,3274,3276,3244,3242,3250,3252,3380,3378,3370,3372,908,906,866,212,724,2914
%N A075170 Sequence A075171 interpreted as binary numbers and converted to decimal.
%R A075170
%O A075170 0,2
%K A075170 nonn,new
%A A075170 Antti Karttunen (my_firstname.my_surname@iki.fi) Sep 13 2002
%Y A075170 Permutation of A014486. Same sequence shown in binary: A075171. The binary width of each term / 2 is given by A075172.
%D A075170
%o A075170 (define (A075170 n) (parenthesization->binexp (binruns->parenthesization n)))
%I A075171
%S A075171 0,10,1010,1100,101100,101010,110010,110100,10110100,10110010,10101010,10101100,11001100,11001010,
%T A075171 11010010,111000,10111000,1011010010,1011001010,1011001100,1010101100,1010101010,1010110010,
%U A075171 1010110100,1100110100,1100110010,1100101010,1100101100,1101001100,1101001010,11100010,11011000
%N A075171 Non-negative integers mapped to Dyck path encodings of the rooted plane trees obtained by recursing on the run lengths of the binary expansion of n.
%e A075171 The rooted plane trees encoded here are:
%e A075171 .....................o........o.........o......o...o...
%e A075171 .....................|........|.........|.......\./....
%e A075171 .......o....o...o....o....o...o..o.o.o..o...o....o.....
%e A075171 .......|.....\./.....|.....\./....\|/....\./.....|.....
%e A075171 @......@......@......@......@......@......@......@.....
%e A075171 0......1......2......3......4......5......6......7.....
%e A075171 Note that we recurse on the run length - 1, thus for 4 = 100 in binary, we construct a tree by joining trees 0 (= 1-1) and 1 (= 2-1) respectively from left to right. For 5 (101) we construct a tree by joining three copies of tree 0 (a single leaf) with a new root node. For 6 (110) we join trees 1 and 0 to get a mirror image of tree 4. For 7 (111) we just add a new root node below tree 2.
%R A075171
%H A075171 A. Karttunen, Alternative Catalan Orderings (With the complete Scheme source)
%O A075171 0,2
%K A075171 nonn,new
%A A075171 Antti Karttunen (my_firstname.my_surname@iki.fi) Sep 13 2002
%Y A075171 Permutation of A063171. Same sequence shown in decimal: A075170. The digital length of each term / 2 (the number of o-nodes in the corresponding trees) is given by A075172. Cf. A075166, A007088.
%D A075171
%o A075171 (Scheme functions showing the essential idea. For the complete source, follow the "Alternative Catalan Orderings" link:)
%o A075171 (define (A075171 n) (A007088 (parenthesization->binexp (binruns->parenthesization n))))
%o A071571 (define (binruns->parenthesization n) (map binruns->parenthesization (map -1+ (binexp->runcount1list n))))
%o A075171 (define (binexp->runcount1list n) (if (zero? n) (list) (let loop ((n n) (rc (list)) (count 0) (prev-bit (modulo n 2))) (if (zero? n) (cons count rc) (if (eq? (modulo n 2) prev-bit) (loop (floor->exact (/ n 2)) rc (1+ count) (modulo n 2)) (loop (floor->exact (/ n 2)) (cons count rc) 1 (modulo n 2)))))))
%I A075172
%S A075172 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,3,4,5,5,5,5,5,5,5,5,5,5,5,5,5,4,4,5,5,6,6,6,6,6,6,
%T A075172 6,6,6,6,6,6,6,5,5,6,6,6,6,6,6,6,6,6,6,6,5,5,5,4,5,6,6,6,7,7,7,7,7,7,7,7,7,7,7,6,
%U A075172 6,7,7,7,7,7,7,7,7,7,7,7,7,7,6,6,6,6,7,7,7,7,7,7,7,7,7,7,7,7,7,6,6,7,7,7,7,7,7,7
%N A075172 The number of edges in each rooted plane tree produced with the binary run length unranking algorithm presented in A075171.
%C A075172 Also the digital length of A075171(n)/ 2. Each value v occurs A000108(v) times.
%R A075172
%O A075172 0,3
%K A075172 nonn,new
%A A075172 Antti Karttunen (my_firstname.my_surname@iki.fi) Sep 13 2002
%Y A075172 Permutation of A072643.
%D A075172
%p A075172
%I A075173
%S A075173 0,1,2,5,8,3,128,21,34,9,32768,7,2147483648,129,10,85,9223372036854775808,35,170141183460469231731687303715884105728,
%T A075173 13,130,32769,57896044618658097711785492504343953926634992332820282019728792003956564819968,23,2056,2147483649,546,133,
%U A075173 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503042048
%N A075173 Prime factorization of n encoded by interleaving successive prime exponents in unary to bit-positions given by columns of A075300.
%R A075173
%C A075173 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 i-1 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.
%C A075173 This injective mapping from N to N offers an example of the proof shown 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. 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's enough to check that ((a(x) OR a(y)) XOR a(y)) = A003987(A003986(a(x),a(y)),a(y)) is zero.
%e A075173 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.
%D A075173 P. J. Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1998, page 191. (12.3. Distributive lattices)
%O A075173 1,3
%K A075173 nonn,new
%A A075173 Antti Karttunen (my_firstname.my_surname@iki.fi) Sep 13 2002
%Y A075173 Variant: A075175. Inverse: A075174. Cf. A059884.
%Y A075173 A003989(x,y) = A075174(A004198(a(x),a(y))), A003990(x,y) = A075174(A003986(a(x),a(y)))
%p A075173
%I A075174
%S A075174 1,2,3,6,0,4,0,12,5,10,15,30,0,20,0,60,0,0,0,0,0,8,0,24,0,0,0,0,0,40,0,120,0,0,9,18,0,0,0,36,
%T A075174 0,0,45,90,0,0,0,180,0,0,0,0,0,0,0,72,0,0,0,0,0,0,0,360,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
%U A075174 0,0,0,0,0,16,0,48,0,0,0,0,0,80,0,240,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,144
%N A075174 Inverse function of N -> N injection A075173.
%C A075174 a(n) = 0 for those n which do not occur as the values of A075173. All positive natural numbers occur here once.
%R A075174
%O A075174 0,2
%K A075174 nonn
%A A075174 Antti Karttunen (my_firstname.my_surname@iki.fi) Sep 13 2002
%Y A075174 a(A075173(n)) = n for all n >= 1. Differs from A075176 first time at a(18) = 0, while A075176(18) = 9.
%D A075174
%p A075174
%I A075175
%S A075175 0,1,2,5,8,3,64,37,18,9,1024,7,32768,65,10,549,2097152,19,268435456,13,66,1025,68719476736,
%T A075175 39,136,32769,274,69,35184372088832,11,36028797018963968,16933,1026,2097153,72,23,73786976294838206464,
%U A075175 268435457,32770,45,302231454903657293676544,67,2475880078570760549798248448,1029,26,68719476737
%N A075175 Prime factorization of n encoded by interleaving successive prime exponents in unary to bit-positions given by columns of A001477.
%C A075175 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.
%C A075175 This injective mapping from N to N offers an example of the proof shown 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's enough to check that ((a(x) OR a(y)) XOR a(y)) = A003987(A003986(a(x),a(y)),a(y)) is zero.
%e A075175 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.
%R A075175
%D A075175 P. J. Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1998, page 191. (12.3. Distributive lattices)
%O A075175 1,3
%K A075175 nonn,new
%A A075175 Antti Karttunen (my_firstname.my_surname@iki.fi) Sep 13 2002
%Y A075175 Variant: A075173. Inverse: A075176.
%Y A075175 A003989(x,y) = A075176(A004198(a(x),a(y))), A003990(x,y) = A075176(A003986(a(x),a(y)))
%D A075175
%p A075175
%I A075176
%S A075176 1,2,3,6,0,4,0,12,5,10,15,30,0,20,0,60,0,0,9,18,0,0,0,36,0,0,45,90,0,0,0,180,0,0,0,0,0,8,0,
%T A075176 24,0,0,0,0,0,40,0,120,0,0,0,0,0,0,0,72,0,0,0,0,0,0,0,360,7,14,21,42,0,28,0,84,35,70,105,210,
%U A075176 0,140,0,420,0,0,63,126,0,0,0,252,0,0,315,630,0,0,0,1260,0,0,0,0,0,56,0,168,0,0,0,0,0,280,0
%N A075176 Inverse function of N -> N injection A075175.
%C A075176 a(n) = 0 for those n which do not occur as the values of A075175. All positive natural numbers occur here once.
%R A075176
%O A075176 0,2
%K A075176 nonn,new
%A A075176 Antti Karttunen (my_firstname.my_surname@iki.fi) Sep 13 2002
%Y A075176 a(A075175(n)) = n for all n >= 1. Differs from A075174 first time at a(18) = 9, while A075174(18) = 0.
%D A075176
%p A075176