A384543 Number of distinct values from the bitwise operation i XOR j for all integers i and j in the range [1, n].

1, 2, 4, 7, 8, 8, 8, 15, 16, 16, 16, 16, 16, 16, 16, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 63, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 127, 128, 128

Offset: 1

Author

Darío Clavijo, Jun 02 2025

Keywords

• nonn
• base

Comments

For any n, the maximum value of (i XOR j) is < 2^floor(log_2(n))+1.

Examples

			For n=3, a(3) = 4 because:
 i | j | i XOR j
---+---+-------
 1 | 1 | 0
 1 | 2 | 3
 1 | 3 | 2
 2 | 1 | 3
 2 | 2 | 0
 2 | 3 | 1
 3 | 1 | 2
 3 | 2 | 1
 3 | 3 | 0
In total there are 4 unique values for i XOR j.
		

Crossrefs

Cf. A000079, A000225, A070939, A151821.

Programs

Mathematica

a[n_] := CountDistinct[Flatten[Table[BitXor[i, j], {i, 1, n}, {j, 1, i}]]]; Array[a, 100] (* Amiram Eldar, Jun 02 2025 *)

PARI

a(n) = #setbinop((x,y)->bitxor(x,y), [1..n]); \\ Michel Marcus, Jun 02 2025

Python

def a(n):
    if n < 4: return [1,1,2,4][n]
    k2 = 1 << n.bit_length()
    if (n & (n - 1)) == 0: return k2 - 1
    return k2
print([a(n) for n in range(1, 68)])

Formula

a(2^k) = A000225(k+1) for k > 1.

a(2^k-1) = A151821(k).

a(2^k+1) = A000079(k+1).

a(n) = 2^k if 2^(k-1) < n < 2^k with k=2^floor(log_2(n))+1.