A350900 Triangle read by rows: T(n, k) = Sum_{i=1..n} gcd(i,n) / gcd(gcd(i,k),n) for 1 <= k <= n.

1, 3, 2, 5, 5, 3, 8, 5, 8, 4, 9, 9, 9, 9, 5, 15, 10, 9, 10, 15, 6, 13, 13, 13, 13, 13, 13, 7, 20, 12, 20, 9, 20, 12, 20, 8, 21, 21, 11, 21, 21, 11, 21, 21, 9, 27, 18, 27, 18, 15, 18, 27, 18, 27, 10, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 11, 40, 25, 24, 20, 40, 15, 40, 20, 24, 25, 40, 12

Offset: 1

Author

Werner Schulte, Jan 21 2022

Keywords

• nonn
• easy
• tabl

Comments

Subtriangle (triangle without main diagonal) is symmetrical.

Conjecture: Let f be an arbitrary arithmetic function. Define for n > 0 the sequence a(f; n) = Sum_{i=1..n, k=1..n} f(gcd(i,n)/gcd(gcd(i,k),n)); a(f; n) equals Dirichlet convolution of f(n)*A000010(n) and A057660(n); if f is multiplicative, then a(f; n) is multiplicative; row sums of this triangle use f(n) = n (see formula section).

Examples

			The triangle T(n, k) for 1 <= k <= n starts:
n \k :   1   2   3   4   5   6   7   8   9  10  11  12
======================================================
   1 :   1
   2 :   3   2
   3 :   5   5   3
   4 :   8   5   8   4
   5 :   9   9   9   9   5
   6 :  15  10   9  10  15   6
   7 :  13  13  13  13  13  13   7
   8 :  20  12  20   9  20  12  20   8
   9 :  21  21  11  21  21  11  21  21   9
  10 :  27  18  27  18  15  18  27  18  27  10
  11 :  21  21  21  21  21  21  21  21  21  21  11
  12 :  40  25  24  20  40  15  40  20  24  25  40  12
  etc.
		

Crossrefs

Row sums gives A373059.

Cf. A000010, A002618, A018804, A057660, A050873.

Programs

PARI

T(n, k) = sum(i=1, n, gcd(i,n) / gcd(gcd(i,k),n));
row(n) = vector(n, k, T(n,k)); \\ Michel Marcus, Jan 22 2022

Formula

T(n, 1) = A018804(n); T(n, n) = n.

T(n, k) = T(n, n-k) for 1 <= k < n.

Conjecture: Row sums equal Dirichlet convolution of A002618 and A057660.