login
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
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.
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
KEYWORD
nonn,tabl
AUTHOR
Luc Rousseau, Jul 03 2022
STATUS
approved