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,2

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.

Links

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

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

Formula

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

Example

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

Prog

(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), ", ")))

Crossrefs

Cf. A191743, A290110, A002088, A001221.

Sequence in context: A358120 A329501 A300670 * A137679 A152072 A105438

Adjacent sequences: A355471 A355472 A355473 * A355475 A355476 A355477

Keyword

nonn,tabl

Author

Luc Rousseau, Jul 03 2022

Status

approved