|
| |
|
|
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.
|
|
9
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
2,6
|
|
|
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
|
|
|
LINKS
|
|
|
|
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.
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
|
|
|
EXAMPLE
|
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
|
|
|
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 *)
|
|
|
PROG
|
(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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
