A305427 - OEIS

%I #8 Jun 10 2018 21:14:39

%S 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,

%T 27,18,49,28,29,22,13,64,51,34,273,60,189,214,743,40,65,126,475,84,

%U 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

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

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

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

%C 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:

%C                                      1

%C                                      |

%C                   ...................2...................

%C                  4                                       3

%C        8......../ \........5                   6......../ \........7

%C       / \                 / \                 / \                 / \

%C      /   \               /   \               /   \               /   \

%C     /     \             /     \             /     \             /     \

%C   16       15         10       21         12       9          14       11

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

%C etc.

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

%H Antti Karttunen, <a href="/A305427/b305427.txt">Table of n, a(n) for n = 0..16383</a>

%H <a href="/index/Ge#GF2X">Index entries for sequences operating on GF(2)[X]-polynomials</a>

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

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

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

%o (PARI)

%o A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));

%o A305420(n) = { my(k=1+n); while(!A091225(k),k++); (k); };

%o 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); };

%o A305427(n) = if(n<=1,(1+n),if(!(n%2),2*A305427(n/2),A305421(A305427((n-1)/2))));

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

%Y Cf. A305421.

%Y Cf. also A091202, A163511.

%K nonn,tabf

%O 0,2

%A _Antti Karttunen_, Jun 10 2018