

A242415


Reverse the deltas of indices of distinct primes in the prime factorization of n.


8



1, 2, 3, 4, 5, 6, 7, 8, 9, 15, 11, 12, 13, 35, 10, 16, 17, 18, 19, 45, 21, 77, 23, 24, 25, 143, 27, 175, 29, 30, 31, 32, 55, 221, 14, 36, 37, 323, 91, 135, 41, 105, 43, 539, 20, 437, 47, 48, 49, 75, 187, 1573, 53, 54, 33, 875, 247, 667, 59, 60, 61, 899, 63, 64, 65
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

This selfinverse permutation (involution) of natural numbers preserves both the total number of prime divisors and the (index of) largest prime factor of n, i.e. for all n it holds that A001222(a(n)) = A001222(n) and A006530(a(n)) = A006530(n) [equally: A061395(a(n)) = A061395(n)]. It also preserves the exponent of the largest prime: A053585(a(n)) = A053585(n).
From the above it follows, that this fixes prime powers (A000961), among other numbers.
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 reverses the order of horizontal line segments of the "steps" in Young (or Ferrers) diagram of a partition, but keeps the order of vertical line segments intact. Please see the last example in the example section and compare also to the comments given in A242419.


LINKS

Antti Karttunen, Table of n, a(n) for n = 1..8192
Wikipedia, Young diagram
Index entries for sequences that are permutations of the natural numbers


FORMULA

If n = p_a^e_a * p_b^e_b * ... * p_h^e_h * p_i^e_i * p_j^e_j * p_k^e_k, where p_a < ... < p_k are distinct primes (sorted into ascending order) in the prime factorization of n, and e_a .. e_k are their nonzero exponents, then a(n) = p_{kj}^e_a * p_{ki}^e_b * p_{kh}^e_c * ... * p_{ka}^e_j * p_k^e_k.
As a recurrence: a(1) = 1, and for n>1, a(n) = (A000040(A241919(n))^A067029(n)) * A242378(A241919(n), a(A051119(A225891(n)))).
By composing/conjugating related permutations:
a(n) = A069799(A242419(n)) = A242419(A069799(n)).
a(n) = A122111(A069799(A122111(n))) = A153212(A069799(A153212(n))).


EXAMPLE

For n = 10 = 2*5 = p_1 * p_3, we get p_(31) * p_3 = 3 * 5 = 15, thus a(10) = 15.
For n = 20 = 2*2*5 = p_1^2 * p_3^1, we get p_(31)^2 * p_3^1 = 3^2 * 5 = 45, thus a(20) = 45.
For n = 84 = 2*2*3*7 = p_1^2 * p_2 * p_4, when we reverse the deltas of indices, but keep the exponents same, we get p_(42)^2 * p_(41) * p_4 = p_2^2 * p_3 * p_4 = 3^2 * 5 * 7 = 315, thus a(84) = 315.
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:
_
 
 
 _ _
 
 _ _
_ _ _ _ _
Reversing the order of horizontal line segment lengths (1,2,2) to (2,2,1), but keeping the order of vertical line segment lengths as (3,2,1), we get a new Young diagram
_ _
 
 
 _ _
 
 _
_ _ _ _ _
which represents the partition (2,2,2,4,4,5), encoded in A112798 by p_2^3 * p_4^2 * p_5^1 = 3^3 * 7^2 * 11 = 14553, thus a(2200) = 14553.


PROG

(MIT/GNU Scheme, with Aubrey Jaffer's SLIB Scheme library)
(require 'factor)
(define (A242415 n) (if (<= n 1) n (let* ((pfs (ifactor n))) (apply * (map expt (map A000040 (revdeltas (map A049084 (uniq pfs)))) (multiplicities pfs))))))
(define (ifactor n) (cond ((< n 2) (list)) (else (sort (factor n) <))))
(define (uniq lista) (let loop ((lista lista) (z (list))) (cond ((null? lista) (reverse! z)) ((and (pair? z) (equal? (car z) (car lista))) (loop (cdr lista) z)) (else (loop (cdr lista) (cons (car lista) z))))))
(define (multiplicities lista) (let loop ((mults (list)) (lista lista) (prev #f)) (cond ((not (pair? lista)) (reverse! mults)) ((equal? (car lista) prev) (setcar! mults (+ 1 (car mults))) (loop mults (cdr lista) prev)) (else (loop (cons 1 mults) (cdr lista) (car lista))))))
(define (revdeltas ints) (partsums (reverse (diff1 ints)))) ;; Maybe possible with just one fold?
(define (diff1 ints) (reverse (foldleft (lambda (xs x) (cons ( x (apply + xs)) xs)) '() ints))) ;; Take the first elem of ints followed by its first differences
(define (partsums a) (cdr (reverse! (foldleft (lambda (psums n) (cons (+ n (car psums)) psums)) (list 0) a)))) ;; Partial sums from left to right.
;; Alternative implementation based on the recurrence, and utilizing memoizing definecmacro from Antti Karttunen's IntSeqlibrary:
(definec (A242415 n) (cond ((<= n 1) n) (else (* (expt (A000040 (A241919 n)) (A067029 n)) (A242378bi (A241919 n) (A242415 (A051119 (A225891 n))))))))


CROSSREFS

Fixed points: A242413.
Cf. A112798, A122111, A153212, A000040, A241919, A067029, A242378, A051119, A225891.
{A000027, A069799, A242415, A242419} form a 4group.
Sequence in context: A032579 A151543 A222261 * A242420 A242419 A073526
Adjacent sequences: A242412 A242413 A242414 * A242416 A242417 A242418


KEYWORD

nonn


AUTHOR

Antti Karttunen, May 24 2014


STATUS

approved



