login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A064194 a(2n) = 3*a(n), a(2n+1) = 2*a(n+1)+a(n), with a(1) = 1. 13

%I

%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).

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

%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

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 20 14:52 EST 2019. Contains 320327 sequences. (Running on oeis4.)