A227507 - OEIS

%I #36 Aug 01 2019 03:56:44

%S 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,

%T 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,

%U 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

%N 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.

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

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

%H U. Abel, W. Awan, and V. Kushnirevych, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Abel/abel5.html">A Generalization of the Gcd-Sum Function</a>, J. Int. Seq. 16 (2013), #13.6.7.

%H Peter H. van der Kamp, <a href="http://www.emis.de/journals/INTEGERS/papers/n24/n24.Abstract.html">On the Fourier transform of the greatest common divisor</a>, INTEGERS 13 (2013), A24.

%F 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.

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

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

%F 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)).

%e 1, 3, 5, 8, 9, 15, 13, 20, 21, 27

%e 1, 1, 2, 2, 4, 2, 6, 4, 6, 4

%e 1, 3, 2, 4, 4, 6, 6, 8, 6, 12

%e 1, 1, 5, 2, 4, 5, 6, 4, 12, 4

%e 1, 3, 2, 8, 4, 6, 6, 12, 6, 12

%e 1, 1, 2, 2, 9, 2, 6, 4, 6, 9

%e The array G_d(n) of Abel et al. (with A018804 on the diagonal) starts as follows:

%e 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ,...

%e 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3,...

%e 2, 2, 5, 2, 2, 5, 2, 2, 5, 2, 2, 5, 2, 2, 5, 2, 2, 5, 2, 2,...

%e 2, 4, 2, 8, 2, 4, 2, 8, 2, 4, 2, 8, 2, 4, 2, 8, 2, 4, 2, 8,...

%e 4, 4, 4, 4, 9, 4, 4, 4, 4, 9, 4, 4, 4, 4, 9, 4, 4, 4, 4, 9,...

%e 2, 6, 5, 6, 2,15, 2, 6, 5, 6, 2,15, 2, 6, 5, 6, 2,15, 2, 6,...

%e 6, 6, 6, 6, 6, 6,13, 6, 6, 6, 6, 6, 6,13, 6, 6, 6, 6, 6, 6,...

%e 4, 8, 4,12, 4, 8, 4,20, 4, 8, 4,12, 4, 8, 4,20, 4, 8, 4,12,..

%e 6, 6,12, 6, 6,12, 6, 6,21, 6, 6,12, 6, 6,12, 6, 6,21, 6, 6,...

%e 4,12, 4,12, 9,12, 4,12, 4,27, 4,12, 4,12, 9,12, 4,12, 4,27,...

%e 10,10,10,10,10,10,10,10,10,10,21,10,10,10,10,10,10,10,10,10,...

%e 4, 8,10,16, 4,20, 4,16,10, 8, 4,40, 4, 8,10,16, 4,20, 4,16,...

%e 12,12,12,12,12,12,12,12,12,12,12,12,25,12,12,12,12,12,12,12,...

%e ... - _R. J. Mathar_, Jan 21 2018

%p p:=(a,n)->add(d*phi(n/d),d in divisors(gcd(a,n))):

%p seq(seq(p(a,n-a),a=0..n-1),n=1..10);

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

%K nonn,mult,tabl

%O 1,2

%A _Peter H van der Kamp_, Jul 13 2013