A193231 Blue code for n: in binary coding of a polynomial over GF(2), substitute x+1 for x (see Comments for precise definition).
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
Offset: 0
Examples
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.
From _Tilman Piesk_, Jun 26 2025: (Start)
The binary exponents of 11 are {0, 1, 3}, because 11 = 2^0 + 2^1 + 2^3.
a(11) = A001317(0) XOR A001317(1) XOR A001317(3) = 1 XOR 3 XOR 15 = 13. (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]
- Tilman Piesk, illustration of the first 256 terms
- Index entries for sequences operating on (or containing) GF(2)[X]-polynomials
- Index entries for sequences that are permutations of the natural numbers
Crossrefs
Cf. A000069, A001969, A001317, A003987, A048720, A048724, A065621, A051437, A118666 (fixed points), A131575, A234022 (the number of 1-bits), A234023, A010060, A234745, A234750.
Programs
-
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 *) -
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)}; -
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 -
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. ;; Antti Karttunen, Dec 27 2013
-
Scheme
;; With memoizing macro definec available in Antti Karttunen's IntSeq-library. ;; 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
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.
(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
Comments