

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].


185



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

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).
(End)
The first 5cycle is (1410, 2783, 2451, 2703, 2803).  Robert Israel, Jan 15 2015
(5194, 5356, 6149, 8186, 10709), (46048, 51339, 87915, 102673, 137205) and (175811, 200924, 226175, 246397, 267838) are other 5cycles.
(10242, 20479, 21413, 29245, 30275, 40354, 48241) is another 7cycle. (End)
Somewhat artificially, also this permutation can be represented as a binary tree. Each child to the left is obtained by multiplying the parent by 3 and subtracting one, while each child to the right is obtained by applying A253888 to the parent:
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
etc.
Each node's (> 1) parent can be obtained with A253889. Sequences A292243, A292244, A292245 and A292246 are constructed from the residues (mod 3) of the vertices encountered on the path from n to the root (1).
(End)


LINKS



FORMULA

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)).
Other identities. For all n >= 1:
As a composition of other permutations involving primeshift operations:
(End)
We also have the following identities:
a(2n) = 3*a(n)  1. [Thus a(2n+1) = 0 or 1 when reduced modulo 3. See A341346]
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)
(End)
Sum_{k=1..n} a(k) ~ c * n^2, where c = (1/4) * Product_{p prime} ((p^2p)/(p^2nextprime(p))) = 1.0319981... , where nextprime is A151800.  Amiram Eldar, Jan 18 2023


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:


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
(PARI)
A003961(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ From A003961
(Python)
from sympy import factorint, nextprime, prod
def a(n):
f = factorint(n)
return 1 if n==1 else (1 + prod(nextprime(i)**f[i] for i in f))//2 # Indranil Ghosh, May 09 2017


CROSSREFS

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. A246342 (Iterates starting from n=12.)
Cf. A246344 (Iterates starting from n=16.)
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, and also A183209, A254103 that are somewhat similar.


KEYWORD

nonn


AUTHOR



EXTENSIONS

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


STATUS

approved



