A305427 Permutation of natural numbers: a(0) = 1, a(1) = 2, a(2n) = 2*a(n), a(2n+1) = A305421(a(n)).

1, 2, 4, 3, 8, 5, 6, 7, 16, 15, 10, 21, 12, 9, 14, 11, 32, 17, 30, 107, 20, 63, 42, 69, 24, 27, 18, 49, 28, 29, 22, 13, 64, 51, 34, 273, 60, 189, 214, 743, 40, 65, 126, 475, 84, 207, 138, 81, 48, 45, 54, 151, 36, 83, 98, 127, 56, 39, 58, 35, 44, 23, 26, 19, 128, 85, 102, 1911, 68, 819, 546, 4113, 120, 455, 378, 3253, 428, 1833, 1486, 925, 80

Offset

0,2

Comments

Note the indexing: Domain starts from 0, while range starts from 1.

This is GF(2)[X] analog of A163511.

This sequence can be represented as a binary tree. Each child to the left is obtained by doubling the parent, and each child to the right is obtained by applying A305421 to the parent:

1

|

...................2...................

4 3

8......../ \........5 6......../ \........7

/ \ / \ / \ / \

/ \ / \ / \ / \

/ \ / \ / \ / \

16 15 10 21 12 9 14 11

32 17 30 107 20 63 42 69 24 27 18 49 28 29 22 13

etc.

Sequence A305417 is obtained by scanning the same tree level by level from right to left.

Links

Antti Karttunen, Table of n, a(n) for n = 0..16383

Index entries for sequences operating on GF(2)[X]-polynomials

Index entries for sequences that are permutations of the natural numbers

Formula

a(0) = 1, a(1) = 2, a(2n) = 2*a(n), a(2n+1) = A305421(a(n)).

a(n) = A305417(A054429(n)).

Prog

(PARI)
A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));
A305420(n) = { my(k=1+n); while(!A091225(k), k++); (k); };
A305421(n) = { my(f = subst(lift(factor(Pol(binary(n))*Mod(1, 2))), x, 2)); for(i=1, #f~, f[i, 1] = Pol(binary(A305420(f[i, 1])))); fromdigits(Vec(factorback(f))%2, 2); };
A305427(n) = if(n<=1, (1+n), if(!(n%2), 2*A305427(n/2), A305421(A305427((n-1)/2))));

Crossrefs

Cf. A305428 (inverse), A305417 (mirror image).

Cf. A305421.

Cf. also A091202, A163511.

Sequence in context: A367263 A048167 A207790 * A269375 A135141 A098709

Adjacent sequences: A305424 A305425 A305426 * A305428 A305429 A305430

Keyword

nonn,tabf

Author

Antti Karttunen, Jun 10 2018

Status

approved