|
|
A153212
|
|
A permutation of the natural numbers: in the prime factorization of n, swap each prime's index difference (from the previous distinct prime that divides n) and the prime's power.
|
|
6
|
|
|
1, 2, 4, 3, 8, 6, 16, 5, 9, 18, 32, 15, 64, 54, 12, 7, 128, 10, 256, 75, 36, 162, 512, 35, 27, 486, 25, 375, 1024, 30, 2048, 11, 108, 1458, 24, 21, 4096, 4374, 324, 245, 8192, 150, 16384, 1875, 45, 13122, 32768, 77, 81, 50, 972, 9375, 65536, 14, 72, 1715, 2916, 39366, 131072, 105, 262144, 118098, 225, 13
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
In order for the "index difference" to make sense, we consider the factorization to be sorted with respect to the primes but not the powers to which they are raised; that is, first comes the smallest prime and each subsequent prime is larger than the previous disregarding their powers.
For every n it is true that a(a(n)) = n.
In other words, this is a self-inverse permutation (involution) of natural numbers.
This permutation maps primes (A000040) to the powers of two larger than one (A000079(n>=1)) and vice versa.
The term a(1) = 1 was added on the grounds that as 1 has an empty prime factorization, there is nothing to swap, thus it stays same. It is also needed as a base case for the given recurrence.
Considered as a function on partitions encoded by the indices of primes in the prime factorization of n (as in table A112798), this implements an operation which exchanges the horizontal and vertical line segment of each "step" in Young (or Ferrers) diagram of a partition. Please see the last example in the example section.
(End)
|
|
LINKS
|
|
|
FORMULA
|
Denote the i-th prime with p(i): p(1)=2, p(2)=3, p(3)=5, p(4)=7, etc. Let n = p(a1)^b1 * p(a2)^b2 * ... * p(ak)^bk is the factorization of n where p(i)^j is the i-th prime raised to power j. As mentioned above, we assume that the primes are sorted, i.e., a1 < a2 < a3 ... < ak. Then a(n) = p(c1)^d1 * p(c2)^d2 * ... * p(ck)^dk where c1 = b1 and c(i) = b(i) + c(i-1) for i > 1 d1 = a1 and d(i) = a(i) - a(i-1) for i > 1.
(End)
|
|
EXAMPLE
|
For n = 10 we have 10 = 2^1 * 5^1 = p(1)^1 * p(3)^1 then a(10) = p(1)^1 * p(2)^2 = 2^1 * 3^2 = 18.
For n = 18 we have 18 = 2^1 * 3^2 = p(1)^1 * p(2)^2 then a(18) = p(1)^1 * p(3)^1 = 2^1 * 5^1 = 10.
For n = 19 we have 19 = 19^1 = p(8)^1 then a(19) = p(1)^8 = 2^8 = 256.
For n = 2200, we see that it encodes the partition (1,1,1,3,3,5) in A112798 as 2200 = p_1 * p_1 * p_1 * p_3 * p_3 * p_5 = 2^3 * 5^2 * 11. This in turn corresponds to the following Young diagram in French notation:
_
| |
| |
| |_ _
| |
| |_ _
|_ _ _ _ _|
Exchanging the order of the horizontal and vertical line segment of each "step", results the following Young diagram:
_ _ _
| |_ _
| |
| |_
| |
|_ _ _ _ _ _|
which represents the partition (3,5,5,6,6), encoded in A112798 by p_3 * p_5^2 * p_6^2 = 5 * 11^2 * 13^2 = 102245, thus a(2200) = 102245.
|
|
PROG
|
(PARI) a(n) = {my(f = factor(n)); my(g = f); for (i=1, #f~, if (i==1, g[i, 1] = prime(f[i, 2]), g[i, 1] = prime(f[i, 2]+ primepi(g[i-1, 1]))); if (i==1, g[i, 2] = primepi(f[i, 1]), g[i, 2] = primepi(f[i, 1]) - primepi(f[i-1, 1])); ); factorback(g); } \\ Michel Marcus, Dec 16 2014
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Luchezar Belev (l_belev(AT)yahoo.com), Dec 20 2008
|
|
EXTENSIONS
|
Term a(1)=1 prepended, and also more terms computed by Antti Karttunen, May 16 2014
|
|
STATUS
|
approved
|
|
|
|