cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

This page as a plain text file.
%I A330607 #59 Mar 26 2022 17:46:42
%S A330607 1,0,0,0,0,1,2,0,0,2,9,4,4,4,4,25,30,20,20,30,145,120,120,120,120,625,
%T A330607 650,600,600,650,3225,3100,3100,3100,3100,15625,15750,15500,15500,
%U A330607 15750,78625,78000,78000,78000,78000,390625,391250,390000,390000,391250,1955625,1952500,1952500,1952500,1952500
%N A330607 Array read by rows: T(n,k) is the number of solutions to the equation Sum_{i=1..n} x_i^2 == k (mod 5) with x_i in 0..4, where n >= 0 and 0 <= k <= 4.
%C A330607 Let v(n) = [T(n,0), T(n,1), T(n,2), T(n,3), T(n,4)]' for n >= 0, where ' denotes transpose, and M = [[1,2,0,0,2], [2,1,2,0,0], [0,2,1,2,0], [0,0,2,1,2], [2,0,0,2,1]]. We claim that v(n+1) = M*v(n) for n >= 0.
%C A330607 To see why this is the case, let j in 0..4, and consider the expressions 0^2 + j, 1^2 + j, 2^2 + j, 3^2 + j, and 4^2 + j modulo 5. It can be easily proved that these five numbers contain M[0,j] 0's, M[1,j] 1's, M[2,j] 2's, M[3,j] 3's, and M[4,j] 4'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 A330607 It follows that v(n) = M^n * v(0), where v(0) = [1,0,0,0,0]'.
%C A330607 The minimal polynomial for M is (z - 5)*(z^2 - 5) = z^3 - 5*z^2 - 5*z + 25. Thus, M^3 - 5*M^2 - 5*M + 25*I = 0, and so M^n*v(0) - 5*M^(n-1)*v(0) - 5*M^(n-2)*v(0) + 25*M^(n-3)*v(0) = 0 for n >= 3. This implies v(n) - 5*v(n-1) - 5*v(n-2) + 25*v(n-3) = 0 for n >= 3. Hence each sequence (T(n,k): n >= 0) satisfies the same recurrence b(n) - 5*b(n-1) - 5*b(n-2) + 25*b(n-3) = 0 for n >= 3.
%C A330607 Clearly, for each k in 0..4, we may find constants c_k, d_k, e_k such that T(n,k) = c_k*sqrt(5)^n + d_k*(-sqrt(5))^n + e_k*5^n for n >= 0. We omit the details.
%H A330607 Colin Barker, <a href="/A330607/b330607.txt">Table of n, a(n) for n = 0..1000</a>
%H A330607 <a href="/index/Rec#order_15">Index entries for linear recurrences with constant coefficients</a>, signature (0,0,0,0,5,0,0,0,0,5,0,0,0,0,-25).
%F A330607 T(n,k) = 5*T(n-1,k) + 5*T(n-2,k) - 25*T(n-3,k) for n >= 3 with initial conditions for T(0,k), T(1,k), and T(2,k) (for each value of k in 0..4) given in the example below.
%F A330607 T(n,k) = 5*T(n-2,k) + 4*5^(n-2) for n >= 2.
%F A330607 T(n,k=1) = T(n,k=4) and T(n,k=2) = T(n,k=3).
%F A330607 T(n,k) ~ 5^(n-1) for each k in 0..4.
%F A330607 Sum_{k = 0..4} T(n,k) = 5^n.
%F A330607 v(n+1) = M*v(n) and v(n) = M^n * [1,0,0,0,0]' for n >= 0, where M = [[1,2,0,0,2], [2,1,2,0,0], [0,2,1,2,0], [0,0,2,1,2], [2,0,0,2,1]] and v(n) = [T(n,0), T(n,1), T(n,2), T(n,3), T(n,4)]'.
%F A330607 Conjecture: T(n,k=1) = A071304(n)/A071304(n-1) for n >= 2.
%F A330607 From _Colin Barker_, Dec 21 2019: (Start)
%F A330607 If we consider the array as a single sequence (a(n): n >= 1), then:
%F A330607 G.f.: (1 - 4*x^5 + 2*x^6 + 2*x^9 - x^10 - 6*x^11 + 4*x^12 + 4*x^13 - 6*x^14) / ((1 - 5*x^5)*(1 - 5*x^10)).
%F A330607 a(n) = 5*a(n-5) + 5*a(n-10) - 25*a(n-15) for n > 14. (End)
%e A330607 Array T(n,k) (with rows n >= 0 and columns 0 <= k <= 4) begins as follows:
%e A330607      1,    0,    0,    0,    0;
%e A330607      1,    2,    0,    0,    2;
%e A330607      9,    4,    4,    4,    4;
%e A330607     25,   30,   20,   20,   30;
%e A330607    145,  120,  120,  120,  120;
%e A330607    625,  650,  600,  600,  650;
%e A330607   3225, 3100, 3100, 3100, 3100;
%e A330607   ...
%e A330607 T(n=2,k=0) = 9 because we have the following solutions (x_1, x_2) to the equation x_1^2 + x_2^2 == 0 (mod 5) (with x_1, x_2 in 0..4): (0,0), (1,2), (1,3), (2,1), (2,4), (3,1), (3,4), (4,2), and (4,3).
%e A330607 T(n=2,k=1) = 4 because we have the following solutions (x_1, x_2) to the equation x_1^2 + x_2^2 == 1 (mod 5) (with x_1, x_2 in 0..4): (0,1), (0,4), (1,0), and (4,0).
%e A330607 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 5) (with x_1, x_2 in 0..4): (1,1), (1,4), (4,1), and (4,4).
%e A330607 T(n=2,k=3) = 4 because we have the following solutions (x_1, x_2) to the equation x_1^2 + x_2^2 == 3 (mod 5) (with x_1, x_2 in 0..4): (2,2), (2,3), (3,2), and (3,3).
%e A330607 T(n=2,k=4) = 4 because we have the following solutions (x_1, x_2) to the equation x_1^2 + x_2^2 == 4 (mod 5) (with x_1, x_2 in 0..4): (0,2), (0,3), (2,0), and (3,0).
%p A330607 with(LinearAlgebra);
%p A330607 v := proc(n) local M, v0;
%p A330607    M := Matrix([[1, 2, 0, 0, 2], [2, 1, 2, 0, 0], [0, 2, 1, 2, 0], [0, 0, 2, 1, 2], [2, 0, 0, 2, 1]]); v0 := Matrix([[1], [0], [0], [0], [0]]);
%p A330607   if n = 0 then v0; else MatrixMatrixMultiply(MatrixPower(M, n), v0); end if;
%p A330607 end proc;
%p A330607 seq(seq(v(n)[k, 1], k = 1 .. 5), n = 0 .. 10);
%o A330607 (PARI) Vec((1 - 4*x^5 + 2*x^6 + 2*x^9 - x^10 - 6*x^11 + 4*x^12 + 4*x^13 - 6*x^14) / ((1 - 5*x^5)*(1 - 5*x^10)) + O(x^50)) \\ _Colin Barker_, Dec 21 2019
%Y A330607 Cf. A071304, A101990, A228920, A228921, A229136, A229138, A318609, A318610.
%K A330607 nonn,tabf,easy
%O A330607 0,7
%A A330607 _Petros Hadjicostas_, Dec 20 2019