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

%I #39 Mar 26 2022 17:46:51

%S 1,0,0,0,0,0,1,2,0,1,2,0,2,8,8,2,8,8,36,24,48,36,24,48,264,192,192,

%T 264,192,192,1296,1440,1152,1296,1440,1152,7200,8064,8064,7200,8064,

%U 8064,46656,44928,48384,46656,44928,48384,286848,276480,276480,286848,276480,276480

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

%C Let v(n) = [T(n,0), T(n,1), T(n,2), T(n,3), T(n,4), T(n,5)]' for n >= 0, where ' denotes transpose, and M = [[1, 0, 2, 1, 0, 2], [2, 1, 0, 2, 1, 0], [0, 2, 1, 0, 2, 1], [1, 0, 2, 1, 0, 2], [2, 1, 0, 2, 1, 0], [0, 2, 1, 0, 2, 1]]. We claim that v(n+1) = M*v(n) for n >= 0.

%C To see why this is the case, let j in 0..5, and consider the expressions 0^2 + j, 1^2 + j, 2^2 + j, 3^2 + j, 4^2 + j, and 5^2 + j modulo 6. It can be easily proved that these six numbers contain M[0,j] 0's, M[1,j] 1's, M[2,j] 2's, M[3,j] 3's, M[4,j] 4's, and M[5,j] 5'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.)

%C It follows that v(n) = M^n * v(0), where v(0) = [1,0,0,0,0,0]'.

%C The minimal polynomial for M is z*(z - 6)*(z^2 + 12) = z^4 - 6*z^3 + 12*z^2 - 72*z. Thus, M^4 - 6*M^3 + 12*M^2 - 72*M = 0, and so M^n*v(0) - 6*M^(n-1)*v(0) + 12*M^(n-2)*v(0) - 72*M^(n-3)*v(0) = 0 for n >= 4. This implies v(n) - 6*v(n-1) + 12*v(n-2) - 72*v(n-3) = 0 for n >= 4. Hence each sequence (T(n,k): n >= 0) satisfies the same recurrence b(n) - 6*b(n-1) + 12*b(n-2) - 72*b(n-3) = 0 for n >= 4.

%C Clearly, for each k in 0..5, we may find constants c_k, d_k, e_k such that T(n,k) = c_k*(2*sqrt(3)*i)^n + d_k*(-2*sqrt(3)*i)^n + e_k*6^n for n >= 0, where i = sqrt(-1). We omit the details.

%H Colin Barker, <a href="/A330635/b330635.txt">Table of n, a(n) for n = 0..1000</a>

%H <a href="/index/Rec#order_18">Index entries for linear recurrences with constant coefficients</a>, signature (0,0,0,0,0,6,0,0,0,0,0,-12,0,0,0,0,0,72).

%F T(n,k) = T(n, k+3) for k = 0,1,2 and n >= 0.

%F T(n,k) = 6*T(n-1,k) - 12*T(n-2,k) + 72*T(n-3,k) for n >= 4 and each k in 0..5. (This is not true for k = 0 or 3 when n = 3 because of the presence of z in the minimal polynomial for M.)

%F Sum_{k=0..5} T(n,k) = 6^n.

%F T(n,k) = -12*T(n-2,k) + 8*6^(n-2) for n >= 3 and k = 0..5.

%F T(n,k) ~ 6^(n-1) for each k in 0..5.

%F From _Colin Barker_, Jan 12 2020: (Start)

%F If we consider this array as a single sequence (a(n): n >= 0), then:

%F a(n) = 6*a(n-6) - 12*a(n-12) + 72*a(n-18) for n > 21.

%F G.f.: (1 - 5*x^6 + 2*x^7 + x^9 + 2*x^10 + 8*x^12 - 4*x^13 + 8*x^14 - 4*x^15 - 4*x^16 + 8*x^17 - 36*x^18 + 36*x^21) / ((1 - 6*x^6)*(1 + 12*x^12)).

%F (End)

%e Array T(n,k) (with rows n >= 0 and columns 0 <= k <= 5) begins as follows:

%e 1, 0, 0, 0, 0, 0;

%e 1, 2, 0, 1, 2, 0;

%e 2, 8, 8, 2, 8, 8;

%e 36, 24, 48, 36, 24, 48;

%e 264, 192, 192, 264, 192, 192;

%e 1296, 1440, 1152, 1296, 1440, 1152;

%e 7200, 8064, 8064, 7200, 8064, 8064;

%e ...

%e T(n=2,k=0) = 2 because we have the following solutions (x_1, x_2) to the equation x_1^2 + x_2^2 == 0 (mod 6) (with x_1, x_2 in 0..5): (0,0) and (3,3).

%e 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 6) (with x_1, x_2 in 0..5): (0,1), (0,5), (1,0), (2,3), (3,2), (3,4), (4,3), and (5,0).

%e T(n=2,k=2) = 8 because we have the following solutions (x_1, x_2) to the equation x_1^2 + x_2^2 == 2 (mod 6) (with x_1, x_2 in 0..5): (1,1), (1,5), (2,2), (2,4), (4,2), (4,4), (5,1), and (5,5).

%e T(n=2,k=3) = 2 because we have the following solutions (x_1, x_2) to the equation x_1^2 + x_2^2 == 3 (mod 6) (with x_1, x_2 in 0..5): (0,3) and (3,0).

%e T(n=2,k=4) = 8 because we have the following solutions (x_1, x_2) to the equation x_1^2 + x_2^2 == 4 (mod 6) (with x_1, x_2 in 0..5): (0,2), (0,4), (1,3), (2,0), (3,1), (3,5), (4,0), and (5,3).

%e T(n=2,k=5) = 8 because we have the following solutions (x_1, x_2) to the equation x_1^2 + x_2^2 == 5 (mod 6) (with x_1, x_2 in 0..5): (1,2), (1,4), (2,1), (2,5), (4,1), (4,5), (5,2), and (5,4).

%p with(LinearAlgebra);

%p v := proc(n) local M, v0;

%p M := Matrix([[1,0,2,1,0,2],[2,1,0,2,1,0],[0,2,1,0,2,1],[1,0,2,1,0,2],[2,1,0,2,1,0],[0,2,1,0,2,1]]);

%p v0 := Matrix([[1], [0], [0], [0], [0], [0]]);

%p if n = 0 then v0; else MatrixMatrixMultiply(MatrixPower(M, n), v0); end if;

%p end proc;

%p seq(seq(v(n)[k, 1], k = 1..6), n = 0..10);

%o (PARI) Vec((1 - 5*x^6 + 2*x^7 + x^9 + 2*x^10 + 8*x^12 - 4*x^13 + 8*x^14 - 4*x^15 - 4*x^16 + 8*x^17 - 36*x^18 + 36*x^21) / ((1 - 6*x^6)*(1 + 12*x^12)) + O(x^60)) \\ _Colin Barker_, Jan 17 2020

%Y Cf. A101990, A228920, A228921, A229136, A229138, A318609, A318610, A330607, A330619.

%K nonn,tabf

%O 0,8

%A _Petros Hadjicostas_, Dec 21 2019