A116640 - OEIS

%I #41 May 09 2017 11:14:08

%S 1,5,7,19,11,23,29,65,19,31,37,73,49,85,103,211,35,47,53,89,65,101,

%T 119,227,89,125,143,251,179,287,341,665,67,79,85,121,97,133,151,259,

%U 121,157,175,283,211,319,373,697,169,205,223,331,259,367,421,745,331

%N a(n) = A116623(A059893(n)).

%C Viewed as a binary tree, this is (1); 5; 7,19; 11,23,29,65; ... Cf. A116623.

%C 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

%H Robert Israel, <a href="/A116640/b116640.txt">Table of n, a(n) for n = 0..10000</a>

%H <a href="/index/3#3x1">Index entries for sequences related to 3x+1 (or Collatz) problem</a>

%F a(A000225(n)) = A001047(n+1).

%F For n>= 1 a(A000079(n)) = A062709(n+1).

%F From _Joe Slater_, Jan 19 2016: (Start)

%F a(0) = 1,

%F a(n) = 3*a(floor(n/2)) - 2*a(floor(n/4)) for n=0 (mod 4) and n>0,

%F a(n) = 6*a(floor(n/4)) - a(floor(n/2)) for n=1 (mod 4),

%F a(n) = a(floor(n/2)) + 2*a(floor(n/4)) for n=2 (mod 4),

%F a(n) = 5*a(floor(n/2)) - 6*a(floor(n/4)) for n=3 (mod 4)

%F (End)

%F a(0) = 1, a(n) = 2*a(floor(n/2)) - A033999(n) * A048883(n) for n>0. -

%F _Joe Slater_, Jan 22 2016

%p a:= proc(n) option remember; piecewise(

%p     n mod 4 = 0, 3*procname(n/2) - 2*procname(n/4),

%p   n mod 4 = 1, 6*procname((n-1)/4) - procname((n-1)/2),

%p   n mod 4 = 2, procname(n/2) + 2*procname((n-2)/4),

%p   5*procname((n-1)/2) - 6*procname((n-3)/4))

%p end proc:

%p a(0):= 1:

%p map(a, [$0..100]); # _Robert Israel_, Jan 19 2016

%t 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 *)

%o (PARI) a(n) = if(n==0, return(1)); 2*a(n\2) - (-1)^n * 3^hammingweight(n) \\ _Charles R Greathouse IV_, Jan 21 2016

%o (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

%Y Cf. A000079, A000225, A001047, A062709.

%K nonn,base,tabf

%O 0,2

%A _Antti Karttunen_, Feb 20 2006. Proposed by Pierre Lamothe (plamothe(AT)aei.ca), May 21 2004.