OFFSET
0,2
COMMENTS
Viewed as a binary tree, this is (1); 5; 7,19; 11,23,29,65; ... Cf. A116623.
If we treat (2n+1) as a binary number with the nonzero bits numbered (highest bit first) from 0..k and the regular binary place value of each nonzero bit numbered from b(0) to b(k) then a(n) = 3^0 * b(0) + 3^1 * b(1) + .. + 3^k. For instance, if n=6 then 2n+1 = 13, which is equal to 8+4+1 or 1101 base(2); and a(n)=29 which is 8*1 + 4*3 + 1*9. - Joe Slater, Jan 23 2016
LINKS
FORMULA
From Joe Slater, Jan 19 2016: (Start)
a(0) = 1,
a(n) = 3*a(floor(n/2)) - 2*a(floor(n/4)) for n=0 (mod 4) and n>0,
a(n) = 6*a(floor(n/4)) - a(floor(n/2)) for n=1 (mod 4),
a(n) = a(floor(n/2)) + 2*a(floor(n/4)) for n=2 (mod 4),
a(n) = 5*a(floor(n/2)) - 6*a(floor(n/4)) for n=3 (mod 4)
(End)
Joe Slater, Jan 22 2016
MAPLE
a:= proc(n) option remember; piecewise(
n mod 4 = 0, 3*procname(n/2) - 2*procname(n/4),
n mod 4 = 1, 6*procname((n-1)/4) - procname((n-1)/2),
n mod 4 = 2, procname(n/2) + 2*procname((n-2)/4),
5*procname((n-1)/2) - 6*procname((n-3)/4))
end proc:
a(0):= 1:
map(a, [$0..100]); # Robert Israel, Jan 19 2016
MATHEMATICA
a[n_] := a[n] = Switch[Mod[n, 4], 0, 3a[Floor[n/2]] - 2a[Floor[n/4]], 1, 6a[Floor[n/4]] - a[Floor[n/2]], 2, a[Floor[n/2]] + 2a[Floor[n/4]], 3, 5a[Floor[n/2]] - 6a[Floor[n/4]]]; a[0]=1; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Feb 28 2016 *)
PROG
(PARI) a(n) = if(n==0, return(1)); 2*a(n\2) - (-1)^n * 3^hammingweight(n) \\ Charles R Greathouse IV, Jan 21 2016
(PARI) a(n) = my(p=2*n+1, v=vecextract(vector(#binary(p), j, 2^(j-1)), p)); sum(i=0, #v-1, 3^i*v[#v-i]) \\ Joe Slater, May 09 2017
CROSSREFS
KEYWORD
nonn,base,tabf
AUTHOR
Antti Karttunen, Feb 20 2006. Proposed by Pierre Lamothe (plamothe(AT)aei.ca), May 21 2004.
STATUS
approved