A054533 -id:A054533 - cp's OEIS frontend

A051168 Triangular array T(h,k) for 0 <= k <= h read by rows: T(h,k) = number of binary Lyndon words with k ones and h-k zeros.

1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 2, 2, 1, 0, 0, 1, 2, 3, 2, 1, 0, 0, 1, 3, 5, 5, 3, 1, 0, 0, 1, 3, 7, 8, 7, 3, 1, 0, 0, 1, 4, 9, 14, 14, 9, 4, 1, 0, 0, 1, 4, 12, 20, 25, 20, 12, 4, 1, 0, 0, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 0, 0, 1, 5, 18, 40, 66, 75, 66, 40, 18, 5, 1, 0, 0, 1, 6

Offset: 0

Clark Kimberling

T(h,k) is the number of classes of aperiodic binary words of k ones and h-k zeros; words u,v are in the same class if v is a cyclic permutation of u (e.g., u=111000, v=110001) and a word is aperiodic if not a juxtaposition of 2 or more identical subwords.
T(2n, n), T(2n+1, n), T(n, 3) match A022553, A000108, A001840, respectively. Row sums match A001037.
From R. J. Mathar, Jul 31 2008: (Start)
This triangle may also be regarded as the square array A(r,n), the n-th term of the r-th Witt transform of the all-1 sequence, r >= 1, n >= 0, read by antidiagonals:
This array begins as follows:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9
0 1 2 3 5 7 9 12 15 18 22 26 30 35 40 45 51 57 63
0 1 2 5 8 14 20 30 40 55 70 91 112 140 168 204 240 285 330
0 1 3 7 14 25 42 66 99 143 200 273 364 476 612 775 969 1197 1463
0 1 3 9 20 42 75 132 212 333 497 728 1026 1428 1932 2583 3384 4389 5598
0 1 4 12 30 66 132 245 429 715 1144 1768 2652 3876 5537 7752 10659 14421 19228
0 1 4 15 40 99 212 429 800 1430 2424 3978 6288 9690 14520 21318 30624 43263 60060
0 1 5 18 55 143 333 715 1430 2700 4862 8398 13995 22610 35530 54477 81719 120175
0 1 5 22 70 200 497 1144 2424 4862 9225 16796 29372 49742 81686 130750 204248
0 1 6 26 91 273 728 1768 3978 8398 16796 32065 58786 104006 178296 297160 482885
0 1 6 30 112 364 1026 2652 6288 13995 29372 58786 112632 208012 371384 643842
0 1 7 35 140 476 1428 3876 9690 22610 49742 104006 208012 400023 742900 1337220
0 1 7 40 168 612 1932 5537 14520 35530 81686 178296 371384 742900 1432613 2674440
...
It is essentially symmetric: A(r,r+i) = A(r,r-i+1).
Some of the diagonals are:
A(r,r+1): A000108
A(r,r): A022553
A(r,r-1): A000108
A(r,r+2): A000150
A(r,r+3): A050181
A(r,r+4): A050182
A(r,r+5): A050183
A(r,r-2): A000150 (End)
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)} A054533(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) = T(n + k, k). - Petros Hadjicostas, Jul 09 2019

			Triangle begins with:
h=0: 1
h=1: 1, 1
h=2: 0, 1, 0
h=3: 0, 1, 1, 0
h=4: 0, 1, 1, 1,  0
h=5: 0, 1, 2, 2,  1,  0
h=6: 0, 1, 2, 3,  2,  1, 0
h=7: 0, 1, 3, 5,  5,  3, 1, 0
h=8: 0, 1, 3, 7,  8,  7, 3, 1, 0
h=9: 0, 1, 4, 9, 14, 14, 9, 4, 1, 0
...
T(6,3) counts classes {111000},{110100},{110010}, each of 6 aperiodic. The class {100100} contains 3 periodic words, counted by T(3,1) as {100}, consisting of 3 aperiodic words 100,010,001.

Andrew Howroyd, Table of n, a(n) for n = 0..1274
Freddy Cachazo and Nick Early, Planar Kinematics: Cyclic Fixed Points, Mirror Superpotential, k-Dimensional Catalan Numbers, and Root Polytopes, arXiv:2010.09708 [math.CO], 2020.
A. Elashvili and M. Jibladze, Hermite reciprocity for the regular representations of cyclic groups, Indag. Math. (N.S.) 9 (1998), no. 2, 233-238; MR1691428 (2000c:13006).
A. Elashvili, M. Jibladze, and D. Pataraia, Combinatorics of necklaces and "Hermite reciprocity", J. Algebraic Combin. 10 (1999), no. 2, 173-188; MR1719140 (2000j:05009). See p. 174. - _N. J. A. Sloane_, Aug 06 2014
M. L. Fredman, A symmetry relationship for a class of partitions, J. Combinatorial Theory Ser. A 18 (1975), 199-202.
Romeo Meštrović, Different classes of binary necklaces and a combinatorial method for their enumerations, arXiv:1804.00992 [math.CO], 2018.
Pieter Moree, The formal series Witt transform, Discr. Math. no. 295 vol. 1-3 (2005) 143-160.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
P. Stanica and S. Maitra, Rotation symmetric boolean functions - count and cryptographic properties, Disc. Appl. Math. 156 (2008) 1567-1580; see h_{n,w} in eq. (3).
Index entries for sequences related to Lyndon words

Columns 1-11: A000012, A004526(n-1), A001840(n-4), A006918(n-4), A011795(n-1), A011796(n-6), A011797(n-1), A031164(n-9), A011845, A032168, A032169. See also A000150.

Cf. A047996, A052307, A052314, A092964, A185158, A123223, A124814.

A := proc(r,n) local gf,d,genf; genf := 1/(1-x) ; gf := 0 ; for d in numtheory[divisors](r) do gf := gf + numtheory[mobius](d)*(subs(x= x^d,genf))^(r/d) ; od: gf := expand(gf/r) ; coeftayl(gf,x=0,n) ; end proc:
A051168 := proc(n,k) if n<=1 then 1; elif n=0 or n=k then 0; else A(n-k,k) ; end if;
end proc:
seq(seq(A051168(n,k),k=0..n),n=0..10) ; # R. J. Mathar, Mar 29 2011

