

A048673


Permutation of natural numbers: a(n) = (A003961(n)+1) / 2 [where A003961(n) shifts the prime factorization of n one step towards larger primes].


125



1, 2, 3, 5, 4, 8, 6, 14, 13, 11, 7, 23, 9, 17, 18, 41, 10, 38, 12, 32, 28, 20, 15, 68, 25, 26, 63, 50, 16, 53, 19, 122, 33, 29, 39, 113, 21, 35, 43, 95, 22, 83, 24, 59, 88, 44, 27, 203, 61, 74, 48, 77, 30, 188, 46, 149, 58, 47, 31, 158, 34, 56, 138, 365, 60, 98, 36, 86, 73
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Inverse of sequence A064216 considered as a permutation of the positive integers.  Howard A. Landman, Sep 25 2001
From Antti Karttunen, Dec 20 2014: (Start)
Permutation of natural numbers obtained by replacing each prime divisor of n with the next prime and mapping the generated odd numbers back to all natural numbers by adding one and then halving.
Note: there is a 7cycle almost right in the beginning: (6 8 14 17 10 11 7). (See also comments at A249821. This 7cycle is endlessly copied in permutations like A250249/A250250.)
The only 3cycle in range 1 .. 402653184 is (2821 3460 5639).
For 1 and 2cycles, see A245449.
(End)
The first 5cycle is (1410, 2783, 2451, 2703, 2803).  Robert Israel, Jan 15 2015


LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Index entries for sequences that are permutations of the natural numbers


FORMULA

From Antti Karttunen, Dec 20 2014: (Start)
a(1) = 1; for n>1: If n = product_{k>=1} (p_k)^(c_k), then a(n) = (1/2) * (1 + product_{k>=1} (p_{k+1})^(c_k)).
a(n) = (A003961(n)+1) / 2.
a(n) = floor((A045965(n)+1)/2).
Other identities. For all n >= 1:
a(n) = A108228(n)+1.
a(n) = A243501(n)/2.
A108951(n) = A181812(a(n)).
a(A246263(A246268(n))) = 2*n.
As a composition of other permutations involving primeshift operations:
a(n) = A243506(A122111(n)).
a(n) = A243066(A241909(n)).
a(n) = A241909(A243062(n)).
a(n) = A244154(A156552(n)).
a(n) = A245610(A244319(n)).
a(n) = A227413(A246363(n)).
a(n) = A245612(A243071(n)).
a(n) = A245608(A245605(n)).
a(n) = A245610(A244319(n)).
a(n) = A249745(A249824(n)).
For n >= 2, a(n) = A245708(1+A245605(n1)).
(End)
From Antti Karttunen, Jan 17 2015: (Start)
We also have the following identities:
a(2n) = 3*a(n)  1. [Thus a(2n+1) = 0 or 1 when reduced modulo 3.]
a(3n) = 5*a(n)  2.
a(4n) = 9*a(n)  4.
a(5n) = 7*a(n)  3.
a(6n) = 15*a(n)  7.
a(7n) = 11*a(n)  5.
a(8n) = 27*a(n)  13.
a(9n) = 25*a(n)  12.
and in general:
a(x*y) = (A003961(x) * a(y))  a(x) + 1, for all x, y >= 1.
(End)


EXAMPLE

For n = 6, as 6 = 2 * 3 = prime(1) * prime(2), we have a(6) = ((prime(1+1) * prime(2+1))+1) / 2 = ((3 * 5)+1)/2 = 8.
For n = 12, as 12 = 2^2 * 3, we have a(12) = ((3^2 * 5) + 1)/2 = 23.


MAPLE

f:= proc(n)
local F, q, t;
F:= ifactors(n)[2];
(1 + mul(nextprime(t[1])^t[2], t = F))/2
end proc:
seq(f(n), n=1..1000); # Robert Israel, Jan 15 2015


MATHEMATICA

Table[(Times @@ Power[If[# == 1, 1, NextPrime@ #] & /@ First@ #, Last@ #] + 1)/2 &@ Transpose@ FactorInteger@ n, {n, 69}] (* Michael De Vlieger, Dec 18 2014, revised Mar 17 2016 *)


PROG

(Haskell)
a048673 = (`div` 2) . (+ 1) . a045965
 Reinhard Zumkeller, Jul 12 2012
(PARI)
A003961(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ Using code of Michel Marcus
A048673(n) = (A003961(n)+1)/2; \\ Antti Karttunen, Dec 20 2014
(Scheme) (define (A048673 n) (/ (+ 1 (A003961 n)) 2)) ;; Antti Karttunen, Dec 20 2014
(Python)
from sympy import factorint, nextprime
from operator import mul
def a(n):
f = factorint(n)
return 1 if n==1 else (1 + reduce(mul, [nextprime(i)**f[i] for i in f]))/2 # Indranil Ghosh, May 09 2017


CROSSREFS

Inverse: A064216.
Row 1 of A251722, Row 2 of A249822.
One more than A108228, half the terms of A243501.
Fixed points: A048674.
Positions of records: A029744, their values: A246360.
Positions of subrecords: A247283, their values: A247284.
Cf. A246351 (Numbers n such that a(n) < n.)
Cf. A246352 (Numbers n such that a(n) >= n.)
Cf. A246281 (Numbers n such that a(n) <= n.)
Cf. A246282 (Numbers n such that a(n) > n.), A252742 (their char. function)
Cf. A246261 (Numbers n for which a(n) is odd.)
Cf. A246263 (Numbers n for which a(n) is even.)
Cf. A246260 (a(n) reduced modulo 2.)
Cf. A246342 (Iterates starting from n=12.)
Cf. A246344 (Iterates starting from n=16.)
Cf. also A003961 (A045965), A108951, A245449, A249735, A249821, A250471, A250249, A250250.
Cf. A245447 (This permutation "squared", a(a(n)).)
Other permutations whose formulas refer to this sequence: A122111, A243062, A243066, A243500, A243506, A244154, A244319, A245605, A245608, A245610, A245612, A245708, A246265, A246267, A246268, A246363, A249745, A249824, A249826.
Sequence in context: A118317 A127522 A254103 * A288119 A292575 A096070
Adjacent sequences: A048670 A048671 A048672 * A048674 A048675 A048676


KEYWORD

nonn


AUTHOR

Antti Karttunen, Jul 14 1999


EXTENSIONS

New name and crossrefs to derived sequences added by Antti Karttunen, Dec 20 2014


STATUS

approved



