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,12

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

Links

Table of n, a(n) for n=0..104.

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

Formula

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

Example

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.

Crossrefs

Cf. A008967, A047971, A219237, A000005.

Sequence in context: A127323 A327298 A132896 * A257921 A261119 A004541

Adjacent sequences: A089786 A089787 A089788 * A089790 A089791 A089792

Keyword

easy,nonn,tabl

Author

Paul Boddington, Jan 09 2004

Status

approved