A064194 a(2n) = 3*a(n), a(2n+1) = 2*a(n+1)+a(n), with a(1) = 1.

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

Offset: 1

Author

Guillaume Hanrot and Paul Zimmermann, Sep 21 2001

Keywords

• easy
• nonn

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

a(n) is also the number of odd elements in the n X n symmetric Pascal matrix. - Stefano Spezia, Nov 14 2022

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.
• Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, pp. 27-28.

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.

Programs

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

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

Mathematica

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 *)

PARI

a(n) = sum(i=0, n-1, sum(j=0, n-1, binomial(i+j, i) % 2)); \\ Michel Marcus, Aug 25 2013

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

Extensions

Edited with clearer definition by N. J. A. Sloane, Jan 18 2016