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

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, 35, 115, 209, 144, 7, 0, 1, 8, 48, 204, 551, 780, 377, 8, 0, 1, 9, 63, 329, 1189, 2640, 2911, 987, 9, 0, 1, 10, 80, 496, 2255, 6930, 12649, 10864, 2584, 10

Offset: 2

Author

Jianing Song, Jun 28 2018

Keywords

• nonn
• tabl

Comments

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

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

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

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

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

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

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.

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.

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.

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:

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

.....1...........1...............0....................1

....-1..........-1...............0...................-1

.....1..........-1...............1....................0

....-1...........1..............-1....................0

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

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.

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.

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.

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.

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.

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

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

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

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

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

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

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

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]

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.

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]

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.

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

Examples

			The array starts in row n = 2 with columns k >= 0 as follows:
  0      1      2      3      4      5      6
  0      1      3      8     21     55    144
  0      1      4     15     56    209    780
  0      1      5     24    115    551   2640
  0      1      6     35    204   1189   6930
  0      1      7     48    329   2255  15456
  0      1      8     63    496   3905  30744
  0      1      9     80    711   6319  56160
  0      1     10     99    980   9701  96030
  0      1     11    120   1309  14279 155760
		

Links

• Jianing Song, Antidiagonals n = 2..101, flattened

Crossrefs

Cf. A172236.

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

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

Programs

Mathematica

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

PARI

T(n, k) = if (k==0, 0, if (k==1, 1, n*T(n,k-1) - T(n,k-2)));
tabl(nn) = for(n=2, nn, for (k=0, nn, print1(T(n,k), ", ")); print); \\ Michel Marcus, Jul 03 2018

PARI

T(n, k) = ([n, -1; 1, 0]^k)[2, 1] \\ Jianing Song, Nov 10 2018

Formula

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.

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

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