A222423 -id:A222423 - cp's OEIS frontend

A080099 Triangle T(n,k) = n AND k, 0<=k<=n, bitwise logical AND, read by rows.

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

Offset: 0

Reinhard Zumkeller, Jan 28 2003

A080100(n) = number of numbers k such that n AND k = 0 in n-th row of the triangular array.

			Triangle starts:
0
0 1
0 0 2
0 1 2 3
0 0 0 0 4
0 1 0 1 4 5
0 0 2 2 4 4 6
0 1 2 3 4 5 6 7
...

Rick L. Shepherd, Rows n=0..500 of triangle, flattened
Eric Weisstein's World of Mathematics, AND.

Cf. A080100, A222423 (row sums), A004198 (array).

Other triangles: A080098 (OR), A051933 (XOR), A265705 (IMPL), A102037 (CNIMPL).

import Data.Bits ((.&.))
a080099 n k = n .&. k :: Int
a080099_row n = map (a080099 n) [0..n]
a080099_tabl = map a080099_row [0..]
-- Reinhard Zumkeller, Aug 03 2014, Jul 05 2012

Column[Table[BitAnd[n, k], {n, 0, 15}, {k, 0, n}], Center] (* Alonso del Arte, Jun 19 2012 *)

T(n,k)=bitand(n,k) \\ Charles R Greathouse IV, Jan 26 2013

def T(n, k): return n & k
print([T(n, k) for n in range(14) for k in range(n+1)]) # Michael S. Branicky, Dec 16 2021

A224915 a(n) = Sum_{k=0..n} n XOR k where XOR is the bitwise logical exclusive-or operator.

Original entry on oeis.org

0, 1, 5, 6, 22, 23, 27, 28, 92, 93, 97, 98, 114, 115, 119, 120, 376, 377, 381, 382, 398, 399, 403, 404, 468, 469, 473, 474, 490, 491, 495, 496, 1520, 1521, 1525, 1526, 1542, 1543, 1547, 1548, 1612, 1613, 1617, 1618, 1634, 1635, 1639, 1640, 1896, 1897, 1901, 1902, 1918

Offset: 0

Alex Ratushnyak, Apr 19 2013

			a(2) = (0 xor 2) + (1 xor 2) = 2 + 3 = 5.

Michael De Vlieger, Table of n, a(n) for n = 0..10000

Cf. A001196 (bit doubling).
Row sums of A051933.
Other sums: A222423 (AND), A350093 (OR), A265736 (IMPL), A350094 (CNIMPL), A004125 (mod).

read("transforms"):
A051933 := proc(n,k)
    XORnos(n,k) ;
end proc:
A224915 := proc(n)
    add(A051933(n,k),k=0..n) ;
end proc: # R. J. Mathar, Apr 26 2013
# second Maple program:
with(MmaTranslator[Mma]):
seq(add(BitXor(n,i),i=0..n),n=0..60); # Ridouane Oudra, Dec 09 2020

Array[Sum[BitXor[#, k], {k, 0, #}] &, 53, 0] (* Michael De Vlieger, Dec 09 2020 *)

a(n) = sum(k=0, n, bitxor(n, k)); \\ Michel Marcus, Jun 08 2019

a(n) = (3*fromdigits(binary(n),4) - n) >>1; \\ Kevin Ryde, Dec 17 2021

for n in range(59):
    s = 0
    for k in range(n):  s += n ^ k
    print(s, end=',')

def A224915(n): return 3*int(bin(n)[2:],4)-n>>1 # Chai Wah Wu, Aug 21 2023

a(n) = Sum_{j=1..n} 4^(v_2(j)), where v_2(j) is the exponent of highest power of 2 dividing j. - Ridouane Oudra, Jun 08 2019
a(n) = n + 3*Sum_{j=1..floor(log_2(n))} 4^(j-1)*floor(n/2^j), for n>=1. - Ridouane Oudra, Dec 09 2020
From Kevin Ryde, Dec 17 2021: (Start)
a(2*n+b) = 4*a(n) + n + b where b = 0 or 1.
a(n) = (A001196(n) - n)/2.
a(n) = A350093(n) - A222423(n), being XOR = OR - AND.
(End)

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

cp's OEIS Frontend

A080099 Triangle T(n,k) = n AND k, 0<=k<=n, bitwise logical AND, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

A224915 a(n) = Sum_{k=0..n} n XOR k where XOR is the bitwise logical exclusive-or operator.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Python

Formula

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