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

Author

Darío Clavijo, Feb 14 2025

Keywords

• nonn
• base
• easy

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

Examples

			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.
		

Links

• Paolo Xausa, Table of n, a(n) for n = 0..10000
• Wikipedia, Adder (electronics)

Crossrefs

Cf. A000079, A000695, A063695, A213173.

Programs

Mathematica

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

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

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.