login
Permutation of natural numbers: a(1) = 1, a(n) = A000079(A055396(n+1)-1) * ((2*a(A246277(n+1))) - 1).
9

%I #16 Jan 18 2015 19:03:40

%S 1,2,3,4,5,8,7,6,9,16,15,32,13,10,11,64,17,128,31,18,29,256,63,12,25,

%T 14,19,512,21,1024,127,26,33,20,255,2048,61,58,35,4096,57,8192,511,30,

%U 125,16384,23,24,49,50,27,32768,37,36,1023,66,41,65536,2047,131072,253,62,51,52,65,262144,39,122,509,524288,4095,1048576,121

%N Permutation of natural numbers: a(1) = 1, a(n) = A000079(A055396(n+1)-1) * ((2*a(A246277(n+1))) - 1).

%C See the comments in A246675. This is otherwise similar permutation, except that after having reached an even number 2m when we have shifted the prime factorization of n+1 k steps towards smaller primes, here, in contrary to A246675, we don't shift the binary representation of the odd number 2m-1, but instead of an odd number (2*a(m))-1 the same number (k) of bit-positions leftward, i.e. multiply it with 2^k.

%C See also the comments at the inverse permutation A246684.

%H Antti Karttunen, <a href="/A246683/b246683.txt">Table of n, a(n) for n = 1..2049</a>

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

%F a(1) = 1, a(n) = A000079(A055396(n+1)-1) * ((2*a(A246277(n+1))) - 1).

%F As a composition of other permutations:

%F a(n) = A249813(A250244(n)).

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

%F a(n) = (1+a((2*n)-1))/2. [The odd bisection from a(1) onward with one added and then halved gives the sequence back].

%F For all n >= 0, the following holds: a(A000051(n)) = A000051(n). [Numbers of the form 2^n + 1 are among the fixed points].

%e Consider 44 = 45-1. To find 45's position in array A246278, we start shifting its prime factorization 45 = 3 * 3 * 5 = p_2 * p_2 * p_3, step by step, until we get an even number, which in this case happens immediately after the first step, as p_1 * p_1 * p_2 = 2*2*3 = 12. 12 is in the 6th column of A246278, thus we take [here a(6) is computed recursively in the same way:] (2*a(6))-1 = (2*8)-1 = 15, "1111" in binary, and shift it one bit left (that is, multiply by 2), to give 2*15 = 30, thus a(44) = 30.

%o (Scheme, with memoization-macro definec)

%o (definec (A246683 n) (cond ((<= n 1) n) (else (* (A000079 (- (A055396 (+ 1 n)) 1)) (-1+ (* 2 (A246683 (A246277 (+ 1 n)))))))))

%Y Inverse: A246684.

%Y Variants: A246675, A246677.

%Y Cf. A000051, A000079, A005408, A055396, A246277, A246278,

%Y A249813, A250244.

%Y Differs from A249813 for the first time at n=20, where a(20) = 18, while A249813(20) = 14.

%K nonn

%O 1,2

%A _Antti Karttunen_, Sep 06 2014