Table[If[n===0,1,1/n Plus@@(MoebiusMu[ # ]Binomial[n/#,k/# ]&/@ Divisors[GCD[n,k]])],{n,0,12},{k,0,n}] (* Wouter Meeussen, Jul 20 2008 *)

{T(n, k) = local(A, ps, c); if( k<0 || k>n, 0, if( n==0 && k==0, 1, A = x * O(x^n) + y * O(y^n); ps = 1 - x - y + A; for( m=1, n, for( i=0, m, c = polcoeff( polcoeff(ps, i, x), m-i, y); if( m==n && i==k, break(2), ps *= (1 -y^(m-i) * x^i + A)^c))); -c))} /* Michael Somos, Jul 03 2004 */

T(n,k) = if (n==0, 1, (1/n) * sumdiv(gcd(n,k), d, moebius(d) * binomial(n/d,k/d)));
tabl(nn) = for (n=0, nn, for (k=0, n, print1(T(n, k), ", ")); print); \\ Michel Marcus, May 16 2018

T(h, k) = 1 for (h, k) in {(0, 0), (1, 0), (1, 1)}; T(h, k) = 0 if h >= 2 and k = 0 or k = h. Otherwise, T(h, k) = (1/h)*(C(h, k)-S(h, k)), where S(h, k) = Sum_{d <= 2, d|h, d|k} (h/d)*T(h/d, k/d).
1 - x - y = Product_{i,j} (1 - x^i * y^j)^T(i+j, j) where i >= 0, j >= 0 are not both zero. - Michael Somos, Jul 03 2004
The prime rows are given by (1+x)^p/p with noninteger coefficients rounded to zero. E.g., for h = 2 below, (1 + x)^2/2 = (1 + 2*x + x^2)/2 = 0.5 + x + 0.5*x^2 gives (0,1,0). - Tom Copeland, Oct 21 2014
T(n,k) = (1/n) * Sum_{d | gcd(n,k)} mu(d) * binomial(n/d, k/d), for n > 0. - Andrew Howroyd, Mar 26 2017
From Petros Hadjicostas, Jun 16 2019: (Start)
O.g.f. for column k >= 1: (x^k/k) * Sum_{d|k} mu(d)/(1 - x^d)^(k/d).
Bivariate o.g.f.: Sum_{n,k >= 0} T(n, k)*x^n*y^k = 1 - Sum_{d >= 1} (mu(d)/d) *log(1 - x^d * (1 + y^d)).
(End)

A054535 Square array giving Ramanujan sum T(n,k) = c_n(k) = Sum_{m=1..n, (m,n)=1} exp(2 Pi i m k / n), read by antidiagonals upwards (n >= 1, k >= 1).

Original entry on oeis.org

1, -1, 1, -1, 1, 1, 0, -1, -1, 1, -1, -2, 2, 1, 1, 1, -1, 0, -1, -1, 1, -1, -1, -1, 2, -1, 1, 1, 0, -1, -2, -1, 0, 2, -1, 1, 0, 0, -1, -1, 4, -2, -1, 1, 1, 1, 0, 0, -1, 1, -1, 0, -1, -1, 1, -1, -1, -3, -4, -1, 2, -1, 2, 2, 1, 1, 0, -1, 1, 0, 0, -1, 1, -1, 0, -1, -1, 1, -1, 2, -1, -1, 0, 0, 6, -1, -1, -2, -1, 1, 1, 1, -1

Offset: 1

N. J. A. Sloane, Apr 09 2000

Replace the first column in A077049 with any k-th column in A177121 to get a new array. Then the matrix inverse of the new array will have the k-th column of A054535 (this array) as its first column. - Mats Granvik, May 03 2010
We have T(n, k) = c_n(k) = Sum_{m=1..n, (m,n)=1} exp(2 Pi i m k / n) and
A054534(n, k) = c_k(n) = Sum_{m=1..k, (m,k)=1} exp(2 Pi i m n / k). That is, the current array is the transpose of array A054534. Dirichlet g.f.'s for these two arrays are given below by R. J. Mathar and  Mats Granvik. - Petros Hadjicostas, Jul 27 2019

			Square array T(n,k) = c_n(k) (with rows n >= 1 and columns k >= 1) starts as follows:
   1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1, ...
  -1,  1, -1,  1, -1,  1, -1,  1, -1,  1, -1,  1, -1, ...
  -1, -1,  2, -1, -1,  2, -1, -1,  2, -1, -1,  2, -1, ...
   0, -2,  0,  2,  0, -2,  0,  2,  0, -2,  0,  2,  0, ...
  -1, -1, -1, -1,  4, -1, -1, -1, -1,  4, -1, -1, -1, ...
   1, -1, -2, -1,  1,  2,  1, -1, -2, -1,  1,  2,  1, ...
  -1, -1, -1, -1, -1, -1,  6, -1, -1, -1, -1, -1, -1, ...
   0,  0,  0, -4,  0,  0,  0,  4,  0,  0,  0, -4,  0, ...
   ... [example edited by _Petros Hadjicostas_, Jul 27 2019]

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, page 160.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. Fifth ed., Oxford Science Publications, Clarendon Press, Oxford, 2003.
E. C. Titchmarsh and D. R. Heath-Brown, The theory of the Riemann zeta-function, 2nd ed., 1986.

Robert Israel, Table of n, a(n) for n = 1..10011 (T(n,k) for n+k <= 142).
Tom M. Apostol, Arithmetical properties of generalized Ramanujan sums, Pacific J. Math. 41 (1972), 281-293.
Eckford Cohen, A class of arithmetic functions, Proc. Natl. Acad. Sci. USA 41 (1955), 939-944.
A. Elashvili, M. Jibladze, and D. Pataraia, Combinatorics of necklaces and "Hermite reciprocity", J. Algebraic Combin. 10 (1999), 173-188.
M. L. Fredman, A symmetry relationship for a class of partitions, J. Combinatorial Theory Ser. A 18 (1975), 199-202.
Emiliano Gagliardo, Le funzioni simmetriche semplici delle radici n-esime primitive dell'unità, Bollettino dell'Unione Matematica Italiana Serie 3, 8(3) (1953), 269-273.
Otto Hölder, Zur Theorie der Kreisteilungsgleichung K_m(x)=0, Prace mat.-fiz. 43 (1936), 13-23.
Peter H. van der Kamp, On the Fourier transform of the greatest common divisor, Integers 13 (2013), #A24. [See Section 3 for historical remarks.]
J. C. Kluyver, Some formulae concerning the integers less than n and prime to n, in: KNAW, Proceedings, 9 I, 1906, Amsterdam, 1906, pp. 408-414; see p. 410.
C. A. Nicol, On restricted partitions and a generalization of the Euler phi number and the Moebius function, Proc. Natl. Acad. Sci. USA 39(9) (1953), 963-968.
C. A. Nicol and H. S. Vandiver, A von Sterneck arithmetical function and restricted partitions with respect to a modulus, Proc. Natl. Acad. Sci. USA 40(9) (1954), 825-835.
K. G. Ramanathan, Some applications of Ramanujan's trigonometrical sum C_m(n), Proc. Indian Acad. Sci., Sect. A 20 (1944), 62-69.
Srinivasa Ramanujan, On certain trigonometric sums and their applications in the theory of numbers, Trans. Camb. Phil. Soc. 22 (1918), 259-276.
R. D. von Sterneck, Ein Analogon zur additiven Zahlentheorie, Sitzungsber. Akad. Wiss. Sapientiae Math.-Naturwiss. Kl. 111 (1902), 1567-1601 (Abt. IIa). [It may not be universally accessible.]
R. D. von Sterneck, Über ein Analogon zur additiven Zahlentheorie, Jahresbericht der Deutschen Mathematiker-Vereinigung 12 (1903), 110-113. [Summary of the 1902 paper.]
Wikipedia, Ramanujan's sum.
Wikipedia, Robert Daublebsky von Sterneck der Jüngere.
Aurel Wintner, On a statistics of the Ramanujan sums, Amer. J. Math., 64(1) (1942), 106-114.

Transpose of array in A054534. Cf. A054532, A054533, A282634.

Cf. A086831=c_n(2) (2nd column), A085097=c_n(3) (3rd column), A085384=c_n(4) (4th column), A085639=c_n(5) (fifth column), A085906=c_n(6) (sixth column), A099837=c_3(n) (third row), A176742=c_4(n) (fourth row), A100051=c_6(n) (sixth row).

with(numtheory): c:=(n,k)->phi(n)*mobius(n/gcd(n,k))/phi(n/gcd(n,k)): for n from 1 to 13 do seq(c(n+1-j,j),j=1..n) od; # gives the sequence in triangular form # Emeric Deutsch
# to get the example above
for n to 8 do
    seq(c(n, k), k = 1 .. 13);
end do
# Petros Hadjicostas, Jul 27 2019

nmax = 14; t[n_, k_] := EulerPhi[n]*(MoebiusMu[n / GCD[n, k]] / EulerPhi[n / GCD[n, k]]); Flatten[ Table[t[n - k + 1, k], {n, 1, nmax}, {k, 1, n}]] (* Jean-François Alcover, Nov 10 2011, after Emeric Deutsch *)
(* To get the example above in table format *)
TableForm[Table[t[n, k], {n, 1, 8}, {k, 1, 13}]]
(* Petros Hadjicostas, Jul 27 2019 *)

T(n,k) = c_n(k) = phi(n) * Moebius(n/gcd(n, k))/phi(n/gcd(n, k)). - Emeric Deutsch, Dec 23 2004 [The r.h.s. of this formula is known as the von Sterneck function, and it was introduced by him around 1900. - Petros Hadjicostas, Jul 20 2019]
Dirichlet series: Sum_{n>=1} c_n(k)/n^s = sigma_{1-s}(k)/zeta(s) where sigma is the sum-of-divisors function. Sum_{n>=1} c_k(n)/n^s = zeta(s)*Sum_{d|k} mu(k/d)*d^(1-s). [Hardy & Wright, Titchmarsh] - R. J. Mathar, Apr 01 2012 [We have sigma_{1-s}(k) = Sum_{d|k} d^{1-s} = Sum_{d|k} (k/d)^{1-s} = sigma_{s-1}(k) / k^{s-1}. - Petros Hadjicostas, Jul 27 2019]
From Mats Granvik, Oct 10 2016: (Start)
For n >= 1 and k >= 1 let
A(n,k) := if n mod k = 0 then k^r, otherwise 0;
B(n,k) := if n mod k = 0 then k/n^s, otherwise 0.
Then the Ramanujan's sum matrix equals
inverse(A).transpose(B) evaluated at s=0 and r=0.
Equals inverse(A051731).transpose(A127093).
Dirichlet g.f.: Sum_{n>=1} Sum_{k>=1} T(n,k)/(n^r*k^s) = zeta(s)*zeta(s + r - 1)/zeta(r) as in Wikipedia. (End)
T(n,k) = c_n(k) = Sum_{s | gcd(n,k)} s * Moebius(n/s). - Petros Hadjicostas, Jul 27 2019
Lambert series and a consequence: Sum_{n >= 1} c_n(k) * z^n / (1 - z^n) = Sum_{s|k} s * z^s and -Sum_{n >= 1} (c_n(k) / n) * log(1 - z^n) = Sum_{s|k} z^s for |z| < 1 (using the principal value of the logarithm). - Petros Hadjicostas, Aug 15 2019

Name edited by Petros Hadjicostas, Jul 27 2019

A054534 Square array giving Ramanujan sum T(n,k) = c_k(n) = Sum_{m=1..k, (m,k)=1} exp(2 Pi i m n / k), read by antidiagonals upwards (n >= 1, k >= 1).

Original entry on oeis.org

1, 1, -1, 1, 1, -1, 1, -1, -1, 0, 1, 1, 2, -2, -1, 1, -1, -1, 0, -1, 1, 1, 1, -1, 2, -1, -1, -1, 1, -1, 2, 0, -1, -2, -1, 0, 1, 1, -1, -2, 4, -1, -1, 0, 0, 1, -1, -1, 0, -1, 1, -1, 0, 0, 1, 1, 1, 2, 2, -1, 2, -1, -4, -3, -1, -1, 1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, 1, 1, -1, -2, -1, -1, 6, 0, 0, -1, -1, 2, -1, 1, -1, 2, 0, 4, -2, -1, 0, -3, -4, -1, 0, -1, 1

Offset: 1

N. J. A. Sloane, Apr 09 2000

The Ramanujan sum is also known as the von Sterneck arithmetic function. Robert Daublebsky von Sterneck introduced it around 1900. - Petros Hadjicostas, Jul 20 2019

T(n, k) = c_k(n) is the sum of the n-th powers of the k-th primitive roots of unity. - Petros Hadjicostas, Jul 27 2019

			Array T(n,k) (with rows n >= 1 and columns k >= 1) begins as follows:
  1, -1, -1,  0, -1,  1, -1,  0,  0,  1, -1, ...
  1,  1, -1, -2, -1, -1, -1,  0,  0, -1, -1, ...
  1, -1,  2,  0, -1, -2, -1,  0, -3,  1, -1, ...
  1,  1, -1,  2, -1, -1, -1, -4,  0, -1, -1, ...
  1, -1, -1,  0,  4,  1, -1,  0,  0, -4, -1, ...
  1,  1,  2, -2, -1,  2, -1,  0, -3, -1, -1, ...
  1, -1, -1,  0, -1,  1,  6,  0,  0,  1, -1, ...
  ...

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, page 160.
H. Rademacher, Collected Papers of Hans Rademacher, vol. II, MIT Press, 1974, p. 435.
S. Ramanujan, On Certain Trigonometrical Sums and their Applications in the Theory of Numbers, pp. 179-199 of Collected Papers of Srinivasa Ramanujan, Ed. G. H. Hardy et al., AMS Chelsea Publishing 2000.
R. D. von Sterneck, Ein Analogon zur additiven Zahlentheorie, Sitzungsber. Acad. Wiss. Sapientiae Math.-Naturwiss. Kl. 111 (1902), 1567-1601 (Abt. IIa).

Seiichi Manyama, Antidiagonals n = 1..140, flattened
Tom M. Apostol, Arithmetical properties of generalized Ramanujan sums, Pacific J. Math. 41 (1972), 281-293.
Austrian Biographical Encyclopedia from 1815 onwards, Daublebsky von Sterneck, Robert.
Eckford Cohen, A class of arithmetic functions, Proc. Natl. Acad. Sci. USA 41 (1955), 939-944.
A. Elashvili, M. Jibladze, and D. Pataraia, Combinatorics of necklaces and "Hermite reciprocity", J. Algebraic Combin. 10 (1999), 173-188.
M. L. Fredman, A symmetry relationship for a class of partitions, J. Combinatorial Theory Ser. A 18 (1975), 199-202.
Emiliano Gagliardo, Le funzioni simmetriche semplici delle radici n-esime primitive dell'unità, Bollettino dell'Unione Matematica Italiana Serie 3, 8(3) (1953), 269-273.
Otto Hölder, Zur Theorie der Kreisteilungsgleichung K_m(x)=0, Prace mat.-fiz. 43 (1936), 13-23.
Peter H. van der Kamp, On the Fourier transform of the greatest common divisor, Integers 13 (2013), #A24. [See Section 3 for historical remarks.]
C. A. Nicol, On restricted partitions and a generalization of the Euler phi number and the Moebius function, Proc. Natl. Acad. Sci. USA 39(9) (1953), 963-968.
C. A. Nicol and H. S. Vandiver, A von Sterneck arithmetical function and restricted partitions with respect to a modulus, Proc. Natl. Acad. Sci. USA 40(9) (1954), 825-835.
K. G. Ramanathan, Some applications of Ramanujan's trigonometrical sum C_m(n), Proc. Indian Acad. Sci., Sect. A 20 (1944), 62-69.
Srinivasa Ramanujan, On certain trigonometric sums and their applications in the theory of numbers, Trans. Camb. Phil. Soc. 22 (1918), 259-276.
M. V. Subbarao, The Brauer-Rademacher identity, Amer. Math. Monthly 72 (1965), 135-138.
Wikipedia, Ramanujan's sum.
Wikipedia, Robert Daublebsky von Sterneck der Jüngere.
Aurel Wintner, On a statistics of the Ramanujan sums, Amer. J. Math., 64(1) (1942), 106-114.

Cf. A000010, A033999, A054532, A054533, A054535, A062570, A085097, A058384, A085639, A085906, A099837, A100051, A176742, A282634.

nmax = 14; mu[n_Integer] = MoebiusMu[n]; mu[] = 0; t[n, k_] := Total[ #*mu[k/#]& /@ Divisors[n]]; Flatten[ Table[ t[n-k+1, k], {n, 1, nmax}, {k, 1, n}]] (* Jean-François Alcover, Nov 14 2011, after Pari *)
TableForm[Table[t[n, k], {n, 1, 7}, {k, 1, 11}]] (* to print a table like the one in the example - Petros Hadjicostas, Jul 27 2019 *)

{T(n, k) = if( n<1 || k<1, 0, sumdiv( n, d, if( k%d==0, d * moebius(k / d))))} /* Michael Somos, Dec 05 2002 */

{T(n, k) = if( n<1 || k<1, 0, polsym( polcyclo( k), n) [n + 1])} /* Michael Somos, Mar 21 2011 */

/*To get an array like in the example above using Michael Somos' programs:*/
{for (n=1, 20, for (k=1, 40, print1(T(n,k), ","); ); print(); ); } /* Petros Hadjicostas, Jul 27 2019 */

T(n, 1) = c_1(n) = 1. T(n, 2) = c_2(n) = A033999(n). T(n, 3) = c_3(n) = A099837(n) if n>1. T(n, 4) = c_4(n) = A176742(n) if n>1. T(n, 6) = c_6(n) = A100051(n) if n>1. - Michael Somos, Mar 21 2011
T(1, n) = c_n(1) = A008683(n). T(2, n) = c_n(2) = A086831(n). T(3, n) = c_n(3) = A085097(n). T(4, n) = c_n(4) = A085384(n). T(5, n) = c_n(5) = A085639(n). T(6, n) = c_n(6) = A085906(n). - Michael Somos, Mar 21 2011
T(n, n) = T(k * n, n) = A000010(n), T(n, 2*n) = -A062570(n). - Michael Somos, Mar 21 2011
Lambert series and a consequence: Sum_{k >= 1} c_k(n) * z^k / (1 - z^k) = Sum_{s|n} s * z^s and -Sum_{k >= 1} (c_k(n) / k) * log(1 - z^k) = Sum_{s|n} z^s for |z| < 1 (using the principal value of the logarithm). - Petros Hadjicostas, Aug 15 2019

A054532 Ramanujan sum T(n, k) = c_k(n) = Sum_{m=1..k, (m,k)=1} exp(2Piimn / k), triangular array read by rows for n >= 1 and 1 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, -1, 2, 1, 1, -1, 2, 1, -1, -1, 0, 4, 1, 1, 2, -2, -1, 2, 1, -1, -1, 0, -1, 1, 6, 1, 1, -1, 2, -1, -1, -1, 4, 1, -1, 2, 0, -1, -2, -1, 0, 6, 1, 1, -1, -2, 4, -1, -1, 0, 0, 4, 1, -1, -1, 0, -1, 1, -1, 0, 0, 1, 10, 1, 1, 2, 2, -1, 2, -1, -4, -3, -1, -1, 4, 1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, 12, 1

Offset: 1

N. J. A. Sloane, Apr 09 2000

T(n, k) = c_k(n) = sum of the n-th powers of the k-th primitive roots of unity. - Petros Hadjicostas, Jul 27 2019

			Triangle T(n,k) (with rows n >= 1 and columns k >= 1) begins as follows:
  1;
  1,  1;
  1, -1,  2;
  1,  1, -1,  2;
  1, -1, -1,  0,  4;
  1,  1,  2, -2, -1,  2;
  1, -1, -1,  0, -1,  1,  6;
  1,  1, -1,  2, -1, -1, -1, 4;
  1, -1,  2,  0, -1, -2, -1, 0, 6;
  ...

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, page 160.

T. D. Noe, Rows n=1..50 of triangle, flattened
Tom M. Apostol, Arithmetical properties of generalized Ramanujan sums, Pacific J. Math. 41 (1972), 281-293.
Eckford Cohen, A class of arithmetic functions, Proc. Natl. Acad. Sci. USA 41 (1955), 939-944.
A. Elashvili, M. Jibladze, and D. Pataraia, Combinatorics of necklaces and "Hermite reciprocity", J. Algebraic Combin. 10 (1999), 173-188.
M. L. Fredman, A symmetry relationship for a class of partitions, J. Combinatorial Theory Ser. A 18 (1975), 199-202.
H. G. Gadiyar and R. Padma, Linking the circle and the sieve: Ramanujan-Fourier series, arXiv:math/0601574 [math.NT], 2006.
Emiliano Gagliardo, Le funzioni simmetriche semplici delle radici n-esime primitive dell'unità, Bollettino dell'Unione Matematica Italiana Serie 3, 8(3) (1953), 269-273.
Otto Hölder, Zur Theorie der Kreisteilungsgleichung K_m(x)=0, Prace mat.-fiz. 43 (1936), 13-23.
Peter H. van der Kamp, On the Fourier transform of the greatest common divisor, Integers 13 (2013), #A24. [See Section 3 for historical remarks.]
J. C. Kluyver, Some formulae concerning the integers less than n and prime to n, in: KNAW, Proceedings, 9 I, 1906, Amsterdam, 1906, pp. 408-414; see p. 410.
P. Moree and H. Hommerson, Value distribution of Ramanujan sums and of cyclotomic polynomial coefficients, arXiv:math/0307352 [math.NT], 2003.
K. Motose, Ramanujan's sums and cyclotomic polynomials, Math. J. Okayama U. 47, no 1, (2005), Article 5.
C. A. Nicol, On restricted partitions and a generalization of the Euler phi number and the Moebius function, Proc. Natl. Acad. Sci. USA 39(9) (1953), 963-968.
C. A. Nicol and H. S. Vandiver, A von Sterneck arithmetical function and restricted partitions with respect to a modulus, Proc. Natl. Acad. Sci. USA 40(9) (1954), 825-835.
K. G. Ramanathan, Some applications of Ramanujan's trigonometrical sum C_m(n), Proc. Indian Acad. Sci., Sect. A 20 (1944), 62-69.
Srinivasa Ramanujan, On certain trigonometric sums and their applications in the theory of numbers, Trans. Camb. Phil. Soc. 22 (1918), 259-276.
R. D. von Sterneck, Ein Analogon zur additiven Zahlentheorie, Sitzungsber. Akad. Wiss. Sapientiae Math.-Naturwiss. Kl. 111 (1902), 1567-1601 (Abt. IIa). [It may not be universally accessible.]
R. D. von Sterneck, Über ein Analogon zur additiven Zahlentheorie, Jahresbericht der Deutschen Mathematiker-Vereinigung 12 (1903), 110-113. [Summary of the 1902 paper.]
Wikipedia, Ramanujan's sum.
Wikipedia, Robert Daublebsky von Sterneck der Jüngere.
Aurel Wintner, On a statistics of the Ramanujan sums, Amer. J. Math., 64(1) (1942), 106-114.

Cf. A054533, A054534, A054535, A282634.

t[n_, k_] := Sum[ c = Exp[2*Pi*I*m*(n/k)]; If[ GCD[m, k] == 1, c, 0], {m, 1, k}] // FullSimplify; Flatten[ Table[ t[n, k], {n, 1, 15}, {k, 1, n}]] (* Jean-François Alcover, Mar 15 2012 *)
(* to get the triangle in the example *)
TableForm[Table[t[n, k], {n, 1, 9}, {k, 1, n}]]
(* Petros Hadjicostas, Jul 27 2019 *)

T(n, k) = c_k(n) = Sum_{m=1..k, (m,k)=1} cos(2*Pi*m*n / k) = mu(k/gcd(k,n)) * phi(k) / phi(k/gcd(k,n)) = Sum_{d | gcd(k,n)} mu(k/d) * d. (All formulas were proved by Kluyver (1906, p. 410).) - Petros Hadjicostas, Aug 20 2019

A086831 Ramanujan sum c_n(2).

Original entry on oeis.org

1, 1, -1, -2, -1, -1, -1, 0, 0, -1, -1, 2, -1, -1, 1, 0, -1, 0, -1, 2, 1, -1, -1, 0, 0, -1, 0, 2, -1, 1, -1, 0, 1, -1, 1, 0, -1, -1, 1, 0, -1, 1, -1, 2, 0, -1, -1, 0, 0, 0, 1, 2, -1, 0, 1, 0, 1, -1, -1, -2, -1, -1, 0, 0, 1, 1, -1, 2, 1, 1, -1, 0, -1, -1, 0, 2, 1, 1, -1, 0, 0, -1, -1, -2, 1, -1, 1, 0, -1, 0, 1, 2, 1, -1, 1, 0, -1, 0, 0, 0, -1, 1, -1, 0, -1

Offset: 1

Yuval Dekel (dekelyuval(AT)hotmail.com), Aug 07 2003

Mobius transform of 1,2,0,0,0,0,... (A130779). - R. J. Mathar, Mar 24 2012

			a(4) = -2 because the primitive fourth roots of unity are i and -i.  We sum their squares to get i^2 + (-i)^2 = -1 + -1 = -2. - _Geoffrey Critzer_, Dec 30 2015

Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976.
E. C. Titchmarsh and D. R. Heath-Brown, The theory of the Riemann zeta-function, 2nd edn., 1986.

Antti Karttunen, Table of n, a(n) for n = 1..65537
Tom M. Apostol, Arithmetical properties of generalized Ramanujan sums, Pacific J. Math. 41 (1972), 281-293.
Eckford Cohen, A class of arithmetic functions, Proc. Natl. Acad. Sci. USA 41 (1955), 939-944.
A. Elashvili, M. Jibladze, and D. Pataraia, Combinatorics of necklaces and "Hermite reciprocity", J. Algebraic Combin. 10 (1999), 173-188.
Michael L. Fredman, A symmetry relationship for a class of partitions, J. Combinatorial Theory Ser. A 18 (1975), 199-202.
Otto Hölder, Zur Theorie der Kreisteilungsgleichung K_m(x)=0, Prace mat.-fiz. 43 (1936), 13-23.
Charles A. Nicol, On restricted partitions and a generalization of the Euler phi number and the Moebius function, Proc. Natl. Acad. Sci. USA 39(9) (1953), 963-968.
Charles A. Nicol and H. S. Vandiver, A von Sterneck arithmetical function and restricted partitions with respect to a modulus, Proc. Natl. Acad. Sci. USA 40(9) (1954), 825-835.
K. G. Ramanathan, Some applications of Ramanujan's trigonometrical sum C_m(n), Proc. Indian Acad. Sci., Sect. A 20 (1944), 62-69.
Srinivasa Ramanujan, On certain trigonometric sums and their applications in the theory of numbers, Trans. Camb. Phil. Soc. 22 (1918), 259-276.
Wikipedia, Ramanujan's sum.
Aurel Wintner, On a statistics of the Ramanujan sums, Amer. J. Math., 64(1) (1942), 106-114.

Cf. A000010, A008683, A054532, A054533, A054534, A054535.

Cf. A085097, A085384, A085639, A085906 for Ramanujan sums c_n(3), c_n(4), c_n(5), c_n(6).

with(numtheory):a:=n->phi(n)*mobius(n/gcd(n,2))/phi(n/gcd(n,2)): seq(a(n),n=1..130); # Emeric Deutsch, Dec 23 2004

f[list_, i_] := list[[i]]; nn = 105; a = Table[MoebiusMu[n], {n, 1, nn}]; b =Table[If[IntegerQ[2/n], n, 0], {n, 1,nn}];Table[DirichletConvolve[f[a, n], f[b, n], n, m], {m, 1, nn}] (* Geoffrey Critzer, Dec 30 2015 *)
f[p_, e_] := If[e == 1, -1, 0]; f[2, e_] := Switch[e, 1, 1, 2, -2, , 0]; a[1] = 1; a[n] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Jan 21 2024 *)

A086831(n) = (eulerphi(n)*moebius(n/gcd(n, 2))/eulerphi(n/gcd(n, 2))); \\ Antti Karttunen, Sep 27 2018

For a general k >= 1, c_n(k) = phi(n)*mu(n/gcd(n, k)) / phi(n/gcd(n, k)); so c_n(1) = mu(n) = A008683(n).
a(n) = phi(n)*mu(n/gcd(n, 2)) / phi(n/gcd(n, 2)).
Dirichlet g.f.: (1+2^(1-s))/zeta(s). [Titchmarsh eq. (1.5.4)] - R. J. Mathar, Mar 26 2011
Multiplicative with a(2) = 1, a(2^2) = -2, and a(2^e) = 0 for e >= 3, and for an odd prime p, a(p) = -1 and a(p^e) = 0 for e >= 2. - Amiram Eldar, Sep 14 2023
Sum_{k=1..n} abs(a(k)) ~ (8/Pi^2) * n. - Amiram Eldar, Jan 21 2024

Corrected and extended by Emeric Deutsch, Dec 23 2004

A085384 Ramanujan sum c_n(4).

Original entry on oeis.org

1, 1, -1, 2, -1, -1, -1, -4, 0, -1, -1, -2, -1, -1, 1, 0, -1, 0, -1, -2, 1, -1, -1, 4, 0, -1, 0, -2, -1, 1, -1, 0, 1, -1, 1, 0, -1, -1, 1, 4, -1, 1, -1, -2, 0, -1, -1, 0, 0, 0, 1, -2, -1, 0, 1, 4, 1, -1, -1, 2, -1, -1, 0, 0, 1, 1, -1, -2, 1, 1, -1, 0, -1, -1, 0, -2, 1, 1, -1, 0, 0, -1, -1, 2

Offset: 1

Yuval Dekel (dekelyuval(AT)hotmail.com), Aug 12 2003

Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976.
E. C. Titchmarsh and D. R. Heath-Brown, The Theory of the Riemann Zeta-function, 2nd ed., 1986.
R. D. von Sterneck, Ein Analogon zur additiven Zahlentheorie, Sitzungsber. Acad. Wiss. Sapientiae Math.-Naturwiss. Kl. 111 (1902), 1567-1601 (Abt. IIa).

Antti Karttunen, Table of n, a(n) for n = 1..65537
Tom M. Apostol, Arithmetical properties of generalized Ramanujan sums, Pacific J. Math. 41 (1972), 281-293.
Eckford Cohen, A class of arithmetic functions, Proc. Natl. Acad. Sci. USA 41 (1955), 939-944.
A. Elashvili, M. Jibladze, and D. Pataraia, Combinatorics of necklaces and "Hermite reciprocity", J. Algebraic Combin. 10 (1999), 173-188.
M. L. Fredman, A symmetry relationship for a class of partitions, J. Combinatorial Theory Ser. A 18 (1975), 199-202.
Otto Hölder, Zur Theorie der Kreisteilungsgleichung K_m(x)=0, Prace mat.-fiz. 43 (1936), 13-23.
J. C. Kluyver, Some formulae concerning the integers less than n and prime to n, in: KNAW, Proceedings, 9 I, 1906, Amsterdam, 1906, pp. 408-414; see p. 410.
C. A. Nicol, On restricted partitions and a generalization of the Euler phi number and the Moebius function, Proc. Natl. Acad. Sci. USA 39(9) (1953), 963-968.
C. A. Nicol and H. S. Vandiver, A von Sterneck arithmetical function and restricted partitions with respect to a modulus, Proc. Natl. Acad. Sci. USA 40(9) (1954), 825-835.
K. G. Ramanathan, Some applications of Ramanujan's trigonometrical sum C_m(n), Proc. Indian Acad. Sci., Sect. A 20 (1944), 62-69.
Srinivasa Ramanujan, On certain trigonometric sums and their applications in the theory of numbers, Trans. Camb. Phil. Soc. 22 (1918), 259-276.
Wikipedia, Ramanujan's sum.
Aurel Wintner, On a statistics of the Ramanujan sums, Amer. J. Math., 64(1) (1942), 106-114.

Cf. A000010, A008683, A054532, A054533, A054534, A054535, A085097, A086831, A085639.

a[n_] := EulerPhi[n] * MoebiusMu[n/GCD[n, 4]] / EulerPhi[n/GCD[n, 4]]; Table[ a[n], {n, 1, 105}]
f[p_, e_] := If[e == 1, -1, 0]; f[2, e_] := Switch[e, 1, 1, 2, 2, 3, -4, , 0]; a[1] = 1; a[n] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Jan 21 2024 *)

a(n)=eulerphi(n)*moebius(n/gcd(n,4))/eulerphi(n/gcd(n,4))

a(n) = phi(n)*mu(n/gcd(n, 4)) / phi(n/gcd(n, 4)).
Dirichlet g.f.: (1+2^(1-s)+4^(1-s))/zeta(s). [Titchmarsh] - R. J. Mathar, Mar 26 2011
Lambert series and a consequence: Sum_{n >= 1} c_n(4) * z^n / (1 - z^n) = Sum_{s|4} s * z^s and -Sum_{n >= 1} (c_n(4) / n) * log(1 - z^n) = Sum_{s|4} z^s for |z| < 1 (using the principal value of the logarithm). - Petros Hadjicostas, Aug 24 2019
From Amiram Eldar, Jan 21 2024: (Start)
Multiplicative with a(2) = 1, a(2^2) = 2, a(2^3) = -4, and a(2^e) = 0 for e >= 4, and for an odd prime p, a(p) = -1, and a(p^e) = 0 for e >= 2.
Sum_{k=1..n} abs(a(k)) ~ (10/Pi^2) * n. (End)

More terms from Robert G. Wilson v and Benoit Cloitre, Aug 17 2003

A085639 Ramanujan sum c_n(5).

Original entry on oeis.org

1, -1, -1, 0, 4, 1, -1, 0, 0, -4, -1, 0, -1, 1, -4, 0, -1, 0, -1, 0, 1, 1, -1, 0, -5, 1, 0, 0, -1, 4, -1, 0, 1, 1, -4, 0, -1, 1, 1, 0, -1, -1, -1, 0, 0, 1, -1, 0, 0, 5, 1, 0, -1, 0, -4, 0, 1, 1, -1, 0, -1, 1, 0, 0, -4, -1, -1, 0, 1, 4, -1, 0, -1, 1, 5, 0, 1, -1, -1, 0, 0, 1, -1, 0, -4, 1, 1, 0, -1

Offset: 1

Yuval Dekel (dekelyuval(AT)hotmail.com), Aug 15 2003

Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976.

Antti Karttunen, Table of n, a(n) for n = 1..65537
Tom M. Apostol, Arithmetical properties of generalized Ramanujan sums, Pacific J. Math. 41 (1972), 281-293.
Eckford Cohen, A class of arithmetic functions, Proc. Natl. Acad. Sci. USA 41 (1955), 939-944.
A. Elashvili, M. Jibladze, and D. Pataraia, Combinatorics of necklaces and "Hermite reciprocity", J. Algebraic Combin. 10 (1999), 173-188.
M. L. Fredman, A symmetry relationship for a class of partitions, J. Combinatorial Theory Ser. A 18 (1975), 199-202.
Emiliano Gagliardo, Le funzioni simmetriche semplici delle radici n-esime primitive dell'unità, Bollettino dell'Unione Matematica Italiana Serie 3, 8(3) (1953), 269-273.
Otto Hölder, Zur Theorie der Kreisteilungsgleichung K_m(x)=0, Prace mat.-fiz. 43 (1936), 13-23.
J. C. Kluyver, Some formulae concerning the integers less than n and prime to n, in: KNAW, Proceedings, 9 I, 1906, Amsterdam, 1906, pp. 408-414; see p. 410.
C. A. Nicol, On restricted partitions and a generalization of the Euler phi number and the Moebius function, Proc. Natl. Acad. Sci. USA 39(9) (1953), 963-968.
C. A. Nicol and H. S. Vandiver, A von Sterneck arithmetical function and restricted partitions with respect to a modulus, Proc. Natl. Acad. Sci. USA 40(9) (1954), 825-835.
K. G. Ramanathan, Some applications of Ramanujan's trigonometrical sum C_m(n), Proc. Indian Acad. Sci., Sect. A 20 (1944), 62-69.
Srinivasa Ramanujan, On certain trigonometric sums and their applications in the theory of numbers, Trans. Camb. Phil. Soc. 22 (1918), 259-276.
M. V. Subbarao, The Brauer-Rademacher identity, Amer. Math. Monthly 72 (1965), 135-138.
Peter H. van der Kamp, On the Fourier transform of the greatest common divisor, Integers 13 (2013), #A24. [See Section 3 for historical remarks.]
Wikipedia, Ramanujan's sum.
Aurel Wintner, On a statistics of the Ramanujan sums, Amer. J. Math., 64(1) (1942), 106-114.

Cf. A000010, A008683, A054532, A054533, A054534, A054535, A085384, A085906, A085097, A086831.

a[n_] := EulerPhi[n] * MoebiusMu[n/GCD[n, 5]] / EulerPhi[n/GCD[n, 5]]; Table[ a[n], {n, 1, 105}]
f[p_, e_] := If[e == 1, -1, 0]; f[5, e_] := Switch[e, 1, 4, 2, -5, , 0]; a[1] = 1; a[n] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Jan 21 2024 *)

a(n)=eulerphi(n)*moebius(n/gcd(n,5))/eulerphi(n/gcd(n,5))

a(n) = phi(n)*mu(n/gcd(n, 5)) / phi(n/gcd(n, 5)).
Dirichlet g.f.: (1+5^(1-s))/zeta(s). - R. J. Mathar, Mar 26 2011
Lambert series and a consequence: Sum_{n >= 1} c_n(5) * z^n / (1 - z^n) = z + 5*z^5 and -Sum_{n >= 1} (c_n(5) / n) * log(1 - z^n) = z + z^5 for |z| < 1 (using the principal value of the logarithm). - Petros Hadjicostas, Aug 24 2019
From Amiram Eldar, Jan 21 2024: (Start)
Multiplicative with a(5) = 4, a(5^2) = -5, and a(5^e) = 0 for e >= 3, and for a prime p != 5, a(p) = -1, and a(p^e) = 0 for e >= 2.
Sum_{k=1..n} abs(a(k)) ~ (10/Pi^2) * n. (End)

More terms from Robert G. Wilson v and Benoit Cloitre, Aug 17 2003

A282634 Recursive 2-parameter sequence allowing the Ramanujan's sum calculation.

Original entry on oeis.org

1, 1, -1, 2, -1, -1, 2, 0, -2, 0, 4, -1, -1, -1, -1, 2, 1, -1, -2, -1, 1, 6, -1, -1, -1, -1, -1, -1, 4, 0, 0, 0, -4, 0, 0, 0, 6, 0, 0, -3, 0, 0, -3, 0, 0, 4, 1, -1, 1, -1, -4, -1, 1, -1, 1, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 4, 0, 2, 0, -2, 0, -4, 0

Offset: 1

Gevorg Hmayakyan, Feb 20 2017

a(n,0) = phi(n), where phi(n) is Euler's totient function A000010(n).

a(n,1) = mu(n), where mu(n) is the Möbius function A008683(n).

			The few first rows follow:            c_n(t)
  t   0   1   2   3   4   5   6     |  t   1   2   3   4   5   6   7
n                                   |n
1     1;                            |1     1;
2     1, -1;                        |2    -1,  1;
3     2, -1, -1;                    |3    -1, -1,  2;
4     2,  0, -2,  0;                |4     0, -2,  0,  2;
5     4, -1, -1, -1, -1;            |5    -1, -1, -1, -1,  4;
6     2,  1, -1, -2, -1,  1;        |6     1, -1, -2, -1,  1,  2;
7     6, -1, -1, -1, -1, -1, -1;    |7    -1, -1, -1, -1, -1, -1,  6;
      ...                           |     ...
[Edited by _Seiichi Manyama_, Mar 05 2018]

Seiichi Manyama, Rows n=1..140 of triangle, flattened
Gevorg Hmayakyan, On The Moebius and Euler Totient Functions Calculation.
Charles A. Nicol, On Restricted Partitions and a Generalization Of The Euler Totient and The Moebius Function, PNAS 39(9) (1953), 963-968.

Cf. A000010 (phi(n)), A008683 (mu(n)), A054532, A054533, A054534, A054535, A231599.

b[n_, m_] := b[n, m] = If[n > 1, b[n - 1, m] - b[n - 1, m - n + 1], 0]
b[1, m_] := b[1, m] = If[m == 0, 1, 0]
nt[n_, t_] := Round[(n - 1)/2 - t/n]
a[n_, t_] := Sum[b[n, k*n + t], {k, 0, nt[n, t]}]
Flatten[Table[Table[a[n, m], {m, 0, n - 1}], {n, 1, 20}]]

a(n,t) = Sum(b(n, k*n + t), k=0..N(n, t)), where b(n,k) = A231599(n-1,k) and N(n,t) = [(n - 1)/2 - t/n].
a(n,t) = c_n(t) for t >= 1, where c_n(t) is a Ramanujan's sum A054533.
a(n,t) = a(n,-t)
From Seiichi Manyama, Mar 05 2018: (Start)
a(n,t) = c_n(n-t) = Sum_{d | gcd(n,n-t)} d*mu(n/d) for 0 <= t <= n-1.
So a(n,t) = Sum_{d | gcd(n,t)} d*mu(n/d) for 1 <= t <= n-1. (End)

A267632 Triangle T(n, k) read by rows: the k-th column of the n-th row lists the number of ways to select k distinct numbers (k >= 1) from [1..n] so that their sum is divisible by n.

Original entry on oeis.org

1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 2, 2, 1, 1, 1, 2, 4, 3, 1, 0, 1, 3, 5, 5, 3, 1, 1, 1, 3, 7, 9, 7, 3, 1, 0, 1, 4, 10, 14, 14, 10, 4, 1, 1, 1, 4, 12, 22, 26, 20, 12, 5, 1, 0, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 1, 1, 5, 19, 42, 66, 76, 66, 43, 19, 5, 1, 0

Offset: 1

Dimitri Papadopoulos, Jan 18 2016

Row less the last element is palindrome for n=odd or n=power of 2 where n is the row number (observation-conjecture).
From Petros Hadjicostas, Jul 13 2019: (Start)
By reading carefully the proof of Lemma 5.1 (pp. 65-66) in Barnes (1959), we see that he actually proved a general result (even though he does not state it in the lemma).
According to the definition of this sequence, for 1 <= k <= n, T(n, k) is the number of unordered sets b_1, b_2, ..., b_k of k distinct integers from 1..n such that b_1 + b_2 + ... + b_k = 0 (mod n). The proof of Lemma 5.1 in Barnes (1959) implies that T(n, k) = (1/n) * Sum_{s | gcd(n, k)} (-1)^(k - (k/s)) * phi(s) * binomial(n/s, k/s) for 1 <= k <= n.
For fixed k >= 1, the g.f. of the column (T(n, k): n >= 1) (with T(n, k) = 0 for 1 <= n < k) is (x^k/k) * Sum_{s|k} phi(s) * (-1)^(k - (k/s)) / (1 - x^s)^(k/s), which generalizes Herbert Kociemba's formula from A032801.
Barnes' (1959) formula is a special case of Theorem 4 (p. 66) in Ramanathan (1944). If R(n, k, v) is the number of unordered sets b_1, b_2, ..., b_k of k distinct integers from 1..n such that b_1 + b_2 + ... + b_k = v (mod n), then he proved that R(n, k, v) = (1/n) * Sum_{s | gcd(n,k)} (-1)^(k - (k/s)) * binomial(n/s, k/s) * C_s(v), where C_s(v) = A054535(s, v) =  Sum_{d | gcd(s,v)} d * Moebius(s/d) is Ramanujan's sum (even though it was first discovered around 1900 by the Austrian mathematician R. D. von Sterneck).
Because C_s(v = 0) = phi(s), we get Barnes' (implicit) result; i.e., R(n, k, v=0) = T(n, k) for 1 <= k <= n.
For k=2, we have R(n, k=2, v=0) = T(n, k=2) = A004526(n-1) for n >= 1. For k=3, we have R(n, k=3, v=0) = T(n, k=3) = A058212(n) for n >= 1. For k=4, we have R(n, k=4, v=0) = A032801(n) for n >= 1. For k=5, we have R(n, k=5, v=0) = T(n, k=5) = A008646(n-5) for n >= 5.
The reason we have T(2*m+1, k) = A037306(2*m+1, k) = A047996(2*m+1, k) for m >= 0 and k >= 1 is the following. When n = 2*m + 1, all divisors s of gcd(n, k) are odd. In such a case, k - (k/s) is even for all k >= 1, and thus (-1)^(k - (k/s)) = 1, and thus T(n = 2*m+1, k) = (1/n) * Sum_{s | gcd(n, k)} phi(s) * binomial(n/s, k/s) = A037306(2*m+1, k) = A047996(2*m+1, k).
By summing the products of the g.f. of column k times y^k from k = 1 to k = infinity, we get the bivariate g.f. for the array: Sum_{n, k >= 1} T(n, k)*x^n*y^k = Sum_{s >= 1} (phi(s)/s) * log((1 - x^s + (-x*y)^s)/(1 - x^s)) = -x/(1 - x) - Sum_{s >= 1} (phi(s)/s) * log(1 - x^s + (-x*y)^s).
Letting y = 1 in the above bivariate g.f., we get the g.f. of the sequence (Sum_{1 <= k <= n} T(n, k): n >= 1) is -x/(1 - x) - Sum_{s >= 1} (phi(s)/s) * log(1 - x^s + (-x)^s) = -x/(1 - x) + Sum_{m >= 0} (phi(2*m + 1)/(2*m + 1)) * log(1 - 2*x^(2*m+1)), which is the g.f. of sequence A082550. Hence, sequence A082550 consists of the row sums.
There is another important interpretation of this array T(n, k) which is related to some of the references for sequence A047996, but because the discussion is too lengthy, we omit the details.
(End)

			For n = 5, there is one way to pick one number (5), two ways to pick two numbers (1+4, 2+3), two ways to pick 3 numbers (1+4+5, 2+3+5), one way to pick 4 numbers (1+2+3+4), and one way to pick 5 numbers (1+2+3+4+5) so that their sum is divisible by 5. Therefore, T(5,1) = 1, T(5,2) = 2, T(5,3) = 2, T(5,4) = 1, and T(5,5) = 1.
Table for T(n,k) begins as follows:
n\k 1 2   3    4    5    6    7    8    9   10
1   1
2   1 0
3   1 1   1
4   1 1   1    0
5   1 2   2    1    1
6   1 2   4    3    1    0
7   1 3   5    5    3    1    1
8   1 3   7    9    7    3    1    0
9   1 4  10   14   14   10    4    1    1
10  1 4  12   22   26   20   12    5    1    0
...

Alois P. Heinz, Rows n = 1..150, flattened
Eric Stephen Barnes, The construction of perfect and extreme forms I, Acta Arith., 5 (1959); see pp. 65-66.
Michiel Kosters, The subset sum problem for finite abelian groups, J. Combin. Theory Ser. A 120 (2013), 527-530.
Jiyou Li and Daqing Wan, Counting subset sums of finite abelian groups, J. Combin. Theory Ser. A 119 (2012), 170-182; see pp. 171-172.
K. G. Ramanathan, Some applications of Ramanujan's trigonometrical sum C_m(n), Proc. Indian Acad. Sci., Sect. A 20 (1944), 62-69; see p. 66.
R. D. von Sterneck, Ein Analogon zur additiven Zahlentheorie, Sitzungsber. Akad. Wiss. Sapientiae Math.-Naturwiss. Kl. 111 (1902), 1567-1601 (Abt. IIa).
R. D. von Sterneck, Über ein Analogon zur additiven Zahlentheorie, Jahresbericht der Deutschen Mathematiker-Vereinigung 12 (1903), 110-113.

Cf. A004526, A032801, A037306, A047996, A054532, A054533, A054534, A054535, A058212, A063776, A082550 (row sums), A309122.

A267632 := proc(n,k)
    local a,msel,p;
    a := 0 ;
    for msel in combinat[choose](n,k) do
        if modp(add(p,p=msel),n) = 0 then
            a := a+1 ;
        end if;
    end do:
    a;
end proc: # R. J. Mathar, May 15 2016
# second Maple program:
b:= proc(n, m, s) option remember; expand(`if`(n=0,
      `if`(s=0, 1, 0), b(n-1, m, s)+x*b(n-1, m, irem(s+n, m))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n$2, 0)):
seq(T(n), n=1..14);  # Alois P. Heinz, Aug 27 2018

f[k_, n_] :=  Length[Select[Select[Subsets[Range[n]], Length[#] == k &], IntegerQ[Total[#]/n] &]];MatrixForm[Table[{n, Table[f[k, n], {k, n}]}, {n, 10}]] (* Dimitri Papadopoulos, Jan 18 2016 *)

T(2n+1, k) = A037306(2n+1, k) = A047996(2n+1, k).
From Petros Hadjicostas, Jul 13 2019: (Start)
T(n, k) = (1/n) * Sum_{s | gcd(n, k)} (-1)^(k - (k/s)) * phi(s) * binomial(n/s, k/s) for 1 <= k <= n.
G.f. for column k >= 1: (x^k/k) * Sum_{s|k} phi(s) * (-1)^(k - (k/s)) / (1 - x^s)^(k/s).
Bivariate g.f.: Sum_{n, k >= 1} T(n, k)*x^n*y^k = -x/(1 - x) - Sum_{s >= 1} (phi(s)/s) * log(1 - x^s + (-x*y)^s).
(End)
Sum_{k=1..n} k * T(n,k) = A309122(n). - Alois P. Heinz, Jul 13 2019

A032801 Number of unordered sets a, b, c, d of distinct integers from 1..n such that a+b+c+d = 0 (mod n).

Original entry on oeis.org

0, 0, 0, 0, 1, 3, 5, 9, 14, 22, 30, 42, 55, 73, 91, 115, 140, 172, 204, 244, 285, 335, 385, 445, 506, 578, 650, 734, 819, 917, 1015, 1127, 1240, 1368, 1496, 1640, 1785, 1947, 2109, 2289, 2470, 2670, 2870, 3090, 3311, 3553, 3795, 4059, 4324, 4612, 4900, 5212, 5525

Offset: 1

N. J. A. Sloane

From Petros Hadjicostas, Jul 12 2019: (Start)
By reading carefully the proof of Lemma 5.1 (pp. 65-66) in Barnes (1959), we see that he actually proved a general result (even though he does not state it in the lemma). For 1 <= k <= n, let T(n, k) be the number of unordered sets b_1, b_2, ..., b_k of k distinct integers from 1..n such that b_1 + b_2 + ... + b_k = 0 (mod n). The proof of Lemma 5.1 in the paper implies that T(n, k) = (1/n) * Sum_{s | gcd(n, k)} (-1)^(k - (k/s)) * phi(s) * binomial(n/s, k/s).
For fixed k >= 1, the g.f. of the sequence (T(n, k): n >= 1) (with T(n, k) = 0 for 1 <= n < k) is (x^k/k) * Sum_{s|k} phi(s) * (-1)^(k - (k/s)) / (1 - x^s)^(k/s).
For k = 4, we get T(n, k=4) = (1/n) * Sum_{d | gcd(n, 4)} (-1)^(4/s) * phi(d) * binomial(n/d, 4/d), which agrees with Barnes' 3-part formula in Lemma 5.1 and with the formula in N. J. A. Sloane's Maple program below. It also agrees with Colin Barker's formula below.
For k = 4, the g.f. is (x^4/4) * Sum_{s|4} phi(s) * (-1)^(4/s) /(1 - x^s)^(4/s), which agrees with Herbert Kociemba's g.f. below.
Barnes' (1959) formula is a special case of Theorem 4 (p. 66) in Ramanathan (1944). If R(n, k, v) is the number of unordered sets b_1, b_2, ..., b_k of k distinct integers from 1..n such that b_1 + b_2 + ... + b_k = v (mod n), then he proved that R(n, k, v) = (1/n) * Sum_{s | gcd(n,k)} (-1)^(k - (k/s)) * binomial(n/s, k/s) * C_s(v), where C_s(v) = A054533(s, v) is Ramanujan's sum (even though it was discovered first around 1900 by the Austrian mathematician R. D. von Sterneck).
Because C_s(v = 0) = phi(s), we get Barnes' (implicit) result; i.e., R(n, k, v=0) = T(n, k) and a(n) = R(n, k=4, v=0) = T(n, k=4).
For k=2, we have R(n, k=2, v=0) = T(n, k=2) = A004526(n-1) for n >= 1. For k=3, we have R(n, k=3, v=0) = T(n, k=3) = A058212(n) for n >= 1. For k=5, we have R(n, k=5, v=0) = T(n, k=5) = A008646(n-5) for n >= 5.
(End)
Von Sterneck (1902, 1903) dealt with this problem. In his notation, we need to find (n)i, the number of integer solutions of the congruence n = x_1 + ... + x_i (mod M) such that 0 <= x_1 < x_2 < ... < x_i < M, where (his n) = 0, (his M) = (our n), and (his i) = 4. He gave several formulas for solving this problem for various cases of his M (M = prime, M = product of two primes, M = power of 2, etc.). - _Petros Hadjicostas, Aug 20 2019

E. V. McLaughlin, Numbers of factorizations in non-unique factorial domains, Senior Thesis, Allegeny College, Meadville, PA, April 2004.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Eric Stephen Barnes, The construction of perfect and extreme forms I, Acta Arith., 5 (1959); see pp. 65-66.
David Broadhurst and Xavier Roulleau, Number of partitions of modular integers, arXiv:2502.19523 [math.NT], 2025. See pp. 4, 14, 19.
K. G. Ramanathan, Some applications of Ramanujan's trigonometrical sum C_m(n), Proc. Indian Acad. Sci., Sect. A 20 (1944), 62-69; see p. 66.
R. D. von Sterneck, Ein Analogon zur additiven Zahlentheorie, Sitzungsber. Akad. Wiss. Sapientiae Math.-Naturwiss. Kl. 111 (1902), 1567-1601 (Abt. IIa). [Accessible only in the USA through the HathiTrust Digital Library.]
R. D. von Sterneck, Über ein Analogon zur additiven Zahlentheorie, Jahresbericht der Deutschen Mathematiker-Vereinigung 12 (1903), 110-113. [This is a summary of the 1902 paper.]
Index entries for linear recurrences with constant coefficients, signature (2,0,-2,2,-2,0,2,-1).

Cf. A001399, A001400, A004526, A008646, A054533, A058212, A008610.

Column k=4 of A267632.

f := n-> if n mod 2 <> 0 then (n-1)*(n-2)*(n-3)/24 elif n mod 4 = 0 then (n-4)*(n^2-2*n+6)/24 else (n-2)*(n^2-4*n+6)/24; fi;

CoefficientList[Series[(x^3 / 4) (1 / (1 - x)^4 + 1 / (1 - x^2)^2 - 2 / (1 - x^4)), {x, 0, 60}],x] (* Vincenzo Librandi, Jul 13 2019 *)

G.f.: x^5*(1+x-x^2+x^3)/((-1+x)^4*(1+x)^2*(1+x^2)). - Herbert Kociemba, Oct 22 2016
a(n) = (-6 * (4 + 2*(-1)^n + (-i)^n + i^n) + (25 + 3*(-1)^n)*n - 12*n^2 + 2*n^3)/48, where i = sqrt(-1). - Colin Barker, Oct 23 2016
a(n) = -A008610(-n), per formulae of Ralf Stephan (A008610) and C. Barker (above). Also, A008610(n) - a(n+4) = (1+(-1)^signum(n mod 4))/2, i.e., (1,0,0,0,1,0,0,0,...) repeating (offset 0). - Gregory Gerard Wojnar, Jul 09 2022

Offset changed by David A. Corneth, Oct 23 2016

cp's OEIS Frontend

A051168 Triangular array T(h,k) for 0 <= k <= h read by rows: T(h,k) = number of binary Lyndon words with k ones and h-k zeros.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A054535 Square array giving Ramanujan sum T(n,k) = c_n(k) = Sum_{m=1..n, (m,n)=1} exp(2 Pi i m k / n), read by antidiagonals upwards (n >= 1, k >= 1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A054534 Square array giving Ramanujan sum T(n,k) = c_k(n) = Sum_{m=1..k, (m,k)=1} exp(2 Pi i m n / k), read by antidiagonals upwards (n >= 1, k >= 1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

A054532 Ramanujan sum T(n, k) = c_k(n) = Sum_{m=1..k, (m,k)=1} exp(2*Pi*i*m*n / k), triangular array read by rows for n >= 1 and 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A086831 Ramanujan sum c_n(2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A085384 Ramanujan sum c_n(4).

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

A054532 Ramanujan sum T(n, k) = c_k(n) = Sum_{m=1..k, (m,k)=1} exp(2Piimn / k), triangular array read by rows for n >= 1 and 1 <= k <= n.