Some notes on the formulae of & correspondences between various bijections of natural numbers effected by manipulation of the exponents and indices of primes in their prime factorizations: A122111, A241909 & A241916. By Antti Karttunen (his-firstname.his-surname@gmail.com) May 19 2014. ----------------------------------------------------------------------------- A122111: Self-inverse permutation of the positive integers induced by partition enumeration in A112798 and partition conjugation. There are two formulations for this in terms of the prime factorization of n: Formula a: a(1) = 1, If n = p_i, then a(n) = 2^i, and otherwise, when n = q_i1 * q_i2 * q_i3 * ... * q_i{k-2} * q_i{k-1} * q_ik, where q_i1, q_i2, q_i3, ..., q_ik, are the primes present in the prime factorization of n, sorted into ascending order, but not necessarily distinct: i1 <= i2 <= i3 <= ... <= i_{k-2} <= i_{k-1} <= ik, with k = A0001222(n) and ik = A061395(n) (i.e. q_ik = A006530(n)). then a(n) = 2^(ik-i_{k-1}) * 3^(i_{k-1}-i_{k-2}) * ... * p_{k-1}^(i2-i1) * p_k^(i1). For n = 2^h = p_1 * p_1 * ... * p_1 (h times), this reduces to a(n) = 2^0 * 3^0 * 5^0 * ... * p_h^1 = p_h. Formula b: b(1) = 1, If n = 2^e, then a(n) = p_e, and otherwise, when n = 2^e1 * 3^e2 * ... * p_h^{e_h}, where e1 ... e_k are the exponents (some of them possibly zero, except the last, e_h) of the primes 2, 3, 5, ... in the prime factorization of n, with h = A061395(n) and p_h = A006530(n) then b(n) = p_{e_h} * p_{e_{h-1}+e_h} * ... * p_{e_2 + e_3 + ... + e_{h-1}+e_h} * p_{e_1 + e_2 + e_3 + ... + e_{h-1}+e_h}. Clearly, both formulas are well-defined on all positive natural numbers, and composing them either way, as a(b(n)) or b(a(n)), we easily arrive at the identity function, which shows that both a and b must be bijections, and indeed (proof omitted), they are the same self-inverse permutation of natural numbers, A122111(n) = a(n) = b(n). Furthermore, from the formula a we can form a following recurrence: a(1) = 1, and then either a(n) = A000079(A241917(n)) * A003961(a(A052126(n))). or the same in a slightly different guise ("batch mode operation"): a(n) = (A000040(A071178(n))^A241919(n)) * A242378(A071178(n), a(A051119(n))). In the latter recurrence ^ stands for the ordinary exponentiation, and the bivariate function A242378(k,n) changes each prime p(i) in the prime factorization of n to p(i+k), i.e. it's the result of A003961 iterated k times starting from n. From the formula b we can form a following recurrence: a(1) = 1, a(n) = A000040(A001222(n)) * a(A064989(n)). Please compare this to the formula for A242424, the Bulgarian Solitaire operation implemented on the same prime-index based encoding of partitions. ----------------------------------------------------------------------------- A241909: Permutation of natural numbers which maps between the partitions as ordered in A112798 and A241918. There are two formulations for this in terms of the prime factorization of n: Formula a: a(1) = 1, If n = p_i, then a(n) = 2^i, and otherwise, when n = q_i1 * q_i2 * q_i3 * ... * q_ik, where q_i1, q_i2, q_i3, ..., q_ik, are the primes present in the prime factorization of n, sorted into ascending order, but not necessarily distinct: i1 <= i2 <= i3 <= ... <= ik, with k = A0001222(n) and ik = A061395(n) (i.e. q_ik = A006530(n)) then a(n) = 2^(i1-1) * 3^(i2-i1) * 5^(i3-i2) * ... * p_k^(1+(ik-i_{k-1})). Formula b: b(1) = 1, If n = 2^e, then a(n) = p_e, and otherwise, when n = 2^e1 * 3^e2 * ... * p_h^{e_h}, where e1 ... e_h are the exponents (some of them possibly zero, except the last, e_h) of the primes 2, 3, 5, ... in the prime factorization of n, with h = A061395(n) and p_h = A006530(n) then b(n) = p_{1+e1} * p_{1+e1+e2} * ... * p_{1+e1+e2+...+e_h-1}. Clearly, both formulas are well-defined on all positive natural numbers, and composing them either way, as a(b(n)) or b(a(n)), we easily arrive at the identity function, which shows that both a and b must be bijections. Furthermore, we show that these bijections are actually same, that a(n) = b(n), and so a(a(n)) = n. We proceed by induction. Let's tackle first the case where we multiply n by its largest prime factor. We have: If n = q_i1 * q_i2 * q_i3 * ... * q_ik, then by the definition of formula a, a(n) = 2^(i1-1) * 3^(i2-i1) * ... * p_k^(1+(ik-i_{k-1})). and thus a(q_ik * n) = 2^(i1-1) * 3^(i2-i1) * ... * p_k^(ik-i_{k-1}) * p_{k+1}^(1). On the other hand, n can be written as: n = 2^e1 * 3^e2 * ... * p_h^{e_h}, and by the induction hypothesis, the result given by the formula b, b(n) = p_{1+e1} * p_{1+e1+e2} * ... * p_{e1+e2+...+e_h}. is assumed to be equivalent to the result given by the formula a: = 2^(i1-1) * 3^(i2-i1) * 5^(i3-i2) * ... * p_k^(1+(ik-i_{k-1})). from which also follows that p_{e1+e2+...+e_h} = p_k, the largest prime divisor of a(n) = b(n). or equally, e1+e2+...+e_h = k. We have b(q_ik * n) = b(p_h * n) = b(2^e1 * 3^e2 * ... * p_h^{e_h + 1}) = p_{1+e1} * p_{1+e1+e2} * ... * p_{1+e1+e2+...+e_{h-1}} * p_{e1+e2+...+e_{h-1}+e_h+1}. Because e1+e2+...+e_h = k (as seen above), the largest prime divisor of a(q_ik * n) = p_{k+1} and b(q_ik * n) = p_{e1+e2+...+e_h+1} are also equal here. The next to largest prime divisor of a(q_ik * n) = p_k^(ik-i_{k-1}) is present if ik > i_{k-1} that is, if n is not in A070003 (Numbers divisible by the square of their largest prime factor), i.e. e_h = 1. Then the next largest prime divisor of b(q_ik * n) = p_{1+e1+e2+...+e_{h-1}} = p_{e1+e2+...+e_{h-1}+e_h} which also matches, as we already saw above that e1+e2+...+e_h = k. -- On the other hand, if n is in A070003, that is e_h >= 2, then the next to largest prime divisor of a(q_ik * n) = 2^(i1-1) * 3^(i2-i1) * ... * p_k^(ik-i_{k-1}) * p_{k+1}^(1). is not p_k^(ik-i_{k-1}) (because it vanishes with zero exponent as i_k = i_{k-1}) and the next largest is the same as with a(n) = 2^(i1-1) * 3^(i2-i1) * ... * p_k^(1+(ik-i_{k-1})). and thus also by induction hypothesis the same as the next largest prime divisor of b(n) = p_{1+e1} * p_{1+e1+e2} * ... * p_{1+e1+e2+...+e_{h-1}} * p_{e1+e2+...+e_{h-1}+e_h}. (which is true because (e1+e2+...+e_{h-1}+e_h) > (1+e1+e2+...+e_{h-1}) as e_h > 1). ---- Let's then examine the case where we multiply n by a prime greater than its greatest prime factor. We have: If n = q_i1 * q_i2 * q_i3 * ... * q_ik, then by the definition of formula a, a(n) = 2^(i1-1) * 3^(i2-i1) * ... * p_k^(1+(ik-i_{k-1})). and thus, with im > ik, a(q_im * n) = 2^(i1-1) * 3^(i2-i1) * ... * p_k^(ik-i_{k-1}) * p_m^(1+(im-ik)). On the other hand, n can be written as: n = 2^e1 * 3^e2 * ... * p_h^{e_h}, and by the induction hypothesis, the result given by the formula b, b(n) = p_{1+e1} * p_{1+e1+e2} * ... * p_{e1+e2+...+e_h}. should be equivalent to the result given by the formula a: = 2^(i1-1) * 3^(i2-i1) * 5^(i3-i2) * ... * p_k^(1+(ik-i_{k-1})). from which also follows that p_{e1+e2+...+e_h} = p_k, the largest prime divisor of a(n) = b(n). or equally, e1+e2+...+e_h = k. We have b(q_im * n) = b(2^e1 * 3^e2 * ... * p_h^{e_h} * q_im) = p_{1+e1} * p_{1+e1+e2} * ... * p_{1+e1+e2+...+e_h} * p_{e1+e2+...+e_h+1}. Because e1+e2+...+e_h = k (as seen above), and q_im > p_h and its exponent is one, the largest prime divisor of a(q_im * n) = p_m [Where k = A001222(n) and m = k+1] and the largest prime divisor of b(q_im * n) = p_{e1+e2+...+e_h+1} are also equal here. The second to last prime in the multiset of prime factors of a(q_im * n) = p_m as (im-ik) >= 1, and the second to last prime in the multiset of prime factors of b(q_im * n) = p_{1+e1+e2+...+e_h} = p_{e1+e2+...+e_h+1} = p_m as well. If n is not in A070003 (Numbers divisible by the square of their largest prime factor), then the next to largest (distinct) prime divisor of a(q_im * n) = p_k, as p_k^(ik-i_{k-1}) is present if ik > i_{k-1} that is, if e_h = 1. Then the next largest prime divisor of b(q_im * n) = p_{1+e1+e2+...+e_{h-1}} = p_{e1+e2+...+e_{h-1}+e_h} which also matches, as we already saw above that e1+e2+...+e_h = k. -- On the other hand, if n is in A070003, that is e_h >= 2, then the next to largest prime divisor of a(q_im * n) = 2^(i1-1) * 3^(i2-i1) * ... * p_k^(ik-i_{k-1}) * p_m^(1+(im-ik)). is not p_k^(ik-i_{k-1}) (because it vanishes with zero exponent as i_k = i_{k-1}) and the next largest is the same as with a(n) = 2^(i1-1) * 3^(i2-i1) * ... * p_k^(1+(ik-i_{k-1})). and thus also by induction hypothesis the same as the next largest prime divisor of b(n) = p_{1+e1} * p_{1+e1+e2} * ... * p_{1+e1+e2+...+e_{h-1}} * p_{e1+e2+...+e_{h-1}+e_h}. (which is true because (e1+e2+...+e_{h-1}+e_h) > (1+e1+e2+...+e_{h-1}) as e_h > 1). Thus we have proved that A241909(A241909(n)) = n holds for all n. Furthermore, from the formula a we can form a following recurrence: a(1) = 1, a(p_k) = 2^k for primes with index k, otherwise a(n) = (A000040(A001222(n))^(A241917(n)+1)) * A052126(a(A052126(n))). From the formula b we can form a following recurrence: a(1) = 1, and for n>1, if n = 2^k, a(n) = A000040(k), otherwise a(n) = A000040(A001511(n)) * A242378(A007814(n), a(A064989(n))). ----------------------------------------------------------------------------- A241916: Permutation of natural numbers, composition of A122111 & A241909: a(n) = A122111(A241909(n)). Working out from the formulation b of A241909 and the formulation a of A122111, one easily obtains the following formulation for this sequence: a(n) = A122111(A241909(n)) => a(2^k) = 2^k, and for other numbers reverse the sequence of powers in the prime factorization of n, except that the exponents of 2 and largest prime dividing n are adjusted by one: If n = 2^e1 * 3^e2 * 5^e3 * ... p_k^e_k, then a(n) = 2^(e_k - 1) * 3^(e_{k-1}) * ... * p_{k-1}^e2 * p_k^(e1+1). On the other hand, if we compose them the other way, a(n) = A241909(A122111(n)). and apply the formulation b of A122111 and the formulation a of A241909, we obtain the same result. Thus A122111 & A241909 as both are involutions (self-inverse, max cycle length = 2), as as they commute with each other, their composition must be an involution as well, which can also be seen directly from the above reduced formula of A241916, as it is just a reversal of prime exponents with a slight twist. Thus the following four permutations of natural numbers: {A000027, A122111, A241909, A241916} form a Klein four-group: http://en.wikipedia.org/wiki/Klein_four-group