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

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A054533 Triangular array giving Ramanujan sum T(n,k) = c_n(k) = Sum_{m=1..n, (m,n)=1} exp(2 Pi i m k / n) for n >= 1 and 1 <= k <= n. 24

%I #110 Jan 01 2023 19:57:52

%S 1,-1,1,-1,-1,2,0,-2,0,2,-1,-1,-1,-1,4,1,-1,-2,-1,1,2,-1,-1,-1,-1,-1,

%T -1,6,0,0,0,-4,0,0,0,4,0,0,-3,0,0,-3,0,0,6,1,-1,1,-1,-4,-1,1,-1,1,4,

%U -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,10,0,2,0,-2,0,-4,0,-2,0,2,0,4,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,12,1

%N Triangular array giving Ramanujan sum T(n,k) = c_n(k) = Sum_{m=1..n, (m,n)=1} exp(2 Pi i m k / n) for n >= 1 and 1 <= k <= n.

%C From _Wolfdieter Lang_, Jan 06 2017: (Start)

%C Periodicity: c_n(k+n) = c_n(k). See the Apostol reference p. 161.

%C Multiplicativity: c_n(k)*c_m(k) = c_{n*m}(k), if gcd(n,m) = 1. For the proof see the Hardy reference, p. 138.

%C Dirichlet g.f. for fixed k: D(n,s) := Sum_{n>=1} c_n(k)/n^s = sigma_{1-s}(k)/zeta(s) = sigma_{s-1}(k)/(k^(s-1)*zeta(s)) for s > 1, with sigma_m(k) the sum of the m-th power of the divisors of k. See the Hardy reference, eqs. (9.6.1) and (9.6.2), pp. 139-140, or Hardy-Wright, Theorem 292, p. 250.

%C Sum_{n>=1} c_n(k)/n = 0. See the Hardy reference, p. 141. (End)

%C Right border gives A000010. - _Omar E. Pol_, May 08 2018

%C Fredman (1975) proved that the number S(n, k, v) of vectors (a_0, ..., a_{n-1}) of nonnegative integer components that satisfy a_0 + ... + a_{n-1} = k and Sum_{i=0..n-1} i*a_i = v (mod n) is given by S(n, k, v) = (1/(n + k)) * Sum_{d | gcd(n, k)} T(d, v) * binomial((n + k)/d, k/d) = S(k, n, v). This was also proved by Elashvili et al. (1999), who also proved that S(n, k, v) = Sum_{d | gcd(n, k, v)} S(n/d, k/d, 1). Here, S(n, k, 1) = A051168(n + k, k). - _Petros Hadjicostas_, Jul 09 2019

%C We have T(n, k) = c_n(k) = Sum_{m=1..n, (m,n)=1} exp(2 Pi i m k / n) and A054532(n, k) = c_k(n) = Sum_{m=1..k, (m,k)=1} exp(2 Pi i m n / k) for n >= 1 and 1 <= k <= n. - _Petros Hadjicostas_, Jul 27 2019

%D T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, pp. 160-161.

%D G. H. Hardy, Ramanujan: twelve lectures on subjects suggested by his life and work, AMS Chelsea Publishing, Providence, Rhode Island, 2002, pp. 137-139.

%D G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. Fifth ed., Oxford Science Publications, Clarendon Press, Oxford, 2003, pp. 237-238.

%H Seiichi Manyama, <a href="/A054533/b054533.txt">Rows n=1..140 of triangle, flattened</a> (Rows 1..50 from T. D. Noe)

%H Tom M. Apostol, <a href="https://projecteuclid.org/euclid.pjm/1102968273">Arithmetical properties of generalized Ramanujan sums</a>, Pacific J. Math. 41 (1972), 281-293.

%H Eckford Cohen, <a href="https://dx.doi.org/10.1073/pnas.41.11.939">A class of arithmetic functions</a>, Proc. Natl. Acad. Sci. USA 41 (1955), 939-944.

%H A. Elashvili, M. Jibladze, and D. Pataraia, <a href="http://dx.doi.org/10.1023/A:1018727630642">Combinatorics of necklaces and "Hermite reciprocity"</a>, J. Algebraic Combin. 10 (1999), 173-188.

%H M. L. Fredman, <a href="https://doi.org/10.1016/0097-3165(75)90008-4">A symmetry relationship for a class of partitions</a>, J. Combinatorial Theory Ser. A 18 (1975), 199-202.

%H Emiliano Gagliardo, <a href="http://www.bdim.eu/item?id=BUMI_1953_3_8_3_269_0">Le funzioni simmetriche semplici delle radici n-esime primitive dell'unità</a>, Bollettino dell'Unione Matematica Italiana Serie 3, 8(3) (1953), 269-273.

%H Otto Hölder, <a href="http://matwbn.icm.edu.pl/ksiazki/pmf/pmf43/pmf4312.pdf">Zur Theorie der Kreisteilungsgleichung K_m(x)=0</a>, Prace mat.-fiz. 43 (1936), 13-23.

%H Peter H. van der Kamp, <a href="http://emis.impa.br/EMIS/journals/INTEGERS/papers/n24/n24.Abstract.html">On the Fourier transform of the greatest common divisor</a>, Integers 13 (2013), #A24. [See Section 3 for historical remarks.]

