cp's OEIS Frontend

A193231 Blue code for n: in binary coding of a polynomial over GF(2), substitute x+1 for x (see Comments for precise definition).

%I A193231 #119 Jul 01 2025 17:49:50
%S A193231 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,
%T A193231 29,28,27,26,24,25,51,50,48,49,54,55,53,52,60,61,63,62,57,56,58,59,34,
%U A193231 35,33,32,39,38,36,37,45,44,46,47,40,41,43,42,85,84,86
%N A193231 Blue code for n: in binary coding of a polynomial over GF(2), substitute x+1 for x (see Comments for precise definition).
%C A193231 This is a self-inverse permutation of the nonnegative integers.
%C A193231 The function "substitute x+1 for x" on polynomials over GF(2) is completely multiplicative.
%C A193231 What is the density of fixed points in this sequence? Do we get a different answer if we look only at irreducible polynomials?
%C A193231 From _Antti Karttunen_, Dec 27 2013: (Start)
%C A193231 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.)
%C A193231 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.
%C A193231 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.
%C A193231 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].
%C A193231 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).
%C A193231 (End)
%H A193231 Antti Karttunen, <a href="/A193231/b193231.txt">Table of n, a(n) for n = 0..8191</a>
%H A193231 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 1.19, "Invertible transforms on words", pp. 49--55 [The name "blue code" is introduced in this book. - _Antti Karttunen_, Dec 28 2013]
%H A193231 Tilman Piesk, <a href="https://commons.wikimedia.org/wiki/File:Reverse_3;_Z_to_Z;_long.svg">illustration of the first 256 terms</a>
%H A193231 <a href="/index/Ge#GF2X">Index entries for sequences operating on (or containing) GF(2)[X]-polynomials</a>
%H A193231 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A193231 From _Antti Karttunen_, Dec 27 2013: (Start)
%F A193231 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.
%F A193231 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).
%F A193231 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]
%F A193231 For all n, abs(a(2n)-a(2n+1)) = 1.
%F A193231 a(A000079(n)) = A001317(n).
%F A193231 (End)
%F A193231 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
%e A193231 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.
%e A193231 From _Tilman Piesk_, Jun 26 2025: (Start)
%e A193231 The binary exponents of 11 are {0, 1, 3}, because 11 = 2^0 + 2^1 + 2^3.
%e A193231 a(11) = A001317(0) XOR A001317(1) XOR A001317(3) = 1 XOR 3 XOR 15 = 13. (End)
%t A193231 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 *)
%o A193231 (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
%o A193231 a(n)=subst(lift(subst(tox(n),X,X+1)),X,2)
%o A193231 (PARI) a(n)={local(x='x);subst(lift(Mod(1,2)*subst(Pol(binary(n),x),x,1+x)),x,2)};
%o A193231 (Scheme)
%o A193231 ;; with memoizing macro definec available in Antti Karttunen's IntSeq-library:
%o A193231 (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.
%o A193231 ;; _Antti Karttunen_, Dec 27 2013
%o A193231 (Scheme)
%o A193231 ;; With memoizing macro definec available in Antti Karttunen's IntSeq-library.
%o A193231 ;; Alternative implementation, a recurrence based on entangling even & odd numbers with complementary pair A048724 and A065621:
%o A193231 (definec (A193231 n) (cond ((< n 2) n) ((even? n) (A048724 (A193231 (/ n 2)))) (else (A065621 (+ (A193231 (/ (- n 1) 2)) 1)))))
%o A193231 ;; _Antti Karttunen_, Dec 27 2013
%o A193231 (Python)
%o A193231 def a065621(n): return n^(2*(n - (n&-n)))
%o A193231 def a048724(n): return n^(2*n)
%o A193231 l=[0, 1]
%o A193231 for n in range(2, 101):
%o A193231     if n%2==0: l.append(a048724(l[n//2]))
%o A193231     else: l.append(a065621(1 + l[(n - 1)//2]))
%o A193231 print(l) # _Indranil Ghosh_, Jun 04 2017
%Y A193231 Cf. A000069, A001969, A001317, A003987, A048720, A048724, A065621, A051437, A118666 (fixed points), A131575, A234022 (the number of 1-bits), A234023, A010060, A234745, A234750.
%Y A193231 Similarly constructed permutation pairs: A003188/A006068, A135141/A227413, A232751/A232752, A233275/A233276, A233277/A233278, A233279/A233280.
%Y A193231 Other permutations based on this (by conjugating, composing, etc): A234024, A234025/A234026, A234027, A234612, A234613, A234747, A234748, A244987, A245812, A245454.
%K A193231 nonn,look,hear
%O A193231 0,3
%A A193231 _Franklin T. Adams-Watters_, Jul 18 2011