login
This site is supported by donations to The OEIS Foundation.

 

Logo


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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 22 00:32 EST 2019. Contains 329383 sequences. (Running on oeis4.)