%I A064194
%S A064194 1,3,7,9,17,21,25,27,43,51,59,63,71,75,79,81,113,129,145,153,169,177,
%T A064194 185,189,205,213,221,225,233,237,241,243,307,339,371,387,419,435,451,
%U A064194 459,491,507,523,531,547,555,563,567,599,615,631,639,655,663,671,675
%N A064194 Number of ring multiplications needed to multiply two degree-n polynomials 
               using Karatsuba's algorithm.
%C A064194 Number of gates in the AND/OR problem (see Chang/Tsai ref).
%D A064194 K.-N. Chang and S.-C. Tsai, Exact solution of a minimal recurrence, Inform. 
               Process. Lett. 75(2000), 61-64.
%D A064194 A. A. Karatsuba and Y.P. Ofman, Multiplication of multiplace numbers 
               by automata. Dokl. Akad. Nauk SSSR 145, 2, 293-294 (1962).
%H A064194 P. J. Grabner and H.-K. Hwang, <a href="http://algo.stat.sinica.edu.tw/
               ">Digital sums and divide-and-conquer recurrences: Fourier expansions 
               and absolute convergence</a>
%F A064194 a(2n) = 3*a(n); a(2n+1)=2*a(n+1)+a(n)
%F A064194 Partial sums of sequence { a(1)=1, a(n)=2^(e0(n-1)+1) }, where e0(n)=A023416(n) 
               the zeros-counting function. - Ralf Stephan (ralf(AT)ark.in-berlin.de), 
               Jul 29 2003
%F A064194 a(1) = 1, a(n) = a([n/2]) + 2a(ceil(n/2)), n>1.
%F A064194 a(n+1)=sum_{0<=i, j<=n} {binomial(i+j, i) mod 2} - Benoit Cloitre (benoit7848c(AT)orange.fr), 
               Mar 07 2005
%Y A064194 Sequence in context: A118258 A117583 A126106 this_sequence A036978 A079464 
               A036976
%Y A064194 Adjacent sequences: A064191 A064192 A064193 this_sequence A064195 A064196 
               A064197
%K A064194 easy,nonn
%O A064194 1,2
%A A064194 Guillaume Hanrot and Paul Zimmermann (hanrot(AT)loria.fr), Sep 21 2001