login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 7
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

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

LINKS

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

FORMULA

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)

EXAMPLE

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

MAPLE

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

PROG

(PARI) 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 */

(PARI) 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

CROSSREFS

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

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

Sequence in context: A325788 A240509 A344901 * A245693 A297866 A298133

Adjacent sequences:  A330616 A330617 A330618 * A330620 A330621 A330622

KEYWORD

nonn,tabf,easy

AUTHOR

Petros Hadjicostas, Dec 20 2019

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 25 16:03 EDT 2021. Contains 346291 sequences. (Running on oeis4.)