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,3

Comments

Permutation of nonnegative numbers.

Links

Table of n, a(n) for n=0..68.

Index entries for sequences that are permutations of the natural numbers

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

Prog

(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

Crossrefs

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

Sequence in context: A339949 A160100 A371257 * A367407 A354370 A113821

Adjacent sequences: A247888 A247889 A247890 * A247892 A247893 A247894

Keyword

nonn,base

Author

Alex Ratushnyak, Sep 26 2014

Status

approved