A346018 Triangle read by rows: T(n,k) is the number of integers m such that 1 <= m <= n and gcd(m,n) <= k, 1 <= k <= n.

1, 1, 2, 2, 2, 3, 2, 3, 3, 4, 4, 4, 4, 4, 5, 2, 4, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 7, 4, 6, 6, 7, 7, 7, 7, 8, 6, 6, 8, 8, 8, 8, 8, 8, 9, 4, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 4, 6, 8, 10, 10, 11, 11, 11, 11, 11, 11, 12

Offset: 1

Author

Pontus von Brömssen, Jul 01 2021

Keywords

• nonn
• tabl

Examples

			Triangle begins:
   n\k  1  2  3  4  5  6  7  8  9 10
  ----------------------------------
   1:   1
   2:   1  2
   3:   2  2  3
   4:   2  3  3  4
   5:   4  4  4  4  5
   6:   2  4  5  5  5  6
   7:   6  6  6  6  6  6  7
   8:   4  6  6  7  7  7  7  8
   9:   6  6  8  8  8  8  8  8  9
  10:   4  8  8  8  9  9  9  9  9 10
		

Crossrefs

Cf. A000010 (column k=1), A126246 (column k=2), A032742.

Programs

PARI

T(n,k) = sum(m=1, n, gcd(m, n) <= k); \\ Michel Marcus, Jul 01 2021

Formula

T(n,1) = A000010(n).

T(n,2) = A126246(n).

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

T(n,n) = n.