A087623 Square array A(n,k) = the cardinality of the set {x in [1,k-1] : gcd(x,k)=n}, read by rising antidiagonals.

0, 0, 1, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 1, 4, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 6, 0, 0, 0, 0, 0, 1, 0, 4, 0, 0, 0, 0, 0, 0, 0, 2, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 1, 2, 4, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 2, 0, 6

Offset

1,6

Comments

Triangle read by rows: T(m,n) is the cardinality of the set {k in [1,n-1] : gcd(k,n)=m}. - The original definition.

A generalization of Euler's phi function: the n-th term of topmost row = A000010(n), for n > 1.

Links

Antti Karttunen, Table of n, a(n) for n = 1..22155; the first 210 antidiagonals of the array (rows of the triangle)

Example

The top left corner of the array:
n\k| 1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18
---+------------------------------------------------------------------------
1  | 0,  1,  2,  2,  4,  2,  6,  4,  6,  4, 10,  4, 12,  6,  8,  8, 16,  6,
2  | 0,  0,  0,  1,  0,  2,  0,  2,  0,  4,  0,  2,  0,  6,  0,  4,  0,  6,
3  | 0,  0,  0,  0,  0,  1,  0,  0,  2,  0,  0,  2,  0,  0,  4,  0,  0,  2,
4  | 0,  0,  0,  0,  0,  0,  0,  1,  0,  0,  0,  2,  0,  0,  0,  2,  0,  0,
5  | 0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  0,  0,  0,  0,  2,  0,  0,  0,
6  | 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  0,  0,  0,  0,  0,  2,
7  | 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  0,  0,  0,  0,
8  | 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  0,  0,
9  | 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,
etc.
A(1,4) = 2 and A(2,4) = 1 because gcd(1,4)=1, gcd(2,4)=2, gcd(3,4)=1.
A(1,12) = 4, A(2,12) = A(3,12) = A(4,12) = 2, and A(6,12) = 1 because gcd(1,12) = gcd(5,12) = gcd(7,12) = gcd(9,12) = 1, gcd(2,12) = gcd(10,12) = 2, gcd(3,12) = gcd(9,12) = 3, gcd(4,12) = gcd(8,12) = 4 and gcd(6,12) = 6.

Prog

(PARI)
up_to = 105;
A087623sq(n, k) = sum(x=1, k-1, gcd(x, k)==n);
A087623list(up_to) = { my(v = vector(up_to), i=0); for(a=1, oo, for(col=1, a, i++; if(i > up_to, return(v)); v[i] = A087623sq((a-(col-1)), col))); (v); };
v087623 = A087623list(up_to);
A087623(n) = v087623[n]; \\ Antti Karttunen, Jan 17 2025

Crossrefs

Cf. A000010.

Cf. also A054523.

Sequence in context: A083914 A083891 A363860 * A387991 A265260 A363888

Adjacent sequences: A087620 A087621 A087622 * A087624 A087625 A087626

Keyword

nonn,easy,tabl

Author

Michele Dondi (bik.mido(AT)tiscalinet.it), Sep 14 2003

Extensions

Definition rephrased in terms of square array instead of triangular table, and data section extended up to 105 terms by Antti Karttunen, Jan 17 2025

Status

approved