OFFSET
0,2
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
LINKS
Reinhard Zumkeller, Table of n, a(n) for n = 0..16383
J. W. Layman, View fractal-like graph
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
EXAMPLE
a(15)=5, since 15 = 33_4 -> 11_4 = 5.
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 *)
PROG
(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
(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
(C) uint32_t a(uint32_t n) { return n ^ ((n & 0x55555555) << 1); } // Falk Hüffner, Jan 22 2022
CROSSREFS
KEYWORD
AUTHOR
John W. Layman, Jul 05 1999
STATUS
approved