A247891 a(n) is Gray-coded in base 4 into n.

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

Offset: 0

Author

Alex Ratushnyak, Sep 26 2014

Keywords

• nonn
• base

Comments

Permutation of nonnegative numbers.

Links

• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A006068 (base 2), A105529 (base 3), A226134 (base 10).

Programs

Python

def basexor(a, b, base):
  result = 0
  digit = 1
  while a or b:
    da = a % base
    db = b % base
    a //= base
    b //= base
    sum = (da+db) % base
    result += sum * digit
    digit *= base
  return result
base = 4  #  2 => A006068, 3 => A105529, 10 => A226134
for n in range(129):
  a = n
  b = n//base
  while b:
    a = basexor(a,b, base)
    b //= base
  print(a, end=', ')

Python

def xor4(x, y): return 4*xor4(x//4, y//4) + (x+y)%4 if x else y
def a(n): return xor4(n, a(n//4)) if n else 0 # David Radcliffe, Jun 22 2025

Formula

a(n) = n XOR4 [n/4] XOR4 [n/16] XOR4 [n/64] ... XOR4 [n/4^m] where m = [log(n)/log(4)], [x] is integer floor of x, and XOR4 is a base 4 analog of binary exclusive-OR operator.

In other words, a(n) = n + [n/4] + [n/16] + ... where addition is performed in base 4 without carries. - David Radcliffe, Jun 22 2025