%I #10 Feb 09 2020 04:31:30
%S 0,0,0,2,0,4,8,14,0,8,16,26,32,44,56,54,0,16,32,50,64,84,104,126,128,
%T 152,176,170,224,252,216,198,0,32,64,98,128,164,200,238,256,296,336,
%U 378,416,396,504,470,512,560,608,594,704,756,680,670,896,952,1008
%N A GF(2) polynomial analog of triangular numbers.
%C The k-th bit in a(n) is one just if there are an odd number of pairs of distinct one bits i#j in n such that i+j=k. GF(2) polynomial ("XOR numbral") multiplication can be implemented as A048720(i,j) = A000695(i AND j) XOR a(i AND j) XOR a(i IOR j) XOR a(i AND NOT j) XOR a(NOT i AND j), analogously to ordinary multiplication (A003991) ij = tri(i+j)-tri(i)-tri(j) via triangular numbers (A000217).
%D Posting by Richard C. Schroeppel to math-fun mailing list, Jun 26 2006.
%H Rémy Sigrist, <a href="/A120710/b120710.txt">Table of n, a(n) for n = 0..8192</a>
%F a(0)=0; a(n + 2^k) = a(n) XOR (n * 2^k), 0<=n<2^k.
%e a(15)=54 because 15=2^0+2^1+2^2+2^3, the four one-bits giving six distinct pairs 01 02 03 12 13 23, which sum to 1 2 3 3 4 5, of which 1 2 4 and 5 occur oddly, yielding 2^1+2^2+2^4+2^5=54.
%o (PARI) a(n) = { if (n==0, return (0), my (k=#binary(n)-1, m=n-2^k); return (bitxor(m*2^k, a(m)))) } \\ _Rémy Sigrist_, Feb 08 2020
%Y Cf. A048720, A000695, A003991, A000217.
%K base,easy,nonn
%O 0,4
%A _Marc LeBrun_, Jun 28 2006
%E Data corrected by _Rémy Sigrist_, Feb 08 2020
|