A193231 - OEIS

%I #106 Jan 29 2025 19:37:02

%S 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 29,28,27,26,24,25,51,50,48,49,54,55,53,52,60,61,63,62,57,56,58,59,34,

%U 35,33,32,39,38,36,37,45,44,46,47,40,41,43,42,85,84,86

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

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

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

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

%C From _Antti Karttunen_, Dec 27 2013: (Start)

%C 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 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 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 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 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 (End)

%H Antti Karttunen, <a href="/A193231/b193231.txt">Table of n, a(n) for n = 0..8191</a>

%H 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 <a href="/index/Ge#GF2X">Index entries for sequences operating on (or containing) GF(2)[X]-polynomials</a>

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%F From _Antti Karttunen_, Dec 27 2013: (Start)

%F 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 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 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 For all n, abs(a(2n)-a(2n+1)) = 1.

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

%F (End)

%F 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 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.

%t 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 (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 a(n)=subst(lift(subst(tox(n),X,X+1)),X,2)

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

%o (Scheme)

%o ;; with memoizing macro definec available in Antti Karttunen's IntSeq-library:

%o (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 ;; _Antti Karttunen_, Dec 27 2013

%o (Scheme)

%o ;; With memoizing macro definec available in Antti Karttunen's IntSeq-library.

%o ;; Alternative implementation, a recurrence based on entangling even & odd numbers with complementary pair A048724 and A065621:

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

%o ;; _Antti Karttunen_, Dec 27 2013

%o (Python)

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

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

%o l=[0, 1]

%o for n in range(2, 101):

%o     if n%2==0: l.append(a048724(l[n//2]))

%o     else: l.append(a065621(1 + l[(n - 1)//2]))

%o print(l) # _Indranil Ghosh_, Jun 04 2017

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

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

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

%K nonn,look,hear,changed

%O 0,3

%A _Franklin T. Adams-Watters_, Jul 18 2011