A048726 -id:A048726 - cp's OEIS frontend

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.

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

Offset: 0

Antti Karttunen, Apr 26 1999

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
To listen to this sequence, I find instrument 99 (crystal) works well with the other parameters defaulted. - Peter Munn, Nov 01 2022

			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)

Alois P. Heinz, Antidiagonals n = 0..200, flattened
Antti Karttunen, Scheme-program for computing this sequence.
N. J. A. Sloane, Transforms: Maple implementation of binary eXclusive OR (XORnos).
Index entries for sequences related to carryless arithmetic
Index entries for sequences related to polynomials in ring GF(2)[X]

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.

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;

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 *)

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

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

A048724 Write n and 2n in binary and add them mod 2.

Original entry on oeis.org

0, 3, 6, 5, 12, 15, 10, 9, 24, 27, 30, 29, 20, 23, 18, 17, 48, 51, 54, 53, 60, 63, 58, 57, 40, 43, 46, 45, 36, 39, 34, 33, 96, 99, 102, 101, 108, 111, 106, 105, 120, 123, 126, 125, 116, 119, 114, 113, 80, 83, 86, 85, 92, 95, 90, 89, 72, 75, 78, 77, 68, 71, 66, 65, 192

Offset: 0

Antti Karttunen, Apr 26 1999

Reversing binary representation of -n. Converting sum of powers of 2 in binary representation of a(n) to alternating sum gives -n. Note that the alternation is applied only to the nonzero bits and does not depend on the exponent of two. All integers have a unique reversing binary representation (see cited exercise for proof). Complement of A065621. - Marc LeBrun, Nov 07 2001
A permutation of the "evil" numbers A001969. - Marc LeBrun, Nov 07 2001
A048725(n) = a(a(n)). - Reinhard Zumkeller, Nov 12 2004

			12 = 1100 in binary, 24=11000 and their sum is 10100=20, so a(12)=20.
a(4) = 12 = + 8 + 4 -> - 8 + 4 = -4.

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1969, Vol. 2, p. 178, (exercise 4.1. Nr. 27)

T. D. Noe, Table of n, a(n) for n = 0..1023
P. Mathonet, M. Rigo, M. Stipulanti and N. Zénaïdi, On digital sequences associated with Pascal's triangle, arXiv:2201.06636 [math.NT], 2022.
H. D. Nguyen, A mixing of Prouhet-Thue-Morse sequences and Rademacher functions, 2014. See Example 20. - _N. J. A. Sloane_, May 24 2014
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

Cf. A048720, A048725, A048726, A048728.
Bisection of A003188 (even part).
See also A065620, A065621.
Cf. A242399.

import Data.Bits (xor, shiftL)
a048724 n = n `xor` shiftL n 1 :: Integer
-- Reinhard Zumkeller, Mar 06 2013

a:= n-> Bits[Xor](n, n+n):
seq(a(n), n=0..100);  # Alois P. Heinz, Apr 06 2016

Table[ BitXor[2n, n], {n, 0, 65}] (* Robert G. Wilson v, Jul 06 2006 *)

a(n)=bitxor(n,2*n) \\ Charles R Greathouse IV, Jan 04 2013

def A048724(n): return n^(n<<1) # Chai Wah Wu, Apr 05 2021

a(n) = Xmult(n, 3) (or n XOR (n<<1)).
a(n) = A065621(-n).
a(2n) = 2a(n), a(2n+1) = 2a(n) + 2(-1)^n + 1.
G.f. 1/(1-x) * sum(k>=0, 2^k*(3t-t^3)/(1+t)/(1+t^2), t=x^2^k). - Ralf Stephan, Sep 08 2003
a(n) = sum(k=0, n, (1-(-1)^round(+n/2^k))/2*2^k). - Benoit Cloitre, Apr 27 2005
a(n) = A001969(A003188(n)). - Philippe Deléham, Apr 29 2005
a(n) = A106409(2*n) for n>0. - Reinhard Zumkeller, May 02 2005
a(n) = A142149(2*n). - Reinhard Zumkeller, Jul 15 2008

A117998 Decimal number generated by the binary bits of the n-th generation of the Rule 102 elementary cellular automaton.

Original entry on oeis.org

1, 6, 20, 120, 272, 1632, 5440, 32640, 65792, 394752, 1315840, 7895040, 17895424, 107372544, 357908480, 2147450880, 4295032832, 25770196992, 85900656640, 515403939840, 1168248930304, 7009493581824, 23364978606080

Offset: 0

Eric W. Weisstein, Apr 08 2006

Central diagonal of A099884 when viewed as a square array. Thus also a subsequence of A118666. - Antti Karttunen, Jan 18 2020

			1; 1, 1, 0; 1, 0, 1, 0, 0; 1, 1, 1, 1, 0, 0, 0; 1, 0, 0, 0, 1, 0, 0, 0, 0; ...

Robert Price, Table of n, a(n) for n = 0..999
Eric Weisstein's World of Mathematics, Rule 102
Index entries for sequences related to binary expansion of n
Index entries for sequences related to cellular automata
Index entries for sequences related to polynomials in ring GF(2)[X]

Iterates of A048726, starting from a(0) = 1.
Central diagonal of A099884. Bisection of A099885. Subsequence of A118666.
Cf. A000079, A001317, A193231.

NestList[BitXor[4#,2#]&,1,50] (* Paolo Xausa, Oct 04 2023 *)

A117998(n) = (subst(lift(Mod(1+'x, 2)^n), 'x, 2)<Antti Karttunen, Jan 19 2020, after Gheorghe Coserea's code for A001317.

def A117998(n): return sum((bool(~n&n-k)^1)<Chai Wah Wu, May 03 2023

It appears that a(n) = A099885(2*n). - Peter Bala, Feb 01 2017
From Antti Karttunen, Jan 19 2020: (Start)
Bala's observation is correct, and follows from the formula given below and from the fact that this is the central diagonal of square array A099884.
a(n) = A000079(n) * A001317(n). [See Eric Weisstein's World of Mathematics -link]
a(0) = 1; for n > 0, a(n) = A048726(a(n-1)).
(End)

A377292 Terms of A118666 as produced by the program given there (without the final sorting).

Original entry on oeis.org

0, 1, 6, 7, 20, 18, 21, 19, 120, 108, 126, 106, 121, 109, 127, 107, 272, 360, 260, 380, 278, 366, 258, 378, 273, 361, 261, 381, 279, 367, 259, 379, 1632, 1904, 1560, 1800, 1652, 1892, 1548, 1820, 1638, 1910, 1566, 1806, 1650, 1890, 1546, 1818, 1633, 1905, 1561, 1801

Offset: 0

Darío Clavijo, Dec 27 2024

nonn

Joerg Arndt, Matters Computational (The Fxtbook), section 1.19.3 "Fixed points of the blue code", p.52-54, with a(n) = blue_fixed_point(n).
Index entries for sequences operating on (or containing) GF(2)[X]-polynomials

Cf. A118666, A117998.

A048726 = lambda n: (n << 2) ^ (n << 1)
def a(n):
    if n == 0: return 0
    f, s = 1, n
    while s > 1:
        f = A048726(f) | (s & 1)
        s >>= 1
    return f
print([a(n) for n in range(0, 52)])

a(2^k) = A117998(k).

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A048724 Write n and 2n in binary and add them mod 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A117998 Decimal number generated by the binary bits of the n-th generation of the Rule 102 elementary cellular automaton.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A377292 Terms of A118666 as produced by the program given there (without the final sorting).

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Formula