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

%I #15 Jan 15 2024 12:02:48

%S 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,

%T 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,

%U 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

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

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

%C The row sum is A000010(n).

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

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

%C 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.

%C From _Peter Bala_, Dec 24 2023: (Start)

%C Essentially the same as triangle A217831.

%C 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)

%H Peter Bala, <a href="/A300294/a300294.pdf">A q-analogue of the totient function</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Euler%27s_totient_function">Euler's totient function</a>

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

%F 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

%e The irregular triangle t begins:

%e n/m 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ...

%e 1: 1

%e 2: 1

%e 3: 1 1

%e 4: 1 0 1

%e 5: 1 1 1 1

%e 6: 1 0 0 0 1

%e 7: 1 1 1 1 1 1

%e 8: 1 0 1 0 1 0 1

%e 9: 1 1 0 1 1 0 1 1

%e 10: 1 0 1 0 0 0 1 0 1

%e 11: 1 1 1 1 1 1 1 1 1 1

%e 12: 1 0 0 0 1 0 1 0 0 0 1

%e 13: 1 1 1 1 1 1 1 1 1 1 1 1

%e 14: 1 0 1 0 1 0 0 0 1 0 1 0 1

%e 15: 1 1 0 1 0 0 1 1 0 0 1 0 1 1

%e 16: 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

%e 17: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

%e 18: 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1

%e 19: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

%e 20: 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1

%e ....

%e 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

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

%K nonn,tabf,easy

%O 1

%A _Wolfdieter Lang_, Mar 03 2018