cp's OEIS Frontend

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

%I A384543 #23 Jun 10 2025 19:55:54
%S A384543 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,
%T A384543 32,32,32,32,32,32,63,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,
%U A384543 64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,127,128,128
%N A384543 Number of distinct values from the bitwise operation i XOR j for all integers i and j in the range [1, n].
%C A384543 For any n, the maximum value of (i XOR j) is < 2^floor(log_2(n))+1.
%F A384543 a(2^k) = A000225(k+1) for k > 1.
%F A384543 a(2^k-1) = A151821(k).
%F A384543 a(2^k+1) = A000079(k+1).
%F A384543 a(n) = 2^k if 2^(k-1) < n < 2^k with k=2^floor(log_2(n))+1.
%e A384543 For n=3, a(3) = 4 because:
%e A384543  i | j | i XOR j
%e A384543 ---+---+-------
%e A384543  1 | 1 | 0
%e A384543  1 | 2 | 3
%e A384543  1 | 3 | 2
%e A384543  2 | 1 | 3
%e A384543  2 | 2 | 0
%e A384543  2 | 3 | 1
%e A384543  3 | 1 | 2
%e A384543  3 | 2 | 1
%e A384543  3 | 3 | 0
%e A384543 In total there are 4 unique values for i XOR j.
%t A384543 a[n_] := CountDistinct[Flatten[Table[BitXor[i, j], {i, 1, n}, {j, 1, i}]]]; Array[a, 100] (* _Amiram Eldar_, Jun 02 2025 *)
%o A384543 (Python)
%o A384543 def a(n):
%o A384543     if n < 4: return [1,1,2,4][n]
%o A384543     k2 = 1 << n.bit_length()
%o A384543     if (n & (n - 1)) == 0: return k2 - 1
%o A384543     return k2
%o A384543 print([a(n) for n in range(1, 68)])
%o A384543 (PARI) a(n) = #setbinop((x,y)->bitxor(x,y), [1..n]); \\ _Michel Marcus_, Jun 02 2025
%Y A384543 Cf. A000079, A000225, A070939, A151821.
%K A384543 nonn,base
%O A384543 1,2
%A A384543 _Darío Clavijo_, Jun 02 2025