cp's OEIS Frontend

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

%I A305427 #8 Jun 10 2018 21:14:39
%S A305427 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 A305427 27,18,49,28,29,22,13,64,51,34,273,60,189,214,743,40,65,126,475,84,
%U A305427 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 A305427 Permutation of natural numbers: a(0) = 1, a(1) = 2, a(2n) = 2*a(n), a(2n+1) = A305421(a(n)).
%C A305427 Note the indexing: Domain starts from 0, while range starts from 1.
%C A305427 This is GF(2)[X] analog of A163511.
%C A305427 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 A305427                                      1
%C A305427                                      |
%C A305427                   ...................2...................
%C A305427                  4                                       3
%C A305427        8......../ \........5                   6......../ \........7
%C A305427       / \                 / \                 / \                 / \
%C A305427      /   \               /   \               /   \               /   \
%C A305427     /     \             /     \             /     \             /     \
%C A305427   16       15         10       21         12       9          14       11
%C A305427 32  17   30  107    20  63   42  69     24  27   18 49      28  29   22  13
%C A305427 etc.
%C A305427 Sequence A305417 is obtained by scanning the same tree level by level from right to left.
%H A305427 Antti Karttunen, <a href="/A305427/b305427.txt">Table of n, a(n) for n = 0..16383</a>
%H A305427 <a href="/index/Ge#GF2X">Index entries for sequences operating on GF(2)[X]-polynomials</a>
%H A305427 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A305427 a(0) = 1, a(1) = 2, a(2n) = 2*a(n), a(2n+1) = A305421(a(n)).
%F A305427 a(n) = A305417(A054429(n)).
%o A305427 (PARI)
%o A305427 A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));
%o A305427 A305420(n) = { my(k=1+n); while(!A091225(k),k++); (k); };
%o A305427 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 A305427(n) = if(n<=1,(1+n),if(!(n%2),2*A305427(n/2),A305421(A305427((n-1)/2))));
%Y A305427 Cf. A305428 (inverse), A305417 (mirror image).
%Y A305427 Cf. A305421.
%Y A305427 Cf. also A091202, A163511.
%K A305427 nonn,tabf
%O A305427 0,2
%A A305427 _Antti Karttunen_, Jun 10 2018