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