|
%I #12 Jun 10 2018 21:14:26
%S 1,2,3,4,7,6,5,8,11,14,9,12,21,10,15,16,13,22,29,28,49,18,27,24,69,42,
%T 63,20,107,30,17,32,19,26,23,44,35,58,39,56,127,98,83,36,151,54,45,48,
%U 81,138,207,84,475,126,65,40,743,214,189,60,273,34,51,64,25,38,53,52,121,46,57,88,173,70,101,116,233,78,105,112,199,254,129
%N Permutation of natural numbers: a(0) = 1, a(2n) = A305421(a(n)), a(2n+1) = 2*a(n).
%C This is GF(2)[X] analog of A005940, but note the indexing: here the domain starts from 0, although the range excludes zero.
%C This sequence can be represented as a binary tree. Each child to the left is obtained by applying A305421 to the parent, and each child to the right is obtained by doubling the parent:
%C 1
%C |
%C ...................2...................
%C 3 4
%C 7......../ \........6 5......../ \........8
%C / \ / \ / \ / \
%C / \ / \ / \ / \
%C / \ / \ / \ / \
%C 11 14 9 12 21 10 15 16
%C 13 22 29 28 49 18 27 24 69 42 63 20 107 30 17 32
%C Sequence A305427 is obtained by scanning the same tree level by level from right to left.
%H Antti Karttunen, <a href="/A305417/b305417.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(2n) = A305421(a(n)), a(2n+1) = 2*a(n).
%F a(n) = A305427(A054429(n)).
%F For all n >= 1, a(A000079(n-1)) = A014580(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 A305417(n) = if(0==n,(1+n),if(!(n%2),A305421(A305417(n/2)),2*(A305417((n-1)/2))));
%Y Cf. A305418 (inverse), A305427 (mirror image).
%Y Cf. A014580 (left edge from 2 onward), A305421.
%Y Cf. also A005940, A052330, A091202.
%K nonn,tabf
%O 0,2
%A _Antti Karttunen_, Jun 10 2018
|
