A330635 -id:A330635 - cp's OEIS frontend

A318609 a(1) = 2, a(2) = 4, a(3) = 6; for n > 3, a(n) = 3a(n-1) - 3a(n-2) + 9*a(n-3).

2, 4, 6, 24, 90, 252, 702, 2160, 6642, 19764, 58806, 176904, 532170, 1595052, 4780782, 14346720, 43053282, 129146724, 387400806, 1162241784, 3486843450, 10460412252, 31380882462, 94143001680, 282430067922, 847289140884, 2541864234006, 7625595890664, 22876797237930

Offset: 1

Jianing Song, Sep 02 2018

a(n) is the number of solutions to Sum_{i=1..n} x_i^2 == 1 (mod 3).

			a(5) = 90 since M^5 * [1, 0, 0]^T = [81, 90, 72]^T.

Jianing Song, Table of n, a(n) for n = 1..500
Index entries for linear recurrences with constant coefficients, signature (3,-3,9).

A101990 gives the number of solutions to Sum_{i=1..n} x_i^2 == 0 (mod 3);
A318610 gives the number of solutions to Sum_{i=1..n} x_i^2 == 2 (mod 3).
Cf. A228921, A228920, A229138, A330607, A330619, A330635.

I:=[2,4,6]; [n le 3 select I[n] else 3*Self(n-1)-3*Self(n-2)+9*Self(n-3): n in [1..30]]; // Jianing Song, Sep 05 2018

LinearRecurrence[{3, -3, 9}, {2, 4, 6}, 30] (* Jianing Song, Sep 05 2018 *)

Vec(2*x*(1-x)/((1-3*x)*(1+3*x^2)) + O(x^40))

a(n) = ([1, 0, 2 ; 2, 1, 0 ; 0, 2, 1]^n*mattranspose([1, 0, 0]))[2]; \\ Michel Marcus, Dec 20 2019

a(n) = middle term in M^n * [1, 0, 0]^T, where M = the 3 X 3 matrix [1, 0, 2 / 2, 1, 0 / 0, 2, 1] and T denotes transpose. [Edited by Petros Hadjicostas, Dec 19 2019]
O.g.f.: 2*x*(1 - x)/((1 - 3*x)*(1 + 3*x^2)).
E.g.f.: 1/3*(exp(3*x) + 2*cos(sqrt(3)*x - 2*Pi/3)).
a(n) = 3^(n/2 - 1)*((-i)^n*(-1 + sqrt(3)*i)/2 + i^n*(-1 - sqrt(3)*i)/2 + 3^(n/2)), where i is the imaginary unit.
a(n) = 3^(n/2 - 1)*(2*cos(n*Pi/2 - 2*Pi/3) + 3^(n/2)).
a(n) = 3^(n-1) + (-3)^(n/2-1) for even n and 3^(n-1) + (-3)^((n-1)/2) for odd n.
a(n) = a(n-1) + 2*A101990(n-1).
a(n) = A318610(n) for even n and 2*3^(n-1) - A318610(n) for odd n.
a(n) + A101990(n) + A318610(n) = 3^n.

A318610 a(1) = 0, a(2) = 4, a(3) = 12; for n > 3, a(n) = 3a(n-1) - 3a(n-2) + 9*a(n-3).

Original entry on oeis.org

0, 4, 12, 24, 72, 252, 756, 2160, 6480, 19764, 59292, 176904, 530712, 1595052, 4785156, 14346720, 43040160, 129146724, 387440172, 1162241784, 3486725352, 10460412252, 31381236756, 94143001680, 282429005040, 847289140884, 2541867422652, 7625595890664, 22876787671992

Offset: 1

Jianing Song, Sep 02 2018

a(n) is the number of solutions to Sum_{i=1..n} x_i^2 == 2 (mod 3).

			a(5) = 72 since M^5 * [1, 0, 0]^T = [81, 90, 72]^T.

Jianing Song, Table of n, a(n) for n = 1..500
Index entries for linear recurrences with constant coefficients, signature (3,-3,9).

A101990 gives the number of solutions to Sum_{i=1..n} x_i^2 == 0 (mod 3);
A318609 gives the number of solutions to Sum_{i=1..n} x_i^2 == 1 (mod 3).
Cf. A228921, A228920, A229138, A330607, A330619, A330635.

I:=[0,4,12]; [n le 3 select I[n] else 3*Self(n-1)-3*Self(n-2)+9*Self(n-3): n in [1..30]]; // Vincenzo Librandi, Sep 04 2018