%H J. C. Kluyver, <a href="https://www.dwc.knaw.nl/DL/publications/PU00013765.pdf">Some formulae concerning the integers less than n and prime to n</a>, in: KNAW, Proceedings, 9 I, 1906, Amsterdam, 1906, pp. 408-414. [See bottom of p. 410, where the author proves that Sum cos(2*Pi*q*v/n) = mu(n/D) * phi(n) /phi(n/D), where D is the gcd of n and q. The summation is over integers v "less than n and prime to n" (top of p. 408).]

%H C. A. Nicol, <a href="https://dx.doi.org/10.1073/pnas.39.9.963">On restricted partitions and a generalization of the Euler phi number and the Moebius function</a>, Proc. Natl. Acad. Sci. USA 39(9) (1953), 963-968.

%H C. A. Nicol and H. S. Vandiver, <a href="https://dx.doi.org/10.1073/pnas.40.9.825 ">A von Sterneck arithmetical function and restricted partitions with respect to a modulus</a>, Proc. Natl. Acad. Sci. USA 40(9) (1954), 825-835.

%H K. G. Ramanathan, <a href="https://www.ias.ac.in/article/fulltext/seca/020/01/0062-0069">Some applications of Ramanujan's trigonometrical sum C_m(n)</a>, Proc. Indian Acad. Sci., Sect. A 20 (1944), 62-69.

%H Srinivasa Ramanujan, <a href="http://ramanujan.sirinudi.org/Volumes/published/ram21.pdf">On certain trigonometric sums and their applications in the theory of numbers</a>, Trans. Camb. Phil. Soc. 22 (1918), 259-276.

%H R. D. von Sterneck, <a href="https://play.google.com/books/reader?id=V1I-AQAAMAAJ&amp;hl=de&amp;printsec=frontcover&amp;pg=GBS.PA1567">Ein Analogon zur additiven Zahlentheorie</a>, Sitzungsber. Akad. Wiss. Sapientiae Math.-Naturwiss. Kl. 111 (1902), 1567-1601 (Abt. IIa).

%H R. D. von Sterneck, <a href="https://eudml.org/doc/144877">Über ein Analogon zur additiven Zahlentheorie</a>, Jahresbericht der Deutschen Mathematiker-Vereinigung 12 (1903), 110-113.

%H M. V. Subbarao, <a href="https://www.jstor.org/stable/2310974">The Brauer-Rademacher identity</a>, Amer. Math. Monthly 72 (1965), 135-138.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Ramanujan%27s_sum">Ramanujan's sum</a>.

%H Wikipedia, <a href="https://de.wikipedia.org/wiki/Robert_Daublebsky_von_Sterneck_der_J%C3%BCngere">Robert Daublebsky von Sterneck der Jüngere</a>.

%H Aurel Wintner, <a href="https://www.jstor.org/stable/2371672">On a statistics of the Ramanujan sums</a>, Amer. J. Math., 64(1) (1942), 106-114.

%F T(n, k) = Sum_{m=1..n, gcd(m,n) = 1} exp(2*Pi*i*m*k / n), n >= 1, 1 <= k <= n, where i is the imaginary unit.

%F T(n, k) = Sum_{d | gcd(n,k)} d*Moebius(n/d), n >= 1, 1 <= k <= n.

%e Triangle begins

%e 1;

%e -1, 1;

%e -1, -1, 2;

%e 0, -2, 0, 2;

%e -1, -1, -1, -1, 4;

%e 1, -1, -2, -1, 1, 2;

%e -1, -1, -1, -1, -1, -1, 6;

%e 0, 0, 0, -4, 0, 0, 0, 4;

%e 0, 0, -3, 0, 0, -3, 0, 0, 6;

%e 1, -1, 1, -1, -4, -1, 1, -1, 1, 4;

%e -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 10;

%e 0, 2, 0, -2, 0, -4, 0, -2, 0, 2, 0, 4;

%e -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 12;

%e ...

%e [Edited by _Jon E. Schoenfield_, Jan 03 2017]

%e Periodicity and multiplicativity: c_6(k) = c_2(k)*c_3(k), e.g.: 2 = c_6(6) = c_2(6)*c_3(6) = c_2(2)*c_3(3) = 1*2 = 2. - _Wolfdieter Lang_, Jan 05 2017

%t c[k_, n_] := Sum[ If[GCD[m, k] == 1, Exp[2 Pi*I*m*n/k], 0], {m, 1, k}]; A054533 = Flatten[ Table[c[n, k] // FullSimplify, {n, 1, 14}, {k, 1, n}] ] (* _Jean-François Alcover_, Jun 27 2012 *)

%t (* to get the triangle in the example above *)

%t FormTable[Table[c[n, k] // FullSimplify, {n, 1, 13}, {k, 1, n}]]

%t (* _Petros Hadjicostas_, Jul 28 2019 *)

%o (PARI) T(n,k) = sumdiv(gcd(n,k), d, d*moebius(n/d));

%o tabl(nn) = {for(n=1, nn, for(k=1, n, print1(T(n,k), ", "); ); print(); ); }; \\ _Michel Marcus_, Jun 14 2018

%Y Cf. A008683, A054532, A054534, A054535, A282634, A000010.

%K sign,easy,nice,tabl

%O 1,6

%A _N. J. A. Sloane_, Apr 09 2000

%E Name edited by _Petros Hadjicostas_, Jul 27 2019

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 14:38 EDT 2024. Contains 371254 sequences. (Running on oeis4.)