|
%I #115 Jan 18 2023 02:21:08
%S 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,
%T 63,50,16,53,19,122,33,29,39,113,21,35,43,95,22,83,24,59,88,44,27,203,
%U 61,74,48,77,30,188,46,149,58,47,31,158,34,56,138,365,60,98,36,86,73
%N Permutation of natural numbers: a(n) = (A003961(n)+1) / 2 [where A003961(n) shifts the prime factorization of n one step towards larger primes].
%C Inverse of sequence A064216 considered as a permutation of the positive integers. - _Howard A. Landman_, Sep 25 2001
%C From _Antti Karttunen_, Dec 20 2014: (Start)
%C 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.
%C 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.)
%C The only 3-cycle in range 1 .. 402653184 is (2821 3460 5639).
%C For 1- and 2-cycles, see A245449.
%C (End)
%C The first 5-cycle is (1410, 2783, 2451, 2703, 2803). - _Robert Israel_, Jan 15 2015
%C From _Michel Marcus_, Aug 09 2020: (Start)
%C (5194, 5356, 6149, 8186, 10709), (46048, 51339, 87915, 102673, 137205) and (175811, 200924, 226175, 246397, 267838) are other 5-cycles.
%C (10242, 20479, 21413, 29245, 30275, 40354, 48241) is another 7-cycle. (End)
%C From _Antti Karttunen_, Feb 10 2021: (Start)
%C 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:
%C 1
%C |
%C ................../ \..................
%C 2 3
%C 5......../ \........4 8......../ \........6
%C / \ / \ / \ / \
%C / \ / \ / \ / \
%C / \ / \ / \ / \
%C 14 13 11 7 23 9 17 18
%C 41 10 38 12 32 28 20 15 68 25 26 63 50 16 53 19
%C etc.
%C 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).
%C (End)
%H Reinhard Zumkeller, <a href="/A048673/b048673.txt">Table of n, a(n) for n = 1..10000</a>
%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>.
%F From _Antti Karttunen_, Dec 20 2014: (Start)
%F 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)).
%F a(n) = (A003961(n)+1) / 2.
%F a(n) = floor((A045965(n)+1)/2).
%F Other identities. For all n >= 1:
%F a(n) = A108228(n)+1.
%F a(n) = A243501(n)/2.
%F A108951(n) = A181812(a(n)).
%F a(A246263(A246268(n))) = 2*n.
%F As a composition of other permutations involving prime-shift operations:
%F a(n) = A243506(A122111(n)).
%F a(n) = A243066(A241909(n)).
%F a(n) = A241909(A243062(n)).
%F a(n) = A244154(A156552(n)).
%F a(n) = A245610(A244319(n)).
%F a(n) = A227413(A246363(n)).
%F a(n) = A245612(A243071(n)).
%F a(n) = A245608(A245605(n)).
%F a(n) = A245610(A244319(n)).
%F a(n) = A249745(A249824(n)).
%F For n >= 2, a(n) = A245708(1+A245605(n-1)).
%F (End)
%F From _Antti Karttunen_, Jan 17 2015: (Start)
%F We also have the following identities:
%F a(2n) = 3*a(n) - 1. [Thus a(2n+1) = 0 or 1 when reduced modulo 3. See A341346]
%F a(3n) = 5*a(n) - 2.
%F a(4n) = 9*a(n) - 4.
%F a(5n) = 7*a(n) - 3.
%F a(6n) = 15*a(n) - 7.
%F a(7n) = 11*a(n) - 5.
%F a(8n) = 27*a(n) - 13.
%F a(9n) = 25*a(n) - 12.
%F and in general:
%F a(x*y) = (A003961(x) * a(y)) - a(x) + 1, for all x, y >= 1.
%F (End)
%F From _Antti Karttunen_, Feb 10 2021: (Start)
%F For n > 1, a(2n) = A016789(a(n)-1), a(2n+1) = A253888(a(n)).
%F a(2^n) = A007051(n) for all n >= 0. [A property shared with A183209 and A254103].
%F (End)
%F a(n) = A003602(A003961(n)). - _Antti Karttunen_, Apr 20 2022
%F 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
%e 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.
%e For n = 12, as 12 = 2^2 * 3, we have a(12) = ((3^2 * 5) + 1)/2 = 23.
%p f:= proc(n)
%p local F,q,t;
%p F:= ifactors(n)[2];
%p (1 + mul(nextprime(t[1])^t[2], t = F))/2
%p end proc:
%p seq(f(n),n=1..1000); # _Robert Israel_, Jan 15 2015
%t 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 *)
%o (Haskell)
%o a048673 = (`div` 2) . (+ 1) . a045965
%o -- _Reinhard Zumkeller_, Jul 12 2012
%o (PARI)
%o A003961(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ From A003961
%o A048673(n) = (A003961(n)+1)/2; \\ _Antti Karttunen_, Dec 20 2014
%o (PARI) A048673(n) = if(1==n,n,if(n%2,A253888(A048673((n-1)/2)),(3*A048673(n/2))-1)); \\ (Not practical, but demonstrates the construction as a binary tree). - _Antti Karttunen_, Feb 10 2021
%o (Scheme) (define (A048673 n) (/ (+ 1 (A003961 n)) 2)) ;; _Antti Karttunen_, Dec 20 2014
%o (Python)
%o from sympy import factorint, nextprime, prod
%o def a(n):
%o f = factorint(n)
%o return 1 if n==1 else (1 + prod(nextprime(i)**f[i] for i in f))//2 # _Indranil Ghosh_, May 09 2017
%Y Inverse: A064216.
%Y Row 1 of A251722, Row 2 of A249822.
%Y One more than A108228, half the terms of A243501.
%Y Fixed points: A048674.
%Y Positions of records: A029744, their values: A246360 (= A007051 interleaved with A057198).
%Y Positions of subrecords: A247283, their values: A247284.
%Y Cf. A246351 (Numbers n such that a(n) < n.)
%Y Cf. A246352 (Numbers n such that a(n) >= n.)
%Y Cf. A246281 (Numbers n such that a(n) <= n.)
%Y Cf. A246282 (Numbers n such that a(n) > n.), A252742 (their char. function)
%Y Cf. A246261 (Numbers n for which a(n) is odd.)
%Y Cf. A246263 (Numbers n for which a(n) is even.)
%Y Cf. A246260 (a(n) reduced modulo 2), A341345 (modulo 3), A341346, A292251 (3-adic valuation), A292252.
%Y Cf. A246342 (Iterates starting from n=12.)
%Y Cf. A246344 (Iterates starting from n=16.)
%Y Cf. also A003602, A003961 (A045965), A108951, A151800, A245449, A249735, A249821, A250471, A250249, A250250.
%Y Cf. A245447 (This permutation "squared", a(a(n)).)
%Y 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.
%Y Cf. also prime-shift based binary trees A005940, A163511, A245612 and A244154.
%Y Cf. A253888, A253889, A292243, A292244, A292245 and A292246 for other derived sequences.
%Y Cf. A323893 (Dirichlet inverse), A323894 (sum with it), A336840 (inverse Möbius transform).
%K nonn
%O 1,2
%A _Antti Karttunen_, Jul 14 1999
%E New name and crossrefs to derived sequences added by _Antti Karttunen_, Dec 20 2014
| 