login
A246684
"Caves of prime shift" permutation: a(1) = 1, a(n) = A242378(A007814(n), 2*a(A003602(n))) - 1.
9
1, 2, 3, 4, 5, 8, 7, 6, 9, 14, 15, 24, 13, 26, 11, 10, 17, 20, 27, 34, 29, 80, 47, 48, 25, 32, 51, 124, 21, 44, 19, 12, 33, 74, 39, 54, 53, 98, 67, 76, 57, 104, 159, 624, 93, 404, 95, 120, 49, 50, 63, 64, 101, 152, 247, 342, 41, 38, 87, 174, 37, 62, 23, 16, 65, 56, 147, 244, 77, 188, 107, 90, 105, 374, 195, 324, 133, 170, 151, 142, 113, 92
OFFSET
1,2
COMMENTS
See the comments in A246676. This is otherwise similar permutation, except that after having reached an odd number 2m-1 when we have shifted the binary representation of n right k steps, here, in contrary to A246676, we don't shift the primes in the prime factorization of the even number 2m, but instead of an even number (2*a(m)), shifting it the same number (k) of positions towards larger primes, whose product is then decremented by one to get the final result.
From Antti Karttunen, Jan 18 2015: (Start)
This can be viewed as an entanglement or encoding permutation where the complementary pairs of sequences to be interwoven together are even and odd numbers (A005843/A005408) which are entangled with another complementary pair: even numbers in the order they appear in A253885 and odd numbers in their usual order: (A253885/A005408).
From the above follows also that this sequence can be represented as a binary tree. Each child to the left is obtained by doubling the parent and subtracting one, and each child to the right is obtained by applying A253885 to the parent:
1
|
...................2...................
3 4
5......../ \........8 7......../ \........6
/ \ / \ / \ / \
/ \ / \ / \ / \
/ \ / \ / \ / \
9 14 15 24 13 26 11 10
17 20 27 34 29 80 47 48 25 32 51 124 21 44 19 12
(End)
FORMULA
a(1) = 1, a(n) = A242378(A007814(n), 2*a(A003602(n))) - 1. [Where the bivariate function A242378(k,n) changes each prime p(i) in the prime factorization of n to p(i+k), i.e., it's the result of A003961 iterated k times starting from n].
a(1) = 1, a(2n) = A253885(a(n)), a(2n+1) = (2*a(n+1))-1. - Antti Karttunen, Jan 18 2015
As a composition of other permutations:
a(n) = A250243(A249814(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 n=30, "11110" in binary. It has to be shifted just one bit-position right that the result were an odd number 15, "1111" in binary. As 15 = 2*8-1, we use 2*a(8) = 2*6 = 12 = 2*2*3 = p_1 * p_1 * p_2 [where p_k denotes the k-th prime, A000040(k)], which we shift one step towards larger primes resulting p_2 * p_2 * p_3 = 3*3*5 = 45, thus a(30) = 45-1 = 44.
PROG
(PARI)
A003961(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ Using code of Michel Marcus
A246684(n) = { my(k=0); if(1==n, 1, while(!(n%2), n = n/2; k++); n = 2*A246684((n+1)/2); while(k>0, n = A003961(n); k--); n-1); };
for(n=1, 8192, write("b246684.txt", n, " ", A246684(n)));
(Scheme, with memoization-macro definec, two implementations)
(definec (A246684 n) (cond ((<= n 1) n) (else (+ -1 (A242378bi (A007814 n) (* 2 (A246684 (A003602 n)))))))) ;; Code for A242378bi given in A242378.
(definec (A246684 n) (cond ((<= n 1) n) ((even? n) (A253885 (A246684 (/ n 2)))) (else (+ -1 (* 2 (A246684 (/ (+ n 1) 2)))))))
CROSSREFS
Inverse: A246683.
Other versions: A246676, A246678.
Similar or related permutations: A005940, A163511, A241909, A245606, A246278, A246375, A249814, A250243.
Differs from A249814 for the first time at n=14, where a(14) = 26, while A249814(14) = 20.
Sequence in context: A246678 A269384 A249814 * A249812 A246675 A269388
KEYWORD
nonn,tabf,look
AUTHOR
Antti Karttunen, Sep 06 2014
STATUS
approved