A181358 Number of twiddle factors in the first stage of a Pease Radix 4 Fast Fourier Transform.

8, 44, 188, 764, 3068, 12284, 49148, 196604, 786428, 3145724, 12582908, 50331644, 201326588, 805306364, 3221225468, 12884901884, 51539607548, 206158430204, 824633720828, 3298534883324, 13194139533308, 52776558133244, 211106232532988, 844424930131964

Offset: 0

Author

Robert Koutsoyannis (bob.koutsoyannis(AT)gmail.com), Oct 14 2010

Keywords

• nonn
• easy

Comments

Number of twiddle factors in the first stage of a Pease Radix 4 Fast Fourier Transform.

Links

• Colin Barker, Table of n, a(n) for n = 0..1000
• Wikipedia, Twiddle factor
• Index entries for linear recurrences with constant coefficients, signature (5,-4).

Programs

PARI

Vec(4*(2+x) / ((1-x) * (1-4*x)) + O(x^30)) \\ Colin Barker, Nov 26 2016

Formula

a(n) = 4*(3*4^n - 1).

From Colin Barker, Nov 26 2016: (Start)

a(n) = 4*A198693(n).

a(n) = 5*a(n-1) - 4*a(n-2) for n>1.

G.f.: 4*(2+x) / ((1-x) * (1-4*x)).

(End)