A089789 Number of irreducible factors of Gauss polynomials.

0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 2, 2, 2, 0, 0, 1, 2, 2, 1, 0, 0, 3, 3, 4, 3, 3, 0, 0, 1, 3, 3, 3, 3, 1, 0, 0, 3, 3, 5, 4, 5, 3, 3, 0, 0, 2, 4, 4, 5, 5, 4, 4, 2, 0, 0, 3, 4, 6, 5, 7, 5, 6, 4, 3, 0, 0, 1, 3, 4, 5, 5, 5, 5, 4, 3, 1, 0, 0, 5, 5, 7, 7, 9, 7, 9, 7, 7, 5, 5, 0, 0, 1, 5, 5, 6, 7, 7, 7, 7, 6, 5, 5, 1, 0

Offset: 0

Author

Paul Boddington, Jan 09 2004

Keywords

• easy
• nonn
• tabl

Comments

T(n,k) is the number of irreducible factors of the (separable) polynomial [n]!/([k]![n-k]!). Here [n]! denotes the product of the first n quantum integers, the n-th quantum integer being defined as (1-q^n)/(1-q).

T(n,k) gives the number of positive integers m <= n such that (n mod m) < (k mod m). - Tom Edgar, Aug 21 2014

Examples

			The triangle T(n,k) begins:
n\k  0  1  2  3  4  5  6  7  8  9  10  11  12  13 ...
0:   0
1:   0  0
2:   0  1  0
3:   0  1  1  0
4:   0  2  2  2  0
5:   0  1  2  2  1  0
6:   0  3  3  4  3  3  0
7:   0  1  3  3  3  3  1  0
8:   0  3  3  5  4  5  3  3  0
9:   0  2  4  4  5  5  4  4  2  0
10:  0  3  4  6  5  7  5  6  4  3   0
11:  0  1  3  4  5  5  5  5  4  3   1   0
12:  0  5  5  7  7  9  7  9  7  7   5   5   0
13:  0  1  5  5  6  7  7  7  7  6   5   5   1   0
... Formatted by _Wolfdieter Lang_, Dec 07 2012
T(8,3) equals the number of irreducible factors of (1-q^8)(1-q^7)(1-q^6)/((1-q^3)(1-q^2)(1-q)), which is a product of 5 cyclotomic polynomials in q, namely the 2nd, 4th, 6th, 7th and 8th. Thus T(8,3)=5.
		

Links

• Stan Wagon and Herbert S. Wilf, When are subset sums equidistributed modulo m?, The Electronic Journal of Combinatorics, Vol. 1, 1994 (#R3).

Crossrefs

Cf. A008967, A047971, A219237, A000005.

Formula

T(n, k) = T(n-1, k-1) + d(n) - d(k), where d(n) is the number of divisors of n.