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