A224915 -id:A224915 - cp's OEIS frontend

A051933 Triangle T(n,m) = Nim-sum (or XOR) of n and m, read by rows, 0<=m<=n.

0, 1, 0, 2, 3, 0, 3, 2, 1, 0, 4, 5, 6, 7, 0, 5, 4, 7, 6, 1, 0, 6, 7, 4, 5, 2, 3, 0, 7, 6, 5, 4, 3, 2, 1, 0, 8, 9, 10, 11, 12, 13, 14, 15, 0, 9, 8, 11, 10, 13, 12, 15, 14, 1, 0, 10, 11, 8, 9, 14, 15, 12, 13, 2, 3, 0, 11, 10, 9, 8, 15, 14, 13, 12, 3, 2, 1, 0, 12, 13, 14, 15, 8, 9, 10, 11, 4, 5, 6, 7, 0

Offset: 0

N. J. A. Sloane, Dec 20 1999

			{0},
{1,0},
{2,3,0},
{3,2,1,0}, ...

E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Academic Press, NY, 2 vols., 1982, see p. 60.
J. H. Conway, On Numbers and Games, Academic Press, p. 52.

Reinhard Zumkeller, Rows n = 0..127 of triangle, flattened first 50 rows by R. J. Mathar
Index entries for sequences related to Nim-sums

Cf. A224915 (row sums), A003987 (array), A051910 (Nim-product).

Other triangles: A080099 (AND), A080098 (OR), A265705 (IMPL), A102037 (CNIMPL), A002262 (k).

import Data.Bits (xor)
a051933 n k = n `xor` k :: Int
a051933_row n = map (a051933 n) [0..n]
a051933_tabl = map a051933_row [0..]
-- Reinhard Zumkeller, Aug 02 2014, Aug 13 2013

using IntegerSequences
A051933Row(n) = [Bits("XOR", n, k) for k in 0:n]
for n in 0:10 println(A051933Row(n)) end  # Peter Luschny, Sep 25 2021

nimsum := proc(a,b) local t1,t2,t3,t4,l; t1 := convert(a+2^20,base,2); t2 := convert(b+2^20,base,2); t3 := evalm(t1+t2); map(x->x mod 2, t3); t4 := convert(evalm(%),list); l := convert(t4,base,2,10); sum(l[k]*10^(k-1), k=1..nops(l)); end; # memo: adjust 2^20 to be much bigger than a and b
AT := array(0..N,0..N); for a from 0 to N do for b from a to N do AT[a,b] := nimsum(a,b); AT[b,a] := AT[a,b]; od: od:
# Alternative:
A051933 := (n, k) -> Bits:-Xor(n, k):
seq(seq(A051933(n, k), k=0..n), n=0..12); # Peter Luschny, Sep 23 2019

Flatten[Table[BitXor[m, n], {m, 0, 12}, {n, 0, m}]] (* Jean-François Alcover, Apr 29 2011 *)

More terms from Michael Lugo (mlugo(AT)thelabelguy.com), Dec 22 1999

A224923 a(n) = Sum_{i=0..n} Sum_{j=0..n} (i XOR j), where XOR is the binary logical exclusive-or operator.

Original entry on oeis.org

0, 2, 12, 24, 68, 114, 168, 224, 408, 594, 788, 984, 1212, 1442, 1680, 1920, 2672, 3426, 4188, 4952, 5748, 6546, 7352, 8160, 9096, 10034, 10980, 11928, 12908, 13890, 14880, 15872, 18912, 21954, 25004, 28056, 31140, 34226, 37320, 40416, 43640, 46866, 50100, 53336, 56604

Offset: 0

Alex Ratushnyak, Apr 19 2013

Alois P. Heinz, Table of n, a(n) for n = 0..1023
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, pp. 42-43.

Cf. A004125, A222423, A224915, A224924.

