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

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, 14, 19, 512, 21, 1024, 127, 26, 33, 20, 255, 2048, 61, 58, 35, 4096, 57, 8192, 511, 30, 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

Offset

1,2

Comments

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.

See also the comments at the inverse permutation A246684.

Links

Antti Karttunen, Table of n, a(n) for n = 1..2049

Index entries for sequences that are permutations of the natural numbers

Formula

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

As a composition of other permutations:

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

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

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

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

Example

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.

Prog

(Scheme, with memoization-macro definec)
(definec (A246683 n) (cond ((<= n 1) n) (else (* (A000079 (- (A055396 (+ 1 n)) 1)) (-1+ (* 2 (A246683 (A246277 (+ 1 n)))))))))

Crossrefs

Inverse: A246684.

Variants: A246675, A246677.

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

A249813, A250244.

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

Sequence in context: A156552 A269383 A249813 * A332816 A372134 A354732

Adjacent sequences: A246680 A246681 A246682 * A246684 A246685 A246686

Keyword

nonn

Author

Antti Karttunen, Sep 06 2014

Status

approved