The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 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. 78
 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] 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) It follows from the first paragraph above that a(A003987(n,k)) = A003987(a(n), a(k)), that is a(n XOR k) = a(n) XOR a(k). - Peter Munn, Nov 27 2019 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 range(2, 101):     if n%2==0: l.append(a048724(l[n//2]))     else: l.append(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, 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: A266089 A340478 A340402 * A191672 A273876 A273865 Adjacent sequences:  A193228 A193229 A193230 * A193232 A193233 A193234 KEYWORD nonn,look,hear 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 26 01:20 EDT 2021. Contains 346294 sequences. (Running on oeis4.)