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

Author

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

Keywords

• nonn
• easy
• tabl

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.

Examples

			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.
		

Links

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

Crossrefs

Cf. A000010.

Cf. also A054523.

Programs

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

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