A048647 Write n in base 4, then replace each digit '1' with '3' and vice versa and convert back to decimal.

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

Offset: 0

Author

John W. Layman, Jul 05 1999

Keywords

• nonn
• easy
• nice
• base
• look

Comments

The graph of a(n) on [ 1..4^k ] resembles a plane fractal of fractal dimension 1.

Self-inverse considered as a permutation of the integers.

First 4^n terms of the sequence form a permutation s(n) of 0..4^n-1, n>=1; the number of inversions of s(n) is A115490(n). - Gheorghe Coserea, Apr 23 2018

Examples

			a(15)=5, since 15 = 33_4 -> 11_4 = 5.
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..16383
• J. W. Layman, View fractal-like graph
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A065256, A007090.

Column k=4 of A248813.

Programs

C

uint32_t a(uint32_t n) { return n ^ ((n & 0x55555555) << 1); } // Falk Hüffner, Jan 22 2022

Haskell

a048647 0 = 0
a048647 n = 4 * a048647 n' + if m == 0 then 0 else 4 - m
            where (n', m) = divMod n 4
-- Reinhard Zumkeller, Apr 08 2013

Maple

f:= proc(n)
option remember;
local m, r;
m:= n mod 4;
r:= 4*procname((n-m)/4);
if m = 0 then r else r + 4-m fi;
end proc:
f(0):= 0:
seq(f(n),n=0..100); # Robert Israel, Nov 03 2014
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 0,
      a(iquo(n, 4, 'r'))*4+[0, 3, 2, 1][r+1])
    end:
seq(a(n), n=0..70);  # Alois P. Heinz, Jan 25 2022

Mathematica

Table[FromDigits[If[#==0,0,4-#]&/@IntegerDigits[n,4],4],{n,0,70}] (* Harvey P. Dale, Jul 23 2012 *)

PARI

a(n)=fromdigits(apply(d->if(d,4-d),digits(n,4)),4) \\ Charles R Greathouse IV, Jun 23 2017

Python

from sympy.ntheory.factor_ import digits
def a(n):
    return int("".join(str(4 - d) if d!=0 else '0' for d in digits(n, 4)[1:]), 4)
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 26 2017

Python

def A048647(n): return n^((n&((1<<(m:=n.bit_length())+(m&1))-1)//3)<<1) # Chai Wah Wu, Jan 29 2023

Formula

a(n) = if n = 0 then 0 else 4*a(floor(n/4)) + if m = 0 then 0 else 4 - m, where m = n mod 4. - Reinhard Zumkeller, Apr 08 2013

G.f. g(x) satisfies: g(x) = 4*(1+x+x^2+x^3)*g(x^4) + (3*x+2*x^2+x^3)/(1-x^4). - Robert Israel, Nov 03 2014