Array[Sum[BitXor[i, j], {i, 0, #}, {j, 0, #}] &, 45, 0] (* Michael De Vlieger, Nov 03 2022 *)

for n in range(99):
    s = 0
    for i in range(n+1):
        for j in range(n+1):
            s += i ^ j
    print(s, end=",") # Alex Ratushnyak, Apr 19 2013

# O(log(n)) version, whereas program above is O(n^2)
def countPots2Until(n):
    nbPots = {1:n>>1}
    lftMask = ~3
    rgtMask = 1
    digit = 2
    while True:
        lft = (n & lftMask) >> 1
        rgt = n & rgtMask
        nbDigs = lft
        if n & digit:
            nbDigs |= rgt
        if nbDigs == 0:
            return nbPots
        nbPots[digit] = nbDigs
        rgtMask |= digit
        digit <<= 1
        lftMask = lftMask ^ digit
def sumXorSquare(n):
    """Returns sum(i^j for i, j <= n)"""
    n += 1
    nbPots = countPots2Until(n)
    return 2 * sum(pot * freq * (n - freq) for pot, freq in nbPots.items())
print([sumXorSquare(n) for n in range(100)])  # Miguel Garcia Diaz, Nov 19 2014

# O(log(n)) version, same as previous, but simpler and about 3x faster.
def xor_square(n: int) -> int:
    return sum((((n + 1 >> i) ** 2 >> 1 << i) +
               ((n + 1) & ((1 << i) - 1)) * (n + 1 + (1 << i) >> i + 1 << 1)
               << 2 * i) for i in range(n.bit_length()))
print([xor_square(n) for n in range(100)]) # Gabriel F. Ushijima, Feb 24 2024

A224924 Sum_{i=0..n} Sum_{j=0..n} (i AND j), where AND is the binary logical AND operator.

Original entry on oeis.org

0, 1, 3, 12, 16, 33, 63, 112, 120, 153, 211, 300, 408, 553, 735, 960, 976, 1041, 1155, 1324, 1536, 1809, 2143, 2544, 2952, 3433, 3987, 4620, 5320, 6105, 6975, 7936, 7968, 8097, 8323, 8652, 9072, 9601, 10239, 10992, 11800, 12729, 13779, 14956, 16248, 17673, 19231, 20928

Offset: 0

Alex Ratushnyak, Apr 19 2013

For n>0, a(2^n)-A000217(2^n)=a(2^n-1)-A000217(2^n-1) [See links]. - R. J. Cano, Aug 21 2013

Enrique Pérez Herrero, Table of n, a(n) for n = 0..1000
R. J. Cano, Additional information
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, pp. 42-43.

Cf. A004125, A222423, A224915, A224923, A000217.

read("transforms") :
A224924 := proc(n)
    local a,i,j ;
    a := 0 ;
    for i from 0 to n do
    for j from 0 to n do
        a := a+ANDnos(i,j) ;
    end do:
    end do:
    a ;
end proc: # R. J. Mathar, Aug 22 2013

a[n_] := Sum[BitAnd[i, j], {i, 0, n}, {j, 0, n}];
Table[a[n], {n, 0, 20}]
(* Enrique Pérez Herrero, May 30 2015 *)

a(n)=sum(i=0,n,sum(j=0,n,bitand(i,j))); \\ R. J. Cano, Aug 21 2013

for n in range(99):
    s = 0
    for i in range(n+1):
      for j in range(n+1):
        s += i & j
    print(s, end=',')

a(2^n) = a(2^n - 1) + 2^n.

a(n) -a(n-1) = 2*A222423(n) -n. - R. J. Mathar, Aug 22 2013

A350093 a(n) = Sum_{k=0..n} n OR k where OR is the bitwise logical OR operator (A003986).

Original entry on oeis.org

0, 2, 7, 12, 26, 34, 45, 56, 100, 114, 131, 148, 174, 194, 217, 240, 392, 418, 447, 476, 514, 546, 581, 616, 684, 722, 763, 804, 854, 898, 945, 992, 1552, 1602, 1655, 1708, 1770, 1826, 1885, 1944, 2036, 2098, 2163, 2228, 2302, 2370, 2441, 2512, 2712, 2786, 2863

Offset: 0

Kevin Ryde, Dec 14 2021

The effect of n OR k is to force a 1-bit at all bit positions where n has a 1-bit, which means n*(n+1) in the sum. Bits of k where n has a 0-bit are NOT(n) AND k = n CNIMPL k so that a(n) = A350094(n) + n*(n+1).

Winston de Greef, Table of n, a(n) for n = 0..10000

Cf. A003986 (bitwise OR), A001196 (bit doubling).
Row sums of A080098.
Other sums: A222423 (AND), A224915 (XOR), A265736 (IMPL), A350094 (CNIMPL).

a(n) = (3*(n^2 + fromdigits(binary(n),4)) + 2*n) >> 2;

a(n) = ((3*n+2)*n + A001196(n)) / 4.
a(2*n) = 4*a(n) - n.
a(2*n+1) = 4*a(n) + 2*n + 2.
a(n) = A222423(n) + A224915(n), being OR = AND + XOR.

A350094 a(n) = Sum_{k=0..n} n CNIMPL k where CNIMPL = NOT(n) AND k is the bitwise logical converse non-implication operator (A102037).

Original entry on oeis.org

0, 0, 1, 0, 6, 4, 3, 0, 28, 24, 21, 16, 18, 12, 7, 0, 120, 112, 105, 96, 94, 84, 75, 64, 84, 72, 61, 48, 42, 28, 15, 0, 496, 480, 465, 448, 438, 420, 403, 384, 396, 376, 357, 336, 322, 300, 279, 256, 360, 336, 313, 288, 270, 244, 219, 192, 196, 168, 141, 112

Offset: 0

Kevin Ryde, Dec 14 2021

The effect of NOT(n) AND k is to retain from k only those bits where n has a 0-bit. Conversely n AND k retains from k those bits where n has a 1-bit. Together they are all bits of k so that a(n) + A222423(n) = Sum_{k=0..n} k = n*(n+1)/2.

Row sums of A102037.
Cf. A001196 (bit doubling).
Other sums: A222423 (AND), A350093 (OR), A224915 (XOR), A265736 (IMPL).

with(Bits): cnimp := (n, k) -> And(Not(n), k):
seq(add(cnimp(n, k), k = 0..n), n = 0..59); # Peter Luschny, Dec 14 2021

a(n) = (3*fromdigits(binary(n),4) - n^2 - 2*n)/4;

a(n) = (A001196(n) - n*(n+2))/4.
a(2*n) = 4*a(n) + n.
a(2*n+1) = 4*a(n).

A375551 a(n) = Sum_{k=0..n} k XOR n-k, where XOR is the bitwise exclusive disjunction. Row sums of A003987.

Original entry on oeis.org

0, 2, 4, 12, 12, 22, 32, 56, 48, 58, 68, 100, 108, 142, 176, 240, 208, 210, 212, 252, 252, 294, 336, 424, 416, 458, 500, 596, 636, 734, 832, 992, 896, 866, 836, 876, 844, 886, 928, 1048, 1008, 1050, 1092, 1220, 1260, 1390, 1520, 1744, 1680, 1714, 1748, 1884, 1916

Offset: 0

Peter Luschny, Sep 27 2024

nonn

Paolo Xausa, Table of n, a(n) for n = 0..10000

Cf. A003986, A003987, A006582, A020522, A051933, A099027, A224915, A376585.

XOR := (n, k) -> Bits:-Xor(n, k):
a := n -> local k; add(XOR(k, n-k), k=0..n):
seq(a(n), n = 0..52);

(* Using definition *)
Table[Sum[BitXor[n - k, k], {k, 0, n}], {n, 0, 100}]
(* Using recurrence -- faster *)
a[0] = 0; a[n_] := a[n] = If[OddQ[n], 4*a[(n-1)/2] + n + 1, 2*(a[n/2] + a[n/2-1])];
Table[a[n], {n, 0, 100}] (* Paolo Xausa, Oct 01 2024 *)

a(n) = sum(k=0, n, bitxor(k, n-k)); \\ Michel Marcus, Sep 28 2024

a(n) = 2*A099027(n).
a(n) = 2*n + A006582(n).
a(2^n - 1) = 4^n - 2^n = A020522(n).
a(2^n) = 4^n - 2^n*(n - 1) = 2*A376585(n).
Recurrence: a(0) = 0; a(2*n) = 2*(a(n) + a(n-1)); a(2*n+1) = 2*(2*a(n) + n + 1). - Paolo Xausa, Oct 01 2024, derived from recurrence in A099027.

cp's OEIS Frontend

A051933 Triangle T(n,m) = Nim-sum (or XOR) of n and m, read by rows, 0<=m<=n.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Haskell

Julia

Maple

Mathematica

Extensions

A224923 a(n) = Sum_{i=0..n} Sum_{j=0..n} (i XOR j), where XOR is the binary logical exclusive-or operator.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Python

Python

A224924 Sum_{i=0..n} Sum_{j=0..n} (i AND j), where AND is the binary logical AND operator.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A350093 a(n) = Sum_{k=0..n} n OR k where OR is the bitwise logical OR operator (A003986).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A350094 a(n) = Sum_{k=0..n} n CNIMPL k where CNIMPL = NOT(n) AND k is the bitwise logical converse non-implication operator (A102037).

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

PARI

Formula

A375551 a(n) = Sum_{k=0..n} k XOR n-k, where XOR is the bitwise exclusive disjunction. Row sums of A003987.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula