login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 self-inverse 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_{k-j}^e_a * p_{k-i}^e_b  * p_{k-h}^e_c * ... * p_{k-a}^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_(3-1) * p_3 = 3 * 5 = 15, thus a(10) = 15.

For n = 20 = 2*2*5 = p_1^2 * p_3^1, we get p_(3-1)^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_(4-2)^2 * p_(4-1) * 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) (set-car! 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 (fold-left (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! (fold-left (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 definec-macro from Antti Karttunen's IntSeq-library:

(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 4-group.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 17 06:34 EST 2019. Contains 319207 sequences. (Running on oeis4.)