LinearRecurrence[{3, -3, 9}, {0, 4, 12}, 30] (* Vincenzo Librandi, Sep 04 2018 *)

concat([0], Vec(4*x^2/((1-3*x)*(1+3*x^2)) + O(x^40)))

a(n) = ([1, 0, 2 ; 2, 1, 0 ; 0, 2, 1]^n*mattranspose([1, 0, 0]))[3]; \\ Michel Marcus, Dec 20 2019

a(n) = last term in M^n * [1, 0, 0]^T, where M = the 3 X 3 matrix [1, 0, 2 /  2, 1, 0 /  0, 2, 1] and T denotes transpose. [Edited by Petros Hadjicostas, Dec 19 2019]
O.g.f.: 4*x^2/((1 - 3x)*(1 + 3*x^2)).
E.g.f.: 1/3*(exp(3*x) + 2*cos(sqrt(3)*x + 2*Pi/3)).
a(n) = 3^(n/2 - 1)*((-i)^n*(-1 - sqrt(3)*i)/2 + i^n*(-1 + sqrt(3)*i)/2 + 3^(n/2)), where i is the imaginary unit.
a(n) = 3^(n/2 - 1)*(2*cos(n*Pi/2 + 2*Pi/3) + 3^(n/2)).
a(n) = 3^(n-1) + (-3)^(n/2-1) for even n and 3^(n-1) - (-3)^((n-1)/2) for odd n.
a(n) = a(n-1) + 2*A318609(n-1).
a(n) = A318609(n) for even n and 2*3^(n-1) - A318609(n) for odd n.
a(n) + A101990(n) + A318609(n) = 3^n.

A330619 Array read by rows: T(n,k) is the number of solutions to the equation Sum_{i=1..n} x_i^2 == k (mod 4) with x_i in 0..3, where n >= 0 and 0 <= k <= 3.

Original entry on oeis.org

1, 0, 0, 0, 2, 2, 0, 0, 4, 8, 4, 0, 8, 24, 24, 8, 32, 64, 96, 64, 192, 192, 320, 320, 1024, 768, 1024, 1280, 4608, 3584, 3584, 4608, 18432, 16384, 14336, 16384, 69632, 69632, 61440, 61440, 262144, 278528, 262144, 245760, 1015808, 1081344, 1081344, 1015808, 4063232, 4194304, 4325376, 4194304

Offset: 0

Petros Hadjicostas, Dec 20 2019

