A300294 Irregular triangle giving the GCD characteristic: t(n, m) = 1 if gcd(n, m) = 1 and zero otherwise, with t(1, 1) = 1 and t(n, m) for n >= 2 and m = 1..(n-1).

1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1

Offset

1

Comments

The sequence of row lengths is 1 for n = 1 and n-1 for n >= 2.

The row sum is A000010(n).

This is the triangle T = A054521 without the T(n, n) = 0 entries.

Without the leading 1 this is as a sequence the triangle A054431 read by rows.

If one puts for n >= 2 also T(n, m) = 0 if (-1)^(n+m) = -1 (not both, n and m, even or odd) then one obtains the triangle A249866 for primitive Pythagorean triples.

From Peter Bala, Dec 24 2023: (Start)

Essentially the same as triangle A217831.

Let phi(n, q) = Sum_{1 <= k <= n, (k, n) = 1} q^k denote the n-th row polynomial of this triangle, so that phi(n, 1) = phi(n) = A000010(n), the Euler totient function. The Gauss formula Sum_{d | n} phi(d) = n and its Möbius inverse formula Sum_{d | n} mu(d)*n/d = phi(n) have the q-analog identities Sum_{d | n} phi(d, q^(n/d)) = q + q^2 + ... + q^n and, for n >= 2, Sum_{d | n} mu(d)*(q^n - 1)/(q^d - 1) = phi(n, q). (End)

Links

Table of n, a(n) for n=1..106.

Peter Bala, A q-analogue of the totient function

Wikipedia, Euler's totient function

Formula

t(1,1) = 1, t(n, m) = 1 if gcd(n, m) = 1 and 0 otherwise, for n >= 1, and m = 1..n-1.

G.f.: Sum_{n >= 1} mobius(n)*x^n/((1 - x^n)*(1 - (q*x)^n)) = q*x + q*x^2 + (q + q^2)*x^3 + (q + q^3)*x^4 + (q + q^2 + q^3 + q^4)*x^5 + (q + q^5)*x^6 + .... - Peter Bala, Dec 29 2023

Example

The irregular triangle t begins:
n/m  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ...
1:   1
2:   1
3:   1 1
4:   1 0 1
5:   1 1 1 1
6:   1 0 0 0 1
7:   1 1 1 1 1 1
8:   1 0 1 0 1 0 1
9:   1 1 0 1 1 0 1 1
10:  1 0 1 0 0 0 1 0 1
11:  1 1 1 1 1 1 1 1 1  1
12:  1 0 0 0 1 0 1 0 0  0  1
13:  1 1 1 1 1 1 1 1 1  1  1  1
14:  1 0 1 0 1 0 0 0 1  0  1  0  1
15:  1 1 0 1 0 0 1 1 0  0  1  0  1  1
16:  1 0 1 0 1 0 1 0 1  0  1  0  1  0  1
17:  1 1 1 1 1 1 1 1 1  1  1  1  1  1  1  1
18:  1 0 0 0 1 0 1 0 0  0  1  0  1  0  0  0  1
19:  1 1 1 1 1 1 1 1 1  1  1  1  1  1  1  1  1  1
20:  1 0 1 0 0 0 1 0 1  0  1  0  1  0  0  0  1  0  1
....
G.f. of row 10 = Sum_{d | 10} mu(d)*(x^10 - 1)/(x^d - 1) = (x^10 - 1)/(x - 1) - (x^10 - 1)/(x^2 - 1) - (x^10 - 1)/(x^5 - 1) + (x^10 - 1) /(x^10 - 1) = x + x^3 + x^7 + x^9. - Peter Bala, Dec 24 2023

Crossrefs

Cf. A000010 (row sums), A008683, A054431, A054521, A217831, A249866, A367544 - A367547.

Sequence in context: A294934 A360128 A174340 * A071041 A082551 A152614

Adjacent sequences: A300291 A300292 A300293 * A300295 A300296 A300297

Keyword

nonn,tabf,easy

Author

Wolfdieter Lang, Mar 03 2018

Status

approved