%I #63 Nov 14 2022 23:04:15
%S 1,3,7,9,17,21,25,27,43,51,59,63,71,75,79,81,113,129,145,153,169,177,
%T 185,189,205,213,221,225,233,237,241,243,307,339,371,387,419,435,451,
%U 459,491,507,523,531,547,555,563,567,599,615,631,639,655,663,671,675
%N a(2n) = 3*a(n), a(2n+1) = 2*a(n+1)+a(n), with a(1) = 1.
%C Number of ring multiplications needed to multiply two degree-n polynomials using Karatsuba's algorithm.
%C Number of gates in the AND/OR problem (see Chang/Tsai reference).
%C a(n) is also the number of odd elements in the n X n symmetric Pascal matrix. - _Stefano Spezia_, Nov 14 2022
%D A. A. Karatsuba and Y. P. Ofman, Multiplication of multiplace numbers by automata. Dokl. Akad. Nauk SSSR 145, 2, 293-294 (1962).
%H N. J. A. Sloane, <a href="/A064194/b064194.txt">Table of n, a(n) for n = 1..10000</a>
%H K.-N. Chang and S.-C. Tsai, <a href="http://dx.doi.org/10.1016/S0020-0190(00)00076-4">Exact solution of a minimal recurrence</a>, Inform. Process. Lett. 75 (2000), 61-64.
%H P. J. Grabner and H.-K. Hwang, <a href="http://algo.stat.sinica.edu.tw/hk/files/2005_07/pdf/Digital_sums_and_divide-and-conquer_recurrences.pdf">Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence</a>, Constructive Approximation, Jan. 2005, Volume 21, Issue 2, pp. 149-179.
%H Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="https://arxiv.org/abs/2210.10968">Identities and periodic oscillations of divide-and-conquer recurrences splitting at half</a>, arXiv:2210.10968 [cs.DS], 2022, pp. 27-28.
%F Partial sums of the sequence { b(1)=1, b(n)=2^(e0(n-1)+1) } (essentially A267584), where e0(n)=A023416(n) is the number of zeros in the binary expansion of n. [Chang/Tsai] - _Ralf Stephan_, Jul 29 2003
%F a(1) = 1, a(n) = a(floor(n/2)) + 2*a(ceiling(n/2)), n > 1.
%F a(n+1) = Sum_{0<=i, j<=n} (binomial(i+j, i) mod 2). - _Benoit Cloitre_, Mar 07 2005
%F In particular, a(2^k)=3^k, a(3*2^k)=7*3^k. - _N. J. A. Sloane_, Jan 18 2016
%F a(n) = 2*A268514(n-1) + 1. - _N. J. A. Sloane_, Feb 07 2016
%p f:=proc(n) option remember; if n=1 then 1 elif n mod 2 = 0 then 3*f(n/2) else 2*f((n+1)/2)+f((n-1)/2); fi; end; [seq(f(n),n=1..60)]; # _N. J. A. Sloane_, Jan 17 2016
%t a[n_] := a[n] = If[EvenQ[n], 3 a[n/2], 2 a[# + 1] + a[#] &[(n - 1)/2]]; a[1] = 1; Array[a, 56] (* _Michael De Vlieger_, Oct 29 2022 *)
%o (PARI) a(n) = sum(i=0, n-1, sum(j=0, n-1, binomial(i+j, i) % 2)); \\ _Michel Marcus_, Aug 25 2013
%o (Magma) [n le 1 select 1 else Self(Floor(n/2)) + 2*Self(Ceiling(n/2)): n in [1..60]]; // _Vincenzo Librandi_, Aug 30 2016
%Y Cf. A023416, A267584, A047999 (Sierpinski triangle).
%Y Cf. also A268514.
%Y Sequences of form a(n)=r*a(ceil(n/2))+s*a(floor(n/2)), a(1)=1, for (r,s) = (1,1), (1,2), (2,1), (1,3), (2,2), (3,1), (1,4), (2,3), (3,2), (4,1): A000027, A006046, A064194, A130665, A073121, A268524, A116520, A268525, A268526, A268527.
%K easy,nonn
%O 1,2
%A Guillaume Hanrot and _Paul Zimmermann_, Sep 21 2001
%E Edited with clearer definition by _N. J. A. Sloane_, Jan 18 2016