login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A193231 Blue code of n: in binary coding of a polynomial over GF(2), substitute x+1 for x. 72
0, 1, 3, 2, 5, 4, 6, 7, 15, 14, 12, 13, 10, 11, 9, 8, 17, 16, 18, 19, 20, 21, 23, 22, 30, 31, 29, 28, 27, 26, 24, 25, 51, 50, 48, 49, 54, 55, 53, 52, 60, 61, 63, 62, 57, 56, 58, 59, 34, 35, 33, 32, 39, 38, 36, 37, 45, 44, 46, 47, 40, 41, 43, 42, 85, 84, 86 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

This is a self-inverse permutation of the nonnegative integers.

The function "substitute x+1 for x" on polynomials over GF(2) is completely multiplicative.

What is the density of fixed points in this sequence? Do we get a different answer if we look only at irreducible polynomials?

From Antti Karttunen, Dec 27 2013: (Start)

As what comes to the above question, the number of fixed points in range [2^(n-1),(2^n)-1] of the sequence is given by A131575(n). In range [0,0] there is one fixed point: 0, in range [1,1] there is also one: 1, in range [2,3] there are no fixed points, in range [4,7] there are two fixed points: 6 and 7, and so on. (Cf. also the C-code given in A118666.)

Similarly, the number of cycles in such ranges begins as 1, 1, 1, 3, 4, 10, 16, 36, 64, 136, ... which is A051437 shifted two steps right (prepended with 1's): Because the sequence is a self-inverse permutation, the number of its cycles in range [2^(n-1),(2^n)-1] is computed as: cycles(n) = (A011782(n)-number_of_fixedpoints(n))/2 + number_of_fixedpoints(n), which matches with the identity: A051437(n-2) = (A011782(n)-A131575(n))/2 + A131575(n), for n>=2.

In OEIS terms, the above comment about multiplicativeness can be rephrased as: a(A048720(x,y)) = A048720(a(x),a(y)) for all integers x, y >= 0. Here A048720(x,y) gives the product of carryless binary multiplication of x and y.

The permutation conjugates between Gray code and its inverse: A003188(n) = a(A006068(a(n))) and A006068(n) = a(A003188(a(n))) [cf. the identity 1.19-9d: gB = Bg^{-1} given on page 53 of fxtbook].

Because of the multiplicativity, the subset of irreducible (and respectively: composite) polynomials over GF(2) is closed under this permutation. Cf. the following mappings: a(A014580(n)) = A234750(n) and a(A091242(n)) = A234745(n).

(End)

LINKS

Antti Karttunen, Table of n, a(n) for n = 0..8191

Joerg Arndt, Matters Computational (The Fxtbook), section 1.19, "Invertible transforms on words", pp. 49--55 [The name "blue code" is introduced in this book. - Antti Karttunen, Dec 28 2013]

Index entries for sequences operating on (or containing) GF(2)[X]-polynomials

Index entries for sequences that are permutations of the natural numbers

FORMULA

From Antti Karttunen, Dec 27 2013: (Start)

a(0) = 0, and for any n = 2^a + 2^b + ... + 2^c, a(n) = A001317(a) XOR A001317(b) XOR ... XOR A001317(c), where XOR is bitwise XOR (A003987) and all the exponents a, b, ..., c are distinct, that is, they are the indices of 1-bits in the binary representation of n.

From above it follows, because all terms of A001317 are odd, that A000035(a(n)) = A010060(n) = A000035(a(2n)). Conversely, we also have A010060(a(n)) = A000035(n). Thus the permutation maps any even number to some evil number, A001969 (and vice versa), like it maps any odd number to some odious number, A000069 (and vice versa).

a(0)=0, a(1)=1, and for n>1, a(2n) = A048724(a(n)), a(2n+1) = A065621(1+a(n)). [A recurrence based on entangling even & odd numbers with the complementary pair A048724/A065621]

For all n, abs(a(2n)-a(2n+1)) = 1.

a(A000079(n)) = A001317(n).

(End)

EXAMPLE

11, binary 1011, corresponds to polynomial x^3+x+1, substituting: (x+1)^3+(x+1)+1 = x^3+x^2+x+1 + x+1 + 1 = x^3+x^2+1, binary 1101 = decimal 13, so a(11) = 13.

MATHEMATICA

f[n_] := Which[0 <= # <= 1, #, EvenQ@ #, BitXor[2 #, #] &[f[#/2]], True, BitXor[#, 2 # + 1] &[f[(# - 1)/2]]] &@ Abs@ n; Table[f@ n, {n, 0, 66}] (* Michael De Vlieger, Feb 12 2016, after Robert G. Wilson v at A048724 and A065621 *)

PROG

(PARI) tox(n) = local(x=Mod(1, 2)*X, xp=1, r); while(n>0, if(n%2, r+=xp); xp*=x; n\=2); r

a(n)=subst(lift(subst(tox(n), X, X+1)), X, 2)

(PARI) a(n)={local(x='x); subst(lift(Mod(1, 2)*subst(Pol(binary(n), x), x, 1+x)), x, 2)};

(Scheme, with memoizing macro definec available in Antti Karttunen's IntSeq-library):

(define (A193231 n) (let loop ((n n) (i 0) (s 0)) (cond ((zero? n) s) ((even? n) (loop (/ n 2) (+ 1 i) s)) (else (loop (/ (- n 1) 2) (+ 1 i) (A003987bi s (A001317 i))))))) ;; A003987bi implements binary XOR, A003987.

(Alternative implementation, a recurrence based on entangling even & odd numbers with complementary pair A048724 and A065621):

(definec (A193231 n) (cond ((< n 2) n) ((even? n) (A048724 (A193231 (/ n 2)))) (else (A065621 (+ (A193231 (/ (- n 1) 2)) 1)))))

;; Antti Karttunen, Dec 27 2013

(Python)

def a065621(n): return n^(2*(n - (n&-n)))

def a048724(n): return n^(2*n)

l=[0, 1]

for n in xrange(2, 101):

    if n%2==0: l+=[a048724(l[n/2]), ]

    else: l+=[a065621(1 + l[(n - 1)/2]), ]

print l # Indranil Ghosh, Jun 04 2017

CROSSREFS

Cf. A000069, A001969, A001317, A003987, A048720, A048724, A065621, A051437, A118666 (fixed points), A131575, A234022 (the number of 1-bits), A234023, A048724, A065621, A003188, A006068, A010060, A234745, A234750.

Similarly constructed permutation pairs: A003188/A006068, A135141/A227413, A232751/A232752, A233275/A233276, A233277/A233278, A233279/A233280.

Other permutations based on this (by conjugating, composing, etc): A234024, A234025/A234026, A234027, A234612, A234613, A234747, A234748, A244987, A245812, A245454.

Sequence in context: A160017 A266154 A266089 * A191672 A273876 A273865

Adjacent sequences:  A193228 A193229 A193230 * A193232 A193233 A193234

KEYWORD

nonn

AUTHOR

Franklin T. Adams-Watters, Jul 18 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 12 19:19 EST 2018. Contains 317116 sequences. (Running on oeis4.)