The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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
 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 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 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. LINKS Table of n, a(n) for n=1..97. 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. 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)). EXAMPLE 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 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); CROSSREFS Cf. A000010, A018804, A054532, A054533, A054534, A054535. Sequence in context: A171232 A093423 A326454 * A134700 A085407 A325523 Adjacent sequences: A227504 A227505 A227506 * A227508 A227509 A227510 KEYWORD nonn,mult,tabl AUTHOR Peter H van der Kamp, Jul 13 2013 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 13 08:24 EDT 2024. Contains 375902 sequences. (Running on oeis4.)