The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A048720 Multiplication table {0..i} X {0..j} of binary polynomials (polynomials over GF(2)) interpreted as binary vectors, then written in base 10; or, binary multiplication without carries. 148
 0, 0, 0, 0, 1, 0, 0, 2, 2, 0, 0, 3, 4, 3, 0, 0, 4, 6, 6, 4, 0, 0, 5, 8, 5, 8, 5, 0, 0, 6, 10, 12, 12, 10, 6, 0, 0, 7, 12, 15, 16, 15, 12, 7, 0, 0, 8, 14, 10, 20, 20, 10, 14, 8, 0, 0, 9, 16, 9, 24, 17, 24, 9, 16, 9, 0, 0, 10, 18, 24, 28, 30, 30, 28, 24, 18, 10, 0, 0, 11, 20, 27, 32, 27, 20, 27, 32, 27, 20, 11, 0 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 0,8 COMMENTS Essentially same as A091257 but computed starting from offset 0 instead of 1. Each polynomial in GF(2)[X] is encoded as the number whose binary representation is given by the coefficients of the polynomial, e.g., 13 = 2^3 + 2^2 + 2^0 = 1101_2 encodes 1*X^3 + 1*X^2 + 0*X^1 + 1*X^0 = X^3 + X^2 + X^0. - Antti Karttunen and Peter Munn, Jan 22 2021 LINKS Antti Karttunen, Scheme-program for computing this sequence. N. J. A. Sloane, Transforms: Maple implementation of binary eXclusive OR (XORnos). FORMULA a(n) = Xmult( (((trinv(n)-1)*(((1/2)*trinv(n))+1))-n), (n-((trinv(n)*(trinv(n)-1))/2)) ); T(2b, c)=T(c, 2b)=T(b, 2c)=2T(b, c); T(2b+1, c)=T(c, 2b+1)=2T(b, c) XOR c - Henry Bottomley, Mar 16 2001 For n >= 0, A003188(2n) = T(n, 3); A003188(2n+1) = T(n, 3) XOR 1, where XOR is the bitwise exclusive-or operator, A003987. - Peter Munn, Feb 11 2021 EXAMPLE Top left corner of array: 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 ... 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 ... 0  2  4  6  8 10 12 14 16 18 20 22 24 26 28 30 ... 0  3  6  5 12 15 10  9 24 27 30 29 20 23 18 17 ... ... From Antti Karttunen and Peter Munn, Jan 23 2021: (Start) Multiplying 10 (= 1010_2) and 11 (= 1011_2), in binary results in:      1011   *  1010   -------    c1011   1011   -------   1101110  (110 in decimal), and we see that there is a carry-bit (marked c) affecting the result. In carryless binary multiplication, the second part of the process (in which the intermediate results are summed) looks like this:     1011   1011   -------   1001110  (78 in decimal). (End) MAPLE trinv := n -> floor((1+sqrt(1+8*n))/2); # Gives integral inverses of the triangular numbers # Binary multiplication of nn and mm, but without carries (use XOR instead of ADD): Xmult := proc(nn, mm) local n, m, s; n := nn; m := mm; s := 0; while (n > 0) do if(1 = (n mod 2)) then s := XORnos(s, m); fi; n := floor(n/2); # Shift n right one bit. m := m*2; # Shift m left one bit. od; RETURN(s); end; MATHEMATICA trinv[n_] := Floor[(1 + Sqrt[1 + 8*n])/2]; Xmult[nn_, mm_] := Module[{n = nn, m = mm, s = 0}, While[n > 0, If[1 == Mod[n, 2], s = BitXor[s, m]]; n = Floor[n/2]; m = m*2]; Return[s]]; a[n_] := Xmult[(trinv[n] - 1)*((1/2)*trinv[n] + 1) - n, n - (trinv[n]*(trinv[n] - 1))/2]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Mar 16 2015, updated Mar 06 2016 after Maple *) PROG (PARI) up_to = 104; A048720sq(b, c) = fromdigits(Vec(Pol(binary(b))*Pol(binary(c)))%2, 2); A048720list(up_to) = { my(v = vector(1+up_to), i=0); for(a=0, oo, for(col=0, a, i++; if(i > up_to, return(v)); v[i] = A048720sq(col, a-col))); (v); }; v048720 = A048720list(up_to); A048720(n) = v048720[1+n]; \\ Antti Karttunen, Feb 15 2021 CROSSREFS Cf. A051776 (Nim-product), A091257 (subtable). Carryless multiplication in other bases: A325820 (3), A059692 (10). Ordinary {0..i} * {0..j} multiplication table: A004247 and its differences from this: A061858 (which lists further sequences related to presence/absence of carry in binary multiplication). Carryless product of the prime factors of n: A234741. Binary irreducible polynomials ("X-primes"): A014580, factorization table: A256170, table of "X-powers": A048723, powers of 3: A001317, rearranged subtable with distinct terms (comparable to A054582): A277820. See A014580 for further sequences related to the difference between factorization into GF(2)[X] irreducibles and ordinary prime factorization of the integer encoding. Row/column 3: A048724 (even bisection of A003188), 5: A048725, 6: A048726, 7: A048727; main diagonal: A000695. Associated additive operation: A003987. Equivalent sequences, as compared with standard integer multiplication: A048631 (factorials), A091242 (composites), A091255 (gcd), A091256 (lcm), A280500 (division). See A091202 (and its variants) and A278233 for maps from/to ordinary multiplication. See A115871, A115872 and A277320 for tables related to cross-domain congruences. Sequence in context: A263139 A063711 A057893 * A067138 A059692 A336225 Adjacent sequences:  A048717 A048718 A048719 * A048721 A048722 A048723 KEYWORD nonn,tabl AUTHOR Antti Karttunen, Apr 26 1999 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 12 19:42 EDT 2021. Contains 344961 sequences. (Running on oeis4.)