Let v(n) = [T(n,0), T(n,1), T(n,2), T(n,3)]' for n >= 0, where ' denotes transpose, and M = [[2,0,0,2], [2,2,0,0], [0,2,2,0], [0,0,2,2]]. We claim that v(n+1) = M*v(n) for n >= 0.
To see why this is the case, let j in 0..3, and consider the expressions 0^2 + j, 1^2 + j, 2^2 + j, and 3^2 + j modulo 4. It can be easily proved that these four numbers contain M[0,j] 0's, M[1,j] 1's, M[2,j] 2's, and M[3,j] 3's. (This is how the transfer matrix M was constructed. The idea is similar to Jianing Song's ideas for sequences A101990, A318609, and A318610.)
It follows that v(n) = M^n * v(0), where v(0) = [1,0,0,0]'.
The minimal polynomial for M is z*(z - 4)*(z^2 - 4*z + 8) = z^4 - 8*z^3 + 24*z^2 - 32*z. Thus, M^4 - 8*M^3 + 24*M^2 - 32*M = 0, and so M^n*v(0) - 8*M^(n-1)*v(0) + 24*M^(n-2)*v(0) - 32*M^(n-3)*v(0) = 0 for n >= 4. This implies v(n) - 8*v(n-1) +  24*v(n-2) - 32*v(n-3) = 0 for n >= 4. Hence each sequence (T(n,k): n >= 0) satisfies the same recurrence b(n) - 8*b(n-1) + 24*b(n-2) - 32*b(n-3) = 0 for n >= 4. (For all k in 0..3, the recurrence is not satisfied for n = 3.)
Clearly, for each k in 0..3, we may find constants c_k, d_k, e_k such that T(n,k) = c_k*(2 + 2*i)^n + d_k*(2 - 2*i)^n + e_k*4^n for n >= 0 (where i = sqrt(-1)). We omit the details.

			Array T(n,k) (with rows n >= 0 and columns 0 <= k <= 3) begins as follows:
     1,    0,    0,    0;
     2,    2,    0,    0;
     4,    8,    4,    0;
     8,   24,   24,    8;
    32,   64,   96,   64;
   192,  192,  320,  320;
  1024,  768, 1024, 1280;
  4608, 3584, 3584, 4608;
  ...
T(n=2,k=0) = 4 because we have the following solutions (x_1, x_2) to the equation x_1^2 + x_2^2 == 0 (mod 4) (with x_1, x_2 in 0..3): (0,0), (0,2), (2,0), and (2,2).
T(n=2,k=1) = 8 because we have the following solutions (x_1, x_2) to the equation x_1^2 + x_2^2 == 1 (mod 4) (with x_1, x_2 in 0..3): (0,1), (0,3), (1,0), (1,2), (2,1), (2,3), (3,0), and (3,2).
T(n=2,k=2) = 4 because we have the following solutions (x_1, x_2) to the equation x_1^2 + x_2^2 == 2 (mod 4) (with x_1, x_2 in 0..3): (1,1), (1,3), (3,1), and (3,3).
T(n=2,k=3) = 0 because we have no solutions (x_1, x_2) to the equation x_1^2 + x_2^2 == 3 (mod 4) (with x_1, x_2 in 0..3).

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (0,0,0,8,0,0,0,-24,0,0,0,32).

Columns include A228920 (k = 0), A229136 (k = 1).

Cf. A101990, A228921, A229138, A318609, A318610, A330607, A330635.

with(LinearAlgebra);
v := proc(n) local M, v0;
  M := Matrix([[2, 0, 0, 2], [2, 2, 0, 0], [0, 2, 2, 0], [0, 0, 2, 2]]);
  v0 := Matrix([[1], [0], [0], [0]]); if n = 0 then v0; else  MatrixMatrixMultiply(MatrixPower(M, n), v0); end if;
end proc;
seq(seq(v(n)[k, 1], k = 1 .. 4), n = 0 .. 10);

a(n) = ([2,0,0,2; 2,2,0,0; 0,2,2,0; 0,0,2,2]^n*mattranspose([1, 0, 0, 0]));
for(n=0, 30, print1(a(n), ", "));  /* after Michel Marcus's program for A101990 */

Vec((1 - 2*x^4 + 2*x^5)*(1 - 4*x^4 + 4*x^8 + 4*x^10) / ((1 - 2*x^2)*(1 + 2*x^2)*(1 - 4*x^4 + 8*x^8)) + O(x^50)) \\ Colin Barker, Dec 21 2019

T(n,k) = 8*T(n-1,k) - 24*T(n-2,k) + 32*T(n-3,k) for n >= 4 with initial conditions for T(1,k), T(2,k), and T(3,k) (for each value of k in 0..3) given in the example below. (The recurrence is not true for n = 3.)
T(n,k) = 4*T(n-1,k) - 8*T(n-2,k) + 2^(2*n-3) for n >= 3.
T(n,k) ~ 4^(n-1) for each k in 0..3.
Sum_{k = 0..3} T(n,k) = 4^n.
v(n+1) = M*v(n) and v(n) = M^n * [1,0,0,0]' for n >= 0, where M = [[2,0,0,2], [2,2,0,0], [0,2,2,0], [0,0,2,2]] and v(n) = [T(n,0), T(n,1), T(n,2), T(n,3)]'.
From Colin Barker, Dec 21 2019: (Start)
If we consider this array as a single sequence (a(n): n >= 0), then:
G.f.: (1 - 2*x^4 + 2*x^5)*(1 - 4*x^4 + 4*x^8 + 4*x^10) / ((1 - 2*x^2)*(1 + 2*x^2)*(1 - 4*x^4 + 8*x^8)).
a(n) = 8*a(n-4) - 24*a(n-8) + 32*a(n-12) for n > 15. (End)

cp's OEIS Frontend

A318609 a(1) = 2, a(2) = 4, a(3) = 6; for n > 3, a(n) = 3*a(n-1) - 3*a(n-2) + 9*a(n-3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula

A318610 a(1) = 0, a(2) = 4, a(3) = 12; for n > 3, a(n) = 3*a(n-1) - 3*a(n-2) + 9*a(n-3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula

A330619 Array read by rows: T(n,k) is the number of solutions to the equation Sum_{i=1..n} x_i^2 == k (mod 4) with x_i in 0..3, where n >= 0 and 0 <= k <= 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

PARI

Formula

A318609 a(1) = 2, a(2) = 4, a(3) = 6; for n > 3, a(n) = 3a(n-1) - 3a(n-2) + 9*a(n-3).

A318610 a(1) = 0, a(2) = 4, a(3) = 12; for n > 3, a(n) = 3a(n-1) - 3a(n-2) + 9*a(n-3).