A355474 Square array T(m,n) = Card({ (i, j) : 1 <= i <= m, 1 <= j <= min(n, i), GCD(i, j) = 1 }), read by antidiagonals upwards.

1, 2, 1, 3, 2, 1, 4, 4, 2, 1, 5, 5, 4, 2, 1, 6, 7, 6, 4, 2, 1, 7, 8, 9, 6, 4, 2, 1, 8, 10, 10, 10, 6, 4, 2, 1, 9, 11, 13, 11, 10, 6, 4, 2, 1, 10, 13, 15, 15, 12, 10, 6, 4, 2, 1, 11, 14, 17, 17, 17, 12, 10, 6, 4, 2, 1, 12, 16, 19, 20, 20, 18, 12, 10, 6, 4, 2, 1

Offset: 1

Author

Luc Rousseau, Jul 03 2022

Keywords

• nonn
• tabl

Comments

Also the number of regions in the 0 < x < y sector of the plane that are delimited by the lines with equations i*x + j*y = 0, where i and j are integers, not both 0, and |i| <= m, |j| <= n. This remark is motivated by Factorization Patterns (FPs) and Factorization Patterns of Sequences of Divisors (FPSD) concerns, as defined in A191743 and A290110. This is the case k=2 of a more general problem where k is omega(z)=A001221(z), the number of distinct primes dividing z, for which we would define T(n1,n2,...,nk) instead of T(m,n). The idea is the following: two numbers (e.g., 12 and 20) can have the same FP (p^2*q) without having the same FPSD ([1 < p < q < p^2 < p*q < p^2*q] != [1 < p < p^2 < q < p*q < p^2*q]). T(m,n) tells how many distinct FPSDs share the same FP of the p^m*q^n form. See the illustration for (m,n) = (2,1), section Links.

Examples

			Let m=2 and n=1. There are exactly two lattice points (i, j) that satisfy 1 <= i <= 2 and 1 <= j <= min(1, i) and GCD(i, j) = 1, namely (1, 1) and (2, 1). So T(2,1) = 2.
Array begins:
  m\n|  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
  ---+----------------------------------------------------
   1 |  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
   2 |  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2
   3 |  3  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4
   4 |  4  5  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6
   5 |  5  7  9 10 10 10 10 10 10 10 10 10 10 10 10 10 10
   6 |  6  8 10 11 12 12 12 12 12 12 12 12 12 12 12 12 12
   7 |  7 10 13 15 17 18 18 18 18 18 18 18 18 18 18 18 18
   8 |  8 11 15 17 20 21 22 22 22 22 22 22 22 22 22 22 22
   9 |  9 13 17 20 24 25 27 28 28 28 28 28 28 28 28 28 28
  10 | 10 14 19 22 26 27 30 31 32 32 32 32 32 32 32 32 32
  11 | 11 16 22 26 31 33 37 39 41 42 42 42 42 42 42 42 42
  12 | 12 17 23 27 33 35 40 42 44 45 46 46 46 46 46 46 46
  13 | 13 19 26 31 38 41 47 50 53 55 57 58 58 58 58 58 58
  14 | 14 20 28 33 41 44 50 53 57 59 62 63 64 64 64 64 64
  15 | 15 22 30 36 44 47 54 58 62 64 68 69 71 72 72 72 72
  16 | 16 23 32 38 47 50 58 62 67 69 74 75 78 79 80 80 80
  17 | 17 25 35 42 52 56 65 70 76 79 85 87 91 93 95 96 96
		

Links

• Luc Rousseau, Illustration of T(2,1)=2 and its relationship with the p^2*q factorization pattern.

Crossrefs

Cf. A191743, A290110, A002088, A001221.

Programs

PARI

T(m, n) = sum(i=1, m, sum(j=1, min(n, i), gcd(i, j)==1))
for(d=2,10,for(n=1,d-1,my(m=d-n);print1(T(m,n),", ")))

Formula

T(n,n) = A002088(n).