A269854 Permutation of natural numbers: a(1) = 1, a(2n) = 2*a(n), a(2n+1) = 2+A003961(a(n)).

1, 2, 3, 4, 5, 6, 7, 8, 11, 10, 9, 12, 17, 14, 13, 16, 29, 22, 15, 20, 23, 18, 27, 24, 47, 34, 21, 28, 35, 26, 19, 32, 83, 58, 33, 44, 41, 30, 37, 40, 65, 46, 31, 36, 77, 54, 127, 48, 137, 94, 55, 68, 59, 42, 57, 56, 101, 70, 79, 52, 53, 38, 25, 64, 245, 166, 91, 116, 95, 66, 67, 88, 119, 82, 45, 60, 107, 74, 43, 80, 191, 130, 121, 92, 89, 62, 39

Offset: 1

Author

Antti Karttunen, Mar 16 2016

Keywords

• nonn
• tabf

Comments

This sequence can be represented as a binary tree. When the parent contains n, the left hand child contains 2n, while the contents of the right hand child is obtained as 2+A003961(n):

1

|

................../ \..................

2 3

4......../ \........5 6......../ \........7

/ \ / \ / \ / \

/ \ / \ / \ / \

/ \ / \ / \ / \

8 11 10 9 12 17 14 13

16 29 22 15 20 23 18 27 24 47 34 21 28 35 26 19

etc.

Links

• Antti Karttunen, Table of n, a(n) for n = 1..8192
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Inverse: A269853.

Cf. A003961, A048673, A163511, A243501, A246375, A269865.

Programs

PARI

default(primelimit, (2^31)+(2^30));
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
A269854(n) = if(1==n, 1, if(!(n%2), 2*A269854(n/2), 2+A003961(A269854((n-1)/2))));
for(n=1, 8192, write("b269854.txt", n, " ", A269854(n)));
(Scheme, with memoization-macro definec)
(definec (A269854 n) (cond ((= 1 n) n) ((even? n) (* 2 (A269854 (/ n 2)))) (else (+ 1 (A243501 (A269854 (/ (- n 1) 2)))))))

Formula

a(1) = 1, a(2n) = 2*a(n), a(2n+1) = 2+A003961(a(n)) = 1 + 2*A048673(a(n)).