A335133 Binary interpretation of the left diagonal of the EQ-triangle with first row generated from the binary expansion of n, with most significant bit given by first row.

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 10, 13, 12, 14, 15, 16, 17, 18, 19, 22, 23, 20, 21, 26, 27, 24, 25, 28, 29, 30, 31, 32, 33, 35, 34, 36, 37, 39, 38, 44, 45, 47, 46, 40, 41, 43, 42, 53, 52, 54, 55, 49, 48, 50, 51, 57, 56, 58, 59, 61, 60, 62, 63, 64, 65, 66, 67

Offset: 0

Author

Rémy Sigrist, May 24 2020

Keywords

• nonn
• look
• base

Comments

For any nonnegative number n, the EQ-triangle for n is built by taking as first row the binary expansion of n (without leading zeros), having each entry in the subsequent rows be the EQ of the two values above it (a "1" indicates that these two values are equal, a "0" indicates that these values are different).

This sequence is a self-inverse permutation of the nonnegative numbers.

Examples

			For n = 42:
- the binary representation of 42 is "101010",
- the corresponding EQ-triangle is:
         1 0 1 0 1 0
          0 0 0 0 0
           1 1 1 1
            1 1 1
             1 1
              1
- the bits on the left diagonal are: 1, 0, 1, 1, 1, 1,
- so a(42) = 2^5 + 2^3 + 2^2 + 2^1 + 2^0 = 47.
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..8192 (n = 0..2^13)
• Index entries for sequences related to binary expansion of n
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A055010, A070939, A279645, A334727 (XOR variant).

Programs

PARI

a(n) = {
    my (b=binary(n), v=0);
    forstep (x=#b-1, 0, -1,
        if (b[1], v+=2^x);
        b=vector(#b-1, k, b[k]==b[k+1])
    );
    return (v)
}

Formula

a(floor(n/2)) = floor(a(n)/2).

abs(a(2*n+1) - a(2*n)) = 1.

a(2^k) = 2^k for any k >= 0.

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

a(2^k-1) = 2^k-1 for any k >= 0.

Apparently, a(n) + A334727(n) = A055010(A070939(n)) for any n > 0.