A305418 Permutation of nonnegative integers: a(1) = 0, a(2n) = 1 + 2*a(n), a(2n+1) = 2*a(A305422(2n+1)).

0, 1, 2, 3, 6, 5, 4, 7, 10, 13, 8, 11, 16, 9, 14, 15, 30, 21, 32, 27, 12, 17, 34, 23, 64, 33, 22, 19, 18, 29, 128, 31, 258, 61, 36, 43, 256, 65, 38, 55, 512, 25, 130, 35, 46, 69, 1024, 47, 20, 129, 62, 67, 66, 45, 2048, 39, 70, 37, 4096, 59, 8192, 257, 26, 63, 54, 517, 16384, 123, 24, 73, 16386, 87, 32768, 513, 142, 131, 8194, 77, 132, 111, 48, 1025, 42, 51

Offset: 1

Author

Antti Karttunen, Jun 10 2018

Keywords

• nonn

Comments

This is GF(2)[X] analog of A156552. Note the indexing: the domain starts from 1, while the range includes also zero.

Links

• Antti Karttunen, Table of n, a(n) for n = 1..4096
• Index entries for sequences operating on GF(2)[X]-polynomials
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A305417 (inverse).

Cf. A305422.

Cf. also A091203, A156552, A052331, A305428.

Programs

PARI

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

Formula

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

a(n) = A054429(A305428(n)).

For all n >= 1:

A000120(a(n)) = A091222(n).

A069010(a(n)) = A091221(n).

A106737(a(n)) = A091220(n).

A132971(a(n)) = A091219(n).

A085357(a(n)) = A304109(n).