login
Array T(n,k) = n*T(n,k-1) - T(n,k-2) read by upward antidiagonals, with T(n,0) = 0, T(n,1) = 1, n >= 2.
9

%I #120 Jul 07 2019 02:21:20

%S 0,0,1,0,1,2,0,1,3,3,0,1,4,8,4,0,1,5,15,21,5,0,1,6,24,56,55,6,0,1,7,

%T 35,115,209,144,7,0,1,8,48,204,551,780,377,8,0,1,9,63,329,1189,2640,

%U 2911,987,9,0,1,10,80,496,2255,6930,12649,10864,2584,10

%N Array T(n,k) = n*T(n,k-1) - T(n,k-2) read by upward antidiagonals, with T(n,0) = 0, T(n,1) = 1, n >= 2.

%C Define {x(k)} to be an integer sequence satisfying all the following conditions:

%C (i) {x(k)} satisfies second-order linear recursion, that is, there exists two integers P, Q such that x(k+2) = P*x(k+1) + Q*x(k) holds for all k >= 0.

%C (ii) {x(k)} is (not necessarily strictly) increasing. ({A000035(k)} satisfies condition (i), but it doesn't satisfy this.)

%C (iii) All terms in {x(k)} do not share a common factor. ({A024023(k)} satisfies both conditions (i) and (ii), but all terms share a common factor 2.)

%C (iv) {x(k)} satisfies strong divisibility, that is, gcd(x(m),x(n)) = x(gcd(m,n)) holds for all m, n >= 0. ({A093131(k)} satisfies all conditions (i) to (iii), but 5 = gcd(A093131(2),A093131(3)) != A093131(gcd(2,3)) = 1.)

%C (v) For all positive integers n, there eventually exists some m > 0 such that n divides x(m). ({A002275(k)} satisfies all conditions (i) to (iv), but 2, 5 and 10 never divide any term.)

%C Then it's easy to show that the only solutions to {x(k)} are x(k) = A172236(n,k) or x(k) = T(n,k), i.e., x(0) = 0, x(1) = 1, P >= 1, Q = 1 or P >= 2, Q = -1.

%C The case n = 0 is not included since it gives the period-4 signed sequence 0, 1, 0, -1, 0, 1, 0, -1, ..., the g.f. of which is the inverse of the 4th cyclotomic polynomial.

%C The case n = 1 is not included since it gives the period-6 signed sequence 0, 1, 1, 0, -1, -1, ..., the g.f. of which is the inverse of the 6th cyclotomic polynomial.

%C The congruence property: let p be an odd prime which is not divisible by n^2 - 4, then T(n,(p-1)/2) == 1/2(((n-2)/p) - ((n+2)/p)) (mod p), T(n,(p+1)/2) == 1/2(((n-2)/p) + ((n+2)/p)) (mod p). Here ((n-2)/p) is the Legendre symbol. Or equivalently:

%C ((n-2)/p)...((n+2)/p)...T(n,(p-1)/2) mod p...T(n,(p+1)/2) mod p

%C .....1...........1...............0....................1

%C ....-1..........-1...............0...................-1

%C .....1..........-1...............1....................0

%C ....-1...........1..............-1....................0

%C To prove this, rewrite (n +- sqrt(n^2-4))/2 as ((sqrt(n+2) +- sqrt(n-2))/2)^2.

%C Let E(n,m) be the smallest number l such that m divides T(n,l), we have: E(n,p) divides (p - ((n^2-4)/p))/2 for odd primes p that are not divisible by n^2 - 4. E(n,p) = p for odd primes p that are divisible by n^2 - 4. E(n,2) = 2 for even n and 3 for odd n.

%C E(n,p^e) <= p^(e-1)*E(n,p) for all primes p. If p^2 does not divide T(n,E(n,p)), then E(n,p^e) = p^(e-1)*E(n,p) for all exponent e. Specially, for primes p >= 5 that are divisible by n^2 - 4, p^2 is never divisible by T(n,p), so E(n,p^e) = p^e as described above. E(n,m_1*m_2) = lcm(E(n,m_1),E(n,m_2)) if gcd(m_1,m_2) = 1.

%C Given n, the largest possible value of E(n,m)/m is 1 for even n and 3/2 for odd n. It can be obtained by the value of E(n,2) described above.

%C Let pi(n,m) be the Pisano period of T(n,k) modulo m, i.e, the smallest number l such that T(n,k+1) == T(n,k) (mod m) holds for all k >= 0, we have: for odd primes p that are not divisible by n^2 - 4, pi(n,p) divides p + ((n-2)/p) if ((n+2)/p) = -1 and (p - ((n-2)/p))/2 if ((n+2)/p) = 1. pi(n,p) = p for odd primes p that are divisible by n - 2 and 2p for odd primes p that are divisible by n + 2. pi(n,2) = 2 even n and 3 for odd n.

%C pi(n,p^e) <= p^(e-1)*pi(n,p) for all primes p. If p^2 does not divide T(n,E(n,p)), then pi(n,p^e) = p^(e-1)*pi(n,p) for all exponent e. Specially, for primes p >= 5 that are divisible by n^2 - 4, p^2 is never divisible by T(n,p), so pi(n,p^e) = p^e or 2p^e as described above. pi(n,m_1*m_2) = lcm(pi(n,m_1),pi(n,m_2)) if gcd(m_1,m_2) = 1.

%C Given n, the largest possible value of pi(n,m)/m is:

%C Parity of n...n + 2 is a power of 2 or 3...max{pi(n,m)/m}.....obtained by

%C ....even..........yes (even exponent)............1...........pi(n,2^e) = 2^e

%C ....even...........yes (odd exponent)...........4/3............pi(n,3) = 4

%C ....even...................no....................2.............pi(n,p) = 2p (p >= 3 is any prime factor of n + 2)

%C .....odd..................yes....................2..........pi(n,3^e) = 2*3^e

%C .....odd...................no....................3..........pi(n,2p^e) = 6p^e (p >= 5 is any prime factor of n + 2)

%C The largest possible value of pi(n,m)/m is obtained by infinitely many m except for the case n = 10, in which we have pi(10,3) = 6, pi(10,7) = 8, pi(10,21) = 24 and pi(10,m)/m <= 14/13 for all other m. [Corrected by _Jianing Song_, Nov 04 2018]

%C Let z(n,m) be the number of zeros in a period of T(n,k) modulo m, i.e., z(n,m) = pi(n,m)/E(n,m), then we have: for odd primes p that are not divisible by n^2 - 4, z(n,p) = 2 if ((n+2)/p) = -1; 1 or 2 if ((n+2)/p) = 1. z(n,p) = 1 for odd primes p that are divisible by n - 2 and 2 for odd primes p that are divisible by n + 2. z(n,2) = 1.

%C For all odd primes p, z(n,p) = 2 if and only if pi(n,p) is even, z(n,p) = 1 if and only if pi(n,p) is odd. For all odd primes p, if E(n,p) is even then z(n,p) = 2 (the converse is not necessarily true). [Comment revised by _Jianing Song_, Jul 06 2019]

%C z(n,p^e) = z(n,p) for all odd primes p. z(n,4) = 1 if n == 2, 3 (mod 4) and 2 if n == 0, 1 (mod 4). z(n,2^e) = 1 for even n and 2 for odd n, e >= 3.

%C By induction it is easy to show that T(n,k) = T(n,m+1)*T(n,k-m) - T(n,m)*T(k-m-1). Let k = 2m we have T(n,2m) = T(n,m)*(T(n,m+1)-T(m-1)); let k = 2m+1 we have T(n,2m+1) = T(n,m+1)^2 - T(n,m)^2 = (T(n,m+1)+T(n,m))*(T(n,m+1)-T(n,m)). So T(n,k) is composite if n >= 3, k >= 3. - _Jianing Song_, Jul 06 2019

%H Jianing Song, <a href="/A316269/b316269.txt">Antidiagonals n = 2..101, flattened</a>

%F T(2,k) = k; T(n,k) = (((n+sqrt(n^2 - 4))/2)^k - ((n - sqrt(n^2 - 4))/2)^k)/sqrt(n^2 - 4), n >= 3, k >= 0.

%F T(n^2+2,k) = A172236(n,2k); T(n^4+4n^2+2,k) = A172236(n,4k)/A172236(n,4).

%F For n >= 2, Sum_{i=1..k} 1/T(n,2^i) = 2/n - ((u^(2^k-1) + v^(2^k-1))/(u + v)) * (1/T(n,2^k)), where u = (n + sqrt(n^2 - 4))/2, v = (n - sqrt(n^2 - 4))/2 are the two roots of the polynomial x^2 - n*x + 1. As a result, Sum_{i=>1} 1/T(n,2^i) = (n - sqrt(n^2 - 4))/2. - _Jianing Song_, Apr 21 2019

%e The array starts in row n = 2 with columns k >= 0 as follows:

%e 0 1 2 3 4 5 6

%e 0 1 3 8 21 55 144

%e 0 1 4 15 56 209 780

%e 0 1 5 24 115 551 2640

%e 0 1 6 35 204 1189 6930

%e 0 1 7 48 329 2255 15456

%e 0 1 8 63 496 3905 30744

%e 0 1 9 80 711 6319 56160

%e 0 1 10 99 980 9701 96030

%e 0 1 11 120 1309 14279 155760

%t Table[If[# == 2, k, Simplify[(((# + Sqrt[#^2 - 4])/2)^k - ((# - Sqrt[#^2 - 4])/2)^k)/Sqrt[#^2 - 4]]] &[n - k + 2], {n, 0, 10}, {k, n, 0, -1}] // Flatten (* _Michael De Vlieger_, Jul 19 2018 *)

%o (PARI) T(n, k) = if (k==0, 0, if (k==1, 1, n*T(n,k-1) - T(n,k-2)));

%o tabl(nn) = for(n=2, nn, for (k=0, nn, print1(T(n,k), ", ")); print); \\ _Michel Marcus_, Jul 03 2018

%o (PARI) T(n, k) = ([n, -1; 1, 0]^k)[2, 1] \\ _Jianing Song_, Nov 10 2018

%Y Cf. A172236.

%Y Sequences with g.f. 1/(1-k*x+x^2): A001477 (k=2), A001906 (k=3), A001353 (k=4), A004254 (k=5), A001109 (k=6), A004187 (k=7), A001090 (k=8), A018913 (k=9), A004189 (k=10).

%Y Cf. A005563 (4th column), A242135 (5th column), A057722 (6th column).

%K nonn,tabl

%O 2,6

%A _Jianing Song_, Jun 28 2018