|
|
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 7-cycle almost right in the beginning: (6 8 14 17 10 11 7). (See also comments at A249821. This 7-cycle is endlessly copied in permutations like A250249/A250250.)
The only 3-cycle in range 1 .. 402653184 is (2821 3460 5639).
(End)
The first 5-cycle 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 5-cycles.
(10242, 20479, 21413, 29245, 30275, 40354, 48241) is another 7-cycle. (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 prime-shift 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^2-p)/(p^2-nextprime(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
|
|
|
|