A002516 - OEIS

%I #52 Sep 20 2021 04:38:27

%S 0,3,6,2,12,7,4,10,24,11,14,18,8,15,20,26,48,19,22,34,28,23,36,42,16,

%T 27,30,50,40,31,52,58,96,35,38,66,44,39,68,74,56,43,46,82,72,47,84,90,

%U 32,51,54,98,60,55,100,106,80,59,62,114,104,63,116,122,192,67,70,130

%N Earliest sequence with a(a(n)) = 2n.

%H T. D. Noe, <a href="/A002516/b002516.txt">Table of n, a(n) for n = 0..1000</a>

%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>

%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>

%H <a href="/index/Aa#aan">Index entries for sequences of the a(a(n)) = 2n family</a>

%F a(4n) = 2*(a(2n)), a(4n+1) = 4n+3, a(4n+2) = 2*(a(2n+1)), a(4n+3) = 8n+2. - _Henry Bottomley_, Apr 27 2000

%F From _Ralf Stephan_, Feb 22 2004: (Start)

%F a(n) = n + 2*A006519(n) if odd part of n is of form 4k+1, or 2n - 4*A006519(n) otherwise.

%F a(2n) = 2*a(n), a(2n+1) = 2n + 3 + (2n - 5)*[n mod 2].

%F G.f.: Sum_{k>=0} 2^k*t(6t^6 + t^4 + 2t^2 + 3)/(1 - t^4)^2, t = x^2^k. (End)

%t a[0] = 0; a[n_ /; Mod[n, 2] == 0] := a[n] = 2*a[n/2]; a[n_ /; Mod[n, 4] == 1] := n+2; a[n_ /; Mod[n, 4] == 3] := 2(n-2); Table[a[n], {n, 0, 67}] (* _Jean-François Alcover_, Feb 06 2012, after _Henry Bottomley_ *)

%o (PARI) v2(n)=valuation(n,2)

%o a(n)=2^v2(n)*(-1+3/2*n/2^v2(n)-(-3+1/2*n/2^v2(n))*(-1)^((n/2^v2(n)-1)/2))

%o (PARI) a(n)=local(t); if(n<1,0,if(n%2==0,2*a(n/2),t=(n-1)/2; 3*t+1/2-(t-5/2)*(-1)^t)) \\ _Ralf Stephan_, Feb 22 2004

%o (Haskell)

%o import Data.List (transpose)

%o a002516 n = a002516_list !! n

%o a002516_list = 0 : concat (transpose

%o [a004767_list, f a002516_list, a017089_list, g $ drop 2 a002516_list])

%o where f [z] = []; f (_:z:zs) = 2 * z : f zs

%o g [z] = [z]; g (z:_:zs) = 2 * z : g zs

%o -- _Reinhard Zumkeller_, Jun 08 2015

%Y Cf. A002517, A004767, A007379, A017089, A091067.

%K nonn,nice

%O 0,2

%A _Colin Mallows_