A380110 In the base 4 expansion of n: map 0->0, 1->1, 2->1, 3->2.

0, 1, 1, 2, 4, 5, 5, 6, 4, 5, 5, 6, 8, 9, 9, 10, 16, 17, 17, 18, 20, 21, 21, 22, 20, 21, 21, 22, 24, 25, 25, 26, 16, 17, 17, 18, 20, 21, 21, 22, 20, 21, 21, 22, 24, 25, 25, 26, 32, 33, 33, 34, 36, 37, 37, 38, 36, 37, 37, 38, 40, 41, 41, 42, 64, 65, 65, 66, 68, 69

Offset

0,4

Comments

This is essentialy the mapping of the half adder where the inputs A,B maps to outputs: C_out and S as in binary: 00->00, 01->01, 10->01, 11->10, where C_out is the carry out bit and S is the sum bit.

The fixed points for this sequence are in the Moser-de Bruijn sequence (A000695).

Links

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

Wikipedia, Adder (electronics)

Formula

a(n) = n iff n in A000695.

a(2^k) = A213173(n).

a(n) = a(n-1)+1 if n odd.

a(n) = n-A063695(n)/2.

Example

Half adder truth table:
 A | B | C_out | S
---+---+-------+------
 0 | 0 | 0     | 0
 0 | 1 | 0     | 1
 1 | 0 | 0     | 1
 1 | 1 | 1     | 0
For n = 25 a(25) = 21 because:
25 = 121_4 and 121_4 maps to 111_4 which is 21.

Mathematica

A380110[n_] := FromDigits[ReplaceAll[IntegerDigits[n, 4], {2 -> 1, 3 -> 2}], 4];
Array[A380110, 100, 0] (* Paolo Xausa, Feb 27 2025 *)

Prog

(Python)
def a(n):
    r, p = 0, 1
    while n:
        ps = (n & 1) + ((n >> 1) & 1)
        r += ps * p
        n >>= 2
        p <<= 2
    return r
print([a(n) for n in range(70)])

Crossrefs

Cf. A000079, A000695, A063695, A213173.

Sequence in context: A317749 A253415 A227401 * A131813 A083038 A061008

Adjacent sequences: A380107 A380108 A380109 * A380111 A380112 A380113

Keyword

nonn,base,easy,new

Author

Darío Clavijo, Feb 14 2025

Status

approved