This site is supported by donations to The OEIS Foundation.

 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
 1, 3, 7, 9, 17, 21, 25, 27, 43, 51, 59, 63, 71, 75, 79, 81, 113, 129, 145, 153, 169, 177, 185, 189, 205, 213, 221, 225, 233, 237, 241, 243, 307, 339, 371, 387, 419, 435, 451, 459, 491, 507, 523, 531, 547, 555, 563, 567, 599, 615, 631, 639, 655, 663, 671, 675 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS Number of ring multiplications needed to multiply two degree-n polynomials using Karatsuba's algorithm. Number of gates in the AND/OR problem (see Chang/Tsai reference). REFERENCES A. A. Karatsuba and Y. P. Ofman, Multiplication of multiplace numbers by automata. Dokl. Akad. Nauk SSSR 145, 2, 293-294 (1962). LINKS N. J. A. Sloane, Table of n, a(n) for n = 1..10000 K.-N. Chang and S.-C. Tsai, Exact solution of a minimal recurrence, Inform. Process. Lett. 75 (2000), 61-64. P. J. Grabner and H.-K. Hwang, Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence, Constructive Approximation, Jan. 2005, Volume 21, Issue 2, pp. 149-179. FORMULA 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 a(1) = 1, a(n) = a(floor(n/2)) + 2*a(ceiling(n/2)), n > 1. a(n+1) = Sum_{0<=i, j<=n} (binomial(i+j, i) mod 2). - Benoit Cloitre, Mar 07 2005 In particular, a(2^k)=3^k, a(3*2^k)=7*3^k. - N. J. A. Sloane, Jan 18 2016 a(n) = 2*A268514(n-1) + 1. - N. J. A. Sloane, Feb 07 2016 MAPLE 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 PROG (PARI) a(n) = sum(i=0, n-1, sum(j=0, n-1, binomial(i+j, i) % 2)); \\ Michel Marcus, Aug 25 2013 (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 CROSSREFS Cf. A023416, A267584, A047999 (Sierpinski triangle). Cf. also A268514. 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. Sequence in context: A118258 A117583 A126106 * A036978 A079464 A036976 Adjacent sequences:  A064191 A064192 A064193 * A064195 A064196 A064197 KEYWORD easy,nonn AUTHOR Guillaume Hanrot and Paul Zimmermann, Sep 21 2001 EXTENSIONS Edited with clearer definition by N. J. A. Sloane, Jan 18 2016 STATUS approved

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.

Last modified October 20 07:33 EDT 2019. Contains 328252 sequences. (Running on oeis4.)