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

Author

Antti Karttunen, Jun 10 2018

Keywords

• nonn
• tabf

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

Crossrefs

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

Cf. A305421.

Cf. also A091202, A163511.

Programs

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))));

Formula

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

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