A227507 Table of p(a,n) read by antidiagonals, where p(a,n) = Sum_{k=1..n} gcd(k,n) exp(2 Pi i k a / n) is the Fourier transform of the greatest common divisor.

1, 3, 1, 5, 1, 1, 8, 2, 3, 1, 9, 2, 2, 1, 1, 15, 4, 4, 5, 3, 1, 13, 2, 4, 2, 2, 1, 1, 20, 6, 6, 4, 8, 2, 3, 1, 21, 4, 6, 5, 4, 2, 5, 1, 1, 27, 6, 8, 6, 6, 9, 4, 2, 3, 1, 21, 4, 6, 4, 6, 2, 4, 2, 2, 1, 1, 40, 10, 12, 12, 12, 6, 15, 4, 8, 5, 3, 1, 25, 4, 10, 4, 6, 4, 6, 2, 4, 2, 2, 1, 1, 39, 12, 8, 10, 12, 6

Offset: 1

Author

Peter H van der Kamp, Jul 13 2013

Keywords

• nonn
• mult
• tabl

Comments

p(a,n) gives the number of pairs (i,j) of congruence classes modulo n, such that i*j = a mod n.

p(a,n) is a multiplicative function of n.

Examples

			1, 3, 5, 8, 9, 15, 13, 20, 21, 27
1, 1, 2, 2, 4, 2, 6, 4, 6, 4
1, 3, 2, 4, 4, 6, 6, 8, 6, 12
1, 1, 5, 2, 4, 5, 6, 4, 12, 4
1, 3, 2, 8, 4, 6, 6, 12, 6, 12
1, 1, 2, 2, 9, 2, 6, 4, 6, 9
The array G_d(n) of Abel et al. (with A018804 on the diagonal) starts as follows:
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ,...
1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3,...
2, 2, 5, 2, 2, 5, 2, 2, 5, 2, 2, 5, 2, 2, 5, 2, 2, 5, 2, 2,...
2, 4, 2, 8, 2, 4, 2, 8, 2, 4, 2, 8, 2, 4, 2, 8, 2, 4, 2, 8,...
4, 4, 4, 4, 9, 4, 4, 4, 4, 9, 4, 4, 4, 4, 9, 4, 4, 4, 4, 9,...
2, 6, 5, 6, 2,15, 2, 6, 5, 6, 2,15, 2, 6, 5, 6, 2,15, 2, 6,...
6, 6, 6, 6, 6, 6,13, 6, 6, 6, 6, 6, 6,13, 6, 6, 6, 6, 6, 6,...
4, 8, 4,12, 4, 8, 4,20, 4, 8, 4,12, 4, 8, 4,20, 4, 8, 4,12,..
6, 6,12, 6, 6,12, 6, 6,21, 6, 6,12, 6, 6,12, 6, 6,21, 6, 6,...
4,12, 4,12, 9,12, 4,12, 4,27, 4,12, 4,12, 9,12, 4,12, 4,27,...
10,10,10,10,10,10,10,10,10,10,21,10,10,10,10,10,10,10,10,10,...
4, 8,10,16, 4,20, 4,16,10, 8, 4,40, 4, 8,10,16, 4,20, 4,16,...
12,12,12,12,12,12,12,12,12,12,12,12,25,12,12,12,12,12,12,12,...
... - _R. J. Mathar_, Jan 21 2018
		

Links

• U. Abel, W. Awan, and V. Kushnirevych, A Generalization of the Gcd-Sum Function, J. Int. Seq. 16 (2013), #13.6.7.
• Peter H. van der Kamp, On the Fourier transform of the greatest common divisor, INTEGERS 13 (2013), A24.

Crossrefs

Cf. A000010, A018804, A054532, A054533, A054534, A054535.

Programs

Maple

p:=(a,n)->add(d*phi(n/d),d in divisors(gcd(a,n))):
seq(seq(p(a,n-a),a=0..n-1),n=1..10);

Formula

The function can be written as a generalized Ramanujan sum: p(a,n) = Sum_{d|gcd(a,n)} d phi(n/d), where phi(n) denotes the totient function.

The rows of its table are equal to two of the diagonals: p(a,n) = p(n-a,n) = p(n+a,n).

p(0,n) = A018804(n), p(1,n) = A000010(n).

f(n) = Sum_{k=1..n} p(r,k)/k = Sum_{k=1..n} c_k(r)/k * floor(n/k), where c_k(r) denotes Ramanujan's sum (A054533(r)).