login
Permutation of natural numbers: a(0) = 1, a(1) = 2, a(p_n) = A003961(a(n)), a(c_n) = 2*a(n), where p_n = n-th prime = A000040(n), c_n = n-th composite number = A002808(n), and A003961(n) shifts the prime factorization of n one step towards larger primes.
7

%I #18 Sep 03 2014 21:06:29

%S 1,2,3,5,4,7,6,9,10,8,14,11,12,15,18,20,16,25,28,21,22,24,30,27,36,40,

%T 32,50,56,33,42,13,44,48,60,54,72,45,80,64,100,35,112,75,66,84,26,63,

%U 88,96,120,108,144,81,90,160,128,200,70,49,224,99,150,132,168,52,126,55,176,192,240,39

%N Permutation of natural numbers: a(0) = 1, a(1) = 2, a(p_n) = A003961(a(n)), a(c_n) = 2*a(n), where p_n = n-th prime = A000040(n), c_n = n-th composite number = A002808(n), and A003961(n) shifts the prime factorization of n one step towards larger primes.

%C Note the indexing: the domain starts from 0, while the range excludes zero.

%C Iterating a(n) from n=0 gives the sequence: 1, 2, 3, 5, 7, 9, 8, 10, 14, 18, 28, 56, 128, 156, 1344, 16524, 2706412500, ..., which is the only one-way cycle of this permutation.

%C Because 2 is the only even prime, it implies that, apart from a(0)=1 and a(2)=3, odd numbers occur in odd positions only (along with many even numbers that also occur in odd positions). This in turn implies that there exists an infinite number of infinite cycles like (... 648391 31 13 15 20 22 30 42 112 196 1350 ...) which contain just one odd composite (A071904). Apart from 9 which is in that one-way cycle, each odd composite occurs in a separate infinite two-way cycle, like 15 in the example above.

%H Antti Karttunen, <a href="/A246681/b246681.txt">Table of n, a(n) for n = 0..10000</a>

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%F a(0) = 1, a(1) = 2, and for n > 1, if A010051(n) = 1 [i.e. when n is a prime], a(n) = A003961(a(A000720(n))), otherwise a(n) = 2*a(A065855(n)).

%F Other identities.

%F For all n >= 0, the following holds:

%F a(A007097(n)) = A000040(n+1). [Maps the iterates of primes to primes].

%F A078442(a(n)) > 0 if and only if n is in A007097. [Follows from above].

%F For all n >= 1, the following holds:

%F a(n) = A163511(A246377(n)).

%F A000035(a(n)) = A010051(n). [Maps primes to odd numbers > 1, and composites to even numbers, in some order. Permutations A246377 & A246379 have the same property].

%F A055396(a(n)) = A049076(n). [An "order of primeness" is mapped to the index of the smallest prime dividing n].

%o (Scheme, two different variants)

%o (definec (A246681 n) (cond ((<= n 1) (+ n 1)) ((= 1 (A010051 n)) (A003961 (A246681 (A000720 n)))) (else (* 2 (A246681 (A065855 n))))))

%o (define (A246681 n) (if (zero? n) 1 (A163511 (A246377 n))))

%Y Inverse: A246682.

%Y Similar or related permutations: A163511, A246377, A246379, A246367, A245821.

%Y Cf. A000040, A000720, A003961, A007097, A010051, A065855, A071904, A078442, A049076, A055396.

%K nonn,look

%O 0,2

%A _Antti Karttunen_, Sep 01 2014