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
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([n/2]) + 2a(ceil(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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 29 05:29 EDT 2017. Contains 288859 sequences.