|
%I #40 Mar 11 2024 18:05:44
%S 0,0,1,0,1,2,0,1,2,1,0,1,2,3,2,0,1,2,3,2,3,0,1,2,1,2,1,2,0,1,2,3,2,3,
%T 2,1,0,1,2,1,2,3,4,3,2,0,1,2,1,2,3,4,3,2,3,0,1,2,3,2,3,4,3,2,3,4,0,1,
%U 2,3,2,3,4,3,2,1,4,3,0,1,2,1,2,1,2,3,2,3,2,3,2,0,1,2,1,2,3,2,1,2,3,2,3,2,3,0,1,2,3,2,3,4,3,2,3,4,1,2,1,2
%N Square array A(n, k) = A101080(k, A003188(n+A006068(k))), read by descending antidiagonals, where A003188 is the binary Gray code, A006068 is its inverse, and A101080(x,y) gives the Hamming distance between binary expansions of x and y.
%C The entry at row n, column k, gives the Hamming distance between binary expansions of k and A003188(n+A006068(k)). When Gray code is viewed as a traversal of vertices of an infinite dimensional hypercube by bit-flipping (see the illustration "Visualized as a traversal of vertices of a tesseract" in the Wikipedia's "Gray code" article) the argument k is the "address" (the binary code given inside each vertex) of the starting vertex, and argument n tells how many edges forward along the Gray code path we should hop from it (to the direction that leads away from the vertex with code 0000...). A(n, k) gives then the Hamming distance between the starting and the ending vertex. For how this works with case n=3, see comments in A268676. - _Antti Karttunen_, Mar 11 2024
%H Antti Karttunen, <a href="/A268833/b268833.txt">Table of n, a(n) for n = 0..32895; the first 256 antidiagonals of array</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Gray_code">Gray code</a>.
%F A(row,col) = A101080(col, A268820(row, row+col)).
%F A(n, k) = A101080(k, A003188(n+A006068(k))). - _Antti Karttunen_, Mar 11 2024
%e The top left [0 .. 24] X [0 .. 24] section of the array:
%e 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
%e 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
%e 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2
%e 1, 3, 3, 1, 3, 1, 1, 3, 3, 1, 1, 3, 1, 3, 3, 1, 3, 1, 1, 3, 1, 3, 3, 1, 1
%e 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2
%e 3, 1, 3, 3, 3, 3, 3, 1, 3, 3, 3, 1, 3, 1, 3, 3, 3, 3, 3, 1, 3, 1, 3, 3, 3
%e 2, 2, 4, 4, 4, 4, 2, 2, 4, 4, 2, 2, 2, 2, 4, 4, 4, 4, 2, 2, 2, 2, 4, 4, 2
%e 1, 3, 3, 3, 3, 3, 1, 3, 3, 3, 1, 3, 1, 3, 3, 3, 3, 3, 1, 3, 1, 3, 3, 3, 1
%e 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2
%e 3, 3, 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 3, 3, 3, 3, 3, 3, 3, 1, 3, 3
%e 4, 4, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 2, 4, 4, 4, 4, 4, 4, 2, 2, 4
%e 3, 3, 3, 1, 5, 3, 3, 5, 5, 3, 3, 5, 3, 3, 3, 1, 5, 3, 3, 5, 3, 3, 3, 1, 3
%e 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 2, 4, 4, 4, 4, 2, 2, 2, 2, 2
%e 3, 1, 3, 3, 3, 5, 5, 3, 3, 5, 5, 3, 3, 1, 3, 3, 3, 5, 5, 3, 3, 1, 3, 3, 3
%e 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 2, 4, 4, 4, 4, 4, 4, 2, 2, 4, 4, 2
%e 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 3, 3, 3, 3, 3, 3, 3, 1, 3, 3, 3, 1
%e 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2
%e 3, 3, 3, 3, 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3
%e 4, 4, 4, 4, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
%e 3, 5, 5, 3, 3, 1, 3, 3, 5, 3, 3, 5, 3, 5, 5, 3, 5, 3, 3, 5, 3, 5, 5, 3, 3
%e 4, 4, 4, 4, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
%e 5, 3, 3, 5, 3, 3, 3, 1, 5, 5, 5, 3, 5, 3, 5, 5, 5, 5, 5, 3, 5, 3, 5, 5, 5
%e 4, 4, 4, 4, 4, 4, 2, 2, 6, 6, 4, 4, 4, 4, 6, 6, 6, 6, 4, 4, 4, 4, 6, 6, 4
%e 3, 3, 3, 3, 3, 3, 1, 3, 5, 5, 3, 5, 3, 5, 5, 5, 5, 5, 3, 5, 3, 5, 5, 5, 3
%e 2, 2, 2, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2
%t A101080[n_, k_]:= DigitCount[BitXor[n, k], 2, 1];A003188[n_]:=BitXor[n, Floor[n/2]]; A006068[n_]:=If[n<2, n, Block[{m=A006068[Floor[n/2]]}, 2m + Mod[Mod[n,2] + Mod[m, 2], 2]]]; a[r_, 0]:= 0; a[0, c_]:=c; a[r_, c_]:= A003188[1 + A006068[a[r - 1, c - 1]]]; A[r_, c_]:=A101080[c, a[r, r + c]]; Table[A[c, r - c], {r, 0, 20}, {c, 0, r}] // Flatten (* _Indranil Ghosh_, Apr 02 2017 *)
%o (Scheme)
%o (define (A268833 n) (A268833bi (A002262 n) (A025581 n)))
%o (define (A268833bi row col) (A101080bi col (A268820bi row (+ row col))))
%o (PARI) b(n) = if(n<1, 0, b(n\2) + n%2);
%o A101080(n, k) = b(bitxor(n, k));
%o A003188(n) = bitxor(n, n\2);
%o A006068(n) = if(n<2, n, {my(m = A006068(n\2)); 2*m + (n%2 + m%2)%2});
%o A268820(r, c) = if(r==0, c, if(c==0, 0, A003188(1 + A006068(A268820(r - 1, c - 1)))));
%o A(r, c) = A101080(c, A268820(r, r + c));
%o for(r=0, 20, for(c=0, r, print1(A(c, r - c),", ");); print();) \\ _Indranil Ghosh_, Apr 02 2017
%o (PARI)
%o up_to = 32895; \\ = binomial(1+256,2)-1.\\ A003188 and A006068 as above.
%o A268833sq(n, k) = hammingweight(bitxor(n,A003188(k+A006068(n))));
%o A268833list(up_to) = { my(v = vector(up_to), i=0); for(a=0,oo, for(col=0,a, i++; if(i > up_to, return(v)); v[i] = A268833sq(a-col,col))); (v); };
%o v268833 = A268833list(1+up_to);
%o A268833(n) = v268833[1+n]; \\ _Antti Karttunen_, Mar 11 2024
%o (Python)
%o def A101080(n, k): return bin(n^k)[2:].count("1")
%o def A003188(n): return n^(n//2)
%o def A006068(n):
%o if n<2: return n
%o else:
%o m=A006068(n//2)
%o return 2*m + (n%2 + m%2)%2
%o def A268820(r, c): return c if r<1 else 0 if c<1 else A003188(1 + A006068(A268820(r - 1, c - 1)))
%o def a(r, c): return A101080(c, A268820(r, r + c))
%o for r in range(21):
%o print([a(c, r - c) for c in range(r + 1)]) # _Indranil Ghosh_, Apr 02 2017
%Y Transpose A268834.
%Y Main diagonal: A268835.
%Y Column 0: A005811.
%Y Row 0: A000004, Row 1: A000012, Row 2: A007395, Row 3: A268676.
%Y Cf. A003188, A006068.
%Y Cf. also A268726, A268727.
%K nonn,tabl
%O 0,6
%A _Antti Karttunen_, Feb 15 2016
%E Definition simplified by _Antti Karttunen_, Mar 11 2024
|
