Weighted Gcd-Sum Functions

László Tóth ^{1} Department of Mathematics University of Pécs Ifjúság u. 6 7624 Pécs Hungary and Institute of Mathematics, Department of Integrative Biology Universität für Bodenkultur Gregor Mendel-Straße 33 A-1180 Wien Austria

                    ltoth@gamma.ttk.pte.hu

Abstract We investigate weighted gcd-sum functions, including the alternating gcd-sum function and those having as weights the binomial coefficients and values of the Gamma function. We also consider the alternating lcm-sum function.

1 Introduction

The gcd-sum function, called also Pillai’s arithmetical function (OEIS \underline{A018804}) is defined by

P (n) := ∑_{k=1}^{n} gcd(k, n) (n ∈ ℕ := {1, 2, …}).  (1)

The function P is multiplicative and its arithmetical and analytical properties are determined by the representation

P (n) = ∑_{d|n} d ϕ(n/d) (n ∈ ℕ),  (2)

1The author gratefully acknowledges support from the Austrian Science Fund (FWF) under the project Nr. P20847-N18.

where ϕ is Euler’s function. See the survey paper [5]. Note that for every prime power p^{a} (a ∈ ℕ),

P (p^{a}) = (a + 1)p^{a} − ap^{a−1}.  (3)

Now let

P_{altern}(n) := ∑_{k=1}^{n}(−1)^{k−1} gcd(k, n) (n ∈ ℕ)  (4)

be the alternating gcd-sum function. As far as we know, the function (4) was not considered before.

Furthermore, let

P_{binom}(n) := ∑_{k=1}^{n} \binom{n}{k} gcd(k, n) (n ∈ ℕ)  (5)

(OEIS \underline{A159068}), where \binom{n}{k} are the binomial coefficients. Every term of the sum (5) is a multiple of n, since gcd(k, n) = kx + ny with suitable integers x, y and k\binom{n}{k} = n\binom{n−1}{k−1} (1 ≤ k ≤ n). Note also the symmetry \binom{n}{k} gcd(k, n) = \binom{n}{n−k} gcd(n − k, n) (1 ≤ k ≤ n − 1).

More generally, consider the weighted gcd-sum functions defined by

P_{w}(n) := ∑_{k=1}^{n} w(k, n) gcd(k, n) (n ∈ ℕ),  (6)

where the weights are functions w : ℕ^{2} → ℂ.

In this paper we evaluate the alternating gcd-sum function P_{altern}(n), deduce a formula for the function P_{binom}(n) and investigate other special cases of (6). We also give a formula for the alternating lcm-sum function defined by

L_{altern}(n) := ∑_{k=1}^{n}(−1)^{k−1} lcm[k, n] (n ∈ ℕ).  (7)

Similar results can be derived for the weighted versions of certain analogs and generalizations of the gcd-sum function, see [5], but we confine ourselves to the function (6).

2 General results

We first give the following simple result.

Proposition 1. i) Let w : ℕ^{2} → ℂ be an arbitrary function. Then

P_{w}(n) = ∑_{d|n} ϕ(d) ∑_{j=1}^{n/d} w(dj, n)  (n ∈ ℕ).  (8)

ii) Assume that there is a function g : (0, 1] → ℂ such that w(k, n) = g(k/n) (1 ≤ k ≤ n) and let G(n) = ∑_{k=1}^{n} g(k/n) (n ∈ ℕ). Then

P_{w}(n) = ∑_{d|n} ϕ(d)G(n/d)  (n ∈ ℕ).  (9)

Proof. i) Using Gauss’ formula m = ∑_{d|m} ϕ(d) for m = gcd(k, n), grouping the terms of (6) and denoting k = dj we obtain at once

P_{w}(n) := ∑_{k=1}^{n} w(k, n) ∑_{d|gcd(k,n)} ϕ(d) = ∑_{d|n} ϕ(d) ∑_{j=1}^{n/d} w(dj, n).

ii) Use (8) and that

∑_{j=1}^{n/d} w(dj, n) = ∑_{j=1}^{n/d} g(dj/n) = ∑_{j=1}^{n/d} g(j/(n/d)) = G(n/d).

For w(k, n) = 1 we reobtain formula formula (2). In the next section we investigate other special cases, including those already mentioned in the Introduction.

Remark 2. Consider the function

R_{w}(n) := ∑_{\begin{matrix}k=1 \\ gcd(k,n)=1 \end{matrix}}^{n} w(k, n) (n ∈ ℕ).  (10)

Then, similar to the proof of i), now with the Möbius μ function instead of ϕ,

R_{w}(n) = ∑_{k=1}^{n} w(k, n) ∑_{d|gcd(k,n)} μ(d) = ∑_{d|n} μ(d) ∑_{j=1}^{n/d} w(dj, n).  (11)

If condition ii) is satisfied, then we have

R_{w}(n) = ∑_{d|n} μ(d)G(n/d) (n ∈ ℕ).  (12)

We will also point out some special cases of (11) and (12).

3 Special cases

3.1 Alternating gcd-sum function

Let w(k, n) = (−1)^{k−1} (k, n ∈ ℕ). Then we have the function P_{altern}(n) defined by (4).

Proposition 3. Let n ∈ ℕ and write n = 2^{a}m, where a ∈ ℕ_{0} := {0, 1, 2, …} and m ∈ ℕ is odd. Then

P_{altern}(n) = \begin{cases}n, & if n is odd (a = 0); \\ −2^{a−1}aP (m) = −\frac{a}{a+2}P (n), & if n is even (a ≥ 1). \end{cases}  (13)

Proof. Use formula (8). Here

S_{d}(n) := ∑_{j=1}^{n/d} w(dj, n) = ∑_{j=1}^{n/d}(−1)^{dj−1} = − ∑_{j=1}^{n/d}(−1)^{dj}.

If n is odd, then every divisor d of n is also odd and obtain S_{d}(n) = − ∑_{j=1}^{n/d}(−1)^{j} = 1, where n/d is odd. Hence, P_{altern}(n) = ∑_{d|n} ϕ(d) = n.

Now let n be even and let d | n. For d odd, S_{d}(n) = − ∑_{j=1}^{n/d}(−1)^{j} = 0, since n/d is even. For d even, S_{d}(n) = − ∑_{j=1}^{n/d} 1 = −n/d. We obtain that

P_{altern}(n) = − ∑_{\begin{matrix}d|n \\ d even \end{matrix}} ϕ(d)\frac{n}{d} = − ∑_{d|n} ϕ(d)\frac{n}{d} + ∑_{\begin{matrix}d|n \\ d odd \end{matrix}} ϕ(d)\frac{n}{d},

where the first sum is P (n) (cf. (2)), and the second one is

∑_{d|m} ϕ(d)\frac{2^{a}m}{d} = 2^{a}P (m).

Using (3), P (n) = P (2^{a})P (m) = 2^{a−1}(a + 2)P (m) and deduce

P_{altern}(n) = −P (n) + 2^{a}P (m) = P (m)(2^{a} − 2^{a−1}(a + 2))

= −2^{a−1}aP (m) = −\frac{a}{a + 2}P (n).

Remark 4. More generally, consider the polynomial

f_{n}(x) := ∑_{k=1}^{n} gcd(k, n)x^{k−1},  (14)

i.e., put w(k, n) = x^{k−1} (formally). Then f_{n}(1) = P (n), f_{n}(−1) = P_{altern}(n) and deduce from Proposition 1,

f_{n}(x) := (1 − x^{n}) ∑_{d|n} \frac{ϕ(d)x^{d−1}}{1 − x^{d}} .  (15)

3.2 Logarithms as weights

Let

P_{log}(n) := ∑_{k=1}^{n}(log k) gcd(k, n).  (16)

Proposition 5. For every n ∈ ℕ,

P_{log}(n) = P (n) log n + ∑_{d|n} log(d!/d^{d})ϕ(n/d).  (17)

Proof. Apply formula (8). For w(k, n) = log k,

∑_{j=1}^{n/d} w(dj, n) = ∑_{j=1}^{n/d} log(dj) = \frac{n}{d} log d + log (\frac{n}{d})!,

hence

P_{log}(n) = ∑_{d|n} ϕ(d) (\frac{n}{d} log d + log (\frac{n}{d})!) ,

and a short computation leads to (17). Remark 6. Writing the exponential form of (17),

∏_{k=1}^{n} k^{gcd(k,n)} = n^{P (n)} ∏_{d|n} (\frac{d!}{d^{d}} )^{ϕ(n/d)} .  (18)

Compare this to the known formula

∏_{\begin{matrix}k=1 \\ gcd(k,n)=1 \end{matrix}}^{n} k = n^{ϕ(n)} ∏_{d|n} (\frac{d!}{d^{d}} )^{μ(n/d)} ,  (19)

cf. [2, p. 197, Ex. 24] (OEIS \underline{A001783}).

3.3 Discrete Fourier transform of the gcd’s

Consider w(k, n) = exp(2πikr/n) (k, n ∈ ℕ), where r ∈ ℤ, and denote

P_{DFT}^{(r)}(n) := ∑_{k=1}^{n} exp(2πikr/n) gcd(k, n),  (20)

representing the discrete Fourier transform of the function f(k) = gcd(k, n) (k ∈ ℕ). Proposition 7. For every n ∈ ℕ, r ∈ ℤ,

P_{DFT}^{(r)}(n) = ∑_{d|gcd(n,r)} d ϕ(n/d).  (21)

Proof. Here exp(2πikr/n) = g(k/n) with g(x) = exp(2πirx). Using formula (9) and that

∑_{k=1}^{n} exp(2πirk/n) = \begin{cases}n, & if n | r; \\ 0, & otherwise; \end{cases}

we obtain

P_{DFT}^{(r)}(n) = ∑_{d|n,n/d|r} ϕ(d)\frac{n}{d} = ∑_{d|n,d|r} dϕ(n/d).

Remark 8. Formula (21) can be written in the form

P_{DFT}^{(r)}(n) = ∑_{d|n} dc_{n/d}(r),  (22)

where c_{n}(k) are the Ramanujan sums. Furthermore, (22) can be extended for r-even functions. See [4], [6, Prop. 2]. Note that in the present treatment we do not need properties of the Ramanujan sums and of r-even functions.

For r = 0 (more generally, in case n | r) we reobtain from (21) formula (2). For r = 1 we deduce

∑_{k=1}^{n} exp(2πik/n) gcd(k, n) = ϕ(n) (n ∈ ℕ),  (23)

which gives by writing the real and the imaginary parts, respectively,

∑_{k=1}^{n} cos(2πk/n) gcd(k, n) = ϕ(n) (n ∈ ℕ),  (24)

∑_{k=1}^{n} sin(2πk/n) gcd(k, n) = 0 (n ∈ ℕ),  (25)

similar relations being valid for gcd(n, r) = 1.

Formulae (23), (24), (25) were pointed out in [4, Ex. 3].

3.4 Binomial coefficients as weights

Let w(k, n) = \binom{n}{k} (k, n ∈ ℕ). Then we have the function P_{binom}(n) defined by (5).

Proposition 9. For every n ∈ ℕ,

P_{binom}(n) = 2^{n} ∑_{d|n} \frac{ϕ(d)}{d} ∑_{ℓ=1}^{d}(−1)^{ℓ} cos^{n}(ℓπ/d) − n.  (26)

Proof. Let ε_{r}^{j} = exp(2πij/r) (1 ≤ j ≤ r) denote the r-th roots of unity. Using the known identity

∑_{k=0}^{⌊n/r⌋} \binom{n}{kr} = \frac{1}{r} ∑_{j=1}^{r}(1 + ε_{r}^{j})^{n} = \frac{2^{n}}{r} ∑_{j=1}^{r} cos^{n}(jπ/r) cos(njπ/r) (n, r ∈ ℕ), (27)

cf. [1, p. 84], and applying (8) we deduce

P_{binom}(n) = ∑_{d|n} ϕ(d) ∑_{j=1}^{n/d} \binom{n}{dj} = ∑_{d|n} ϕ(d) (\frac{2^{n}}{d} ∑_{ℓ=1}^{d} cos^{n}(ℓπ/d) cos(nℓπ/d) − 1)

= 2^{n} ∑_{d|n} \frac{ϕ(d)}{d} ∑_{ℓ=1}^{d}(−1)^{ℓ} cos^{n}(ℓπ/d) − ∑_{d|n} ϕ(d),

giving (26).

Note that (11) and (27) lead to the following formula for the sequence OEIS \underline{A056188}:

R_{binom}(n) := ∑_{\begin{matrix}k=1 \\ gcd(k,n)=1 \end{matrix}}^{n} \binom{n}{k} = 2^{n} ∑_{d|n} \frac{μ(d)}{d} ∑_{ℓ=1}^{d}(−1)^{ℓ} cos^{n}(ℓπ/d) (n > 1).  (28)

3.5 Weights concerning the Gamma function

Now let

P_{Gamma}(n) := ∑_{k=1}^{n} log Γ (\frac{k}{n}) gcd(k, n),  (29)

where Γ is the Gamma function.

Proposition 10. For every n ∈ ℕ,

P_{Gamma}(n) = \frac{log 2π}{2} (P (n) − n) − \frac{1}{2}n log n + \frac{1}{2} ∑_{d|n} ϕ(d) log d.  (30)

Proof. This follows by (9) and by

∏_{k=1}^{n} Γ (\frac{k}{n}) = (2π)^{(n−1)/2}n^{−1/2}, (n ∈ ℕ),

which is a consequence of Gauss’ multiplication formula.

Remark 11. (30) can be written also as

P_{Gamma}(n) = \frac{log 2π}{2} (P (n) − n) − \frac{1}{2}(ϕ ∗ log)(n),  (31)

where ∗ deotes the Dirichlet convolution. Note that ϕ ∗ log = μ ∗ id ∗ log = Λ ∗ id, where id(n) = n (n ∈ ℕ) and Λ is the von Mangoldt function.

Writing the exponential form,

∏_{k=1}^{n} (Γ (\frac{k}{n}))^{gcd(k,n)} = (2π)^{(P (n)−n)/2}n^{−n/2} ∏_{d|n} d^{ϕ(d)/2}.  (32)

Compare this to the following formula given in [3]:

∏_{\begin{matrix}k=1 \\ gcd(k,n)=1 \end{matrix}}^{n} Γ (\frac{k}{n}) = \frac{(2π)^{ϕ(n)/2}}{exp(Λ(n)/2)} = \begin{cases}(2π)^{ϕ(n)/2}/\sqrt{p}, & n = p^{a} (a prime power); \\ (2π)^{ϕ(n)/2}, & otherwise. \end{cases}  (33)

3.6 Further special cases

It is possible to investigate other special cases, too. As examples we give the next ones with weights regarding, among others, the floor function ⌊.⌋, and the saw-tooth function ψ defined as ψ(x) = x − ⌊x⌋ − 1/2 for x ∈ ℝ \ ℤ and ψ(x) = 0 for x ∈ ℤ.

Proposition 12. For every n ∈ ℕ,

P_{id}(n) := ∑_{k=1}^{n} k gcd(k, n) = \frac{n}{2}(P (n) + n).  (34)

Proposition 13. For every n ∈ ℕ and α ∈ ℝ,

P_{floor}(n) := ∑_{k=1}^{n} ⌊α + \frac{k}{n}⌋ gcd(k, n) = ∑_{d|n} ϕ(d) ⌊\frac{nα}{d}⌋ .  (35)

Proposition 14. For every n, r ∈ ℕ,

P_{saw-tooth}^{(r)}(n) := ∑_{k=1}^{n} ψ(kr/n) gcd(k, n) = 0.  (36)

Proposition 15. For every n ∈ ℕ, n > 1,

P_{sin}(n) := ∑_{k=1}^{n−1}(log sin(kπ/n)) gcd(k, n) = (ϕ ∗ log)(n) − (log 2)(P (n) − n).  (37)

Proposition 16. For every n ∈ ℕ and α ∈ ℝ with α + k/n ∉ ℤ (1 ≤ k ≤ n),

P_{cot}(n) := ∑_{k=1}^{n} cot π(α + k/n) gcd(k, n) = n ∑_{d|n} \frac{ϕ(d)}{d} cot(πnα/d).  (38)

These follow from Proposition 1 using the following well-known formulae:

∑_{k=1}^{n} ⌊α + \frac{k}{n}⌋ = ⌊nα⌋ ,  (n ∈ ℕ),  (39)

∑_{k=1}^{n} ψ(kr/n) = 0 (n, r ∈ ℕ),  (40)

∏_{k=1}^{n−1} sin(kπ/n) = \frac{n}{2^{n−1}}  (n ∈ ℕ)  (41)

(for n = 1 the empty product is 1),

∑_{k=1}^{n} cot π(α + k/n) = n cot πnα (n ∈ ℕ, α ∈ ℝ, α + k/n ∉ ℤ, 1 ≤ k ≤ n).  (42)

4 The alternating lcm-sum function

Some of the previous results have counterparts for the lcm-sum function (OEIS \underline{A051193})

L(n) := ∑_{k=1}^{n} lcm[k, n] = \frac{n}{2} (1 + ∑_{d|n} dϕ(d))  (n ∈ ℕ).  (43)

We consider here the alternating lcm-sum function defined by (7) and then the analog of (18).

Let F (n) := \frac{1}{n} ∑_{d|n} dϕ(d). Note that F (n) = ∑_{k=1}^{n}(gcd(k, n))^{−1} representing the arithmetic mean of the orders of elements in the cyclic group of order n, cf. [5, p. 3]. Furthermore, let β(n) := (1 ∗ μ id)(n) = ∏_{d|n}(1 − p) and let h(n) := ∏_{k=1}^{n} k^{k} be the sequence of hyperfactorials (OEIS \underline{A002109}).

Proposition 17. Let n ∈ ℕ. If n is odd, then

L_{altern}(n) = \frac{n}{2} (1 + ∑_{d|n} dμ(d)τ(n/d)) = \frac{n}{2} (1 + ∏_{p^{a}||n}(a(1 − p) + 1)) ,  (44)

where τ is the divisor function.

If n is even of the form n = 2^{a}m, where a ≥ 1 and m ∈ ℕ is odd, then

L_{altern}(n) = 2^{a−1}m (\frac{2^{2a} − 1}{3}mF (m) − 1) = \frac{n}{2} (\frac{2^{2a} − 1}{2^{2a+1} + 1}nF (n) − 1) .  (45)

Proof. Let id_{−1}(n) = n^{−1} and 1(n) = 1 (n ∈ ℕ). We have

L_{altern}(n) = n ∑_{k=1}^{n}(−1)^{k−1}k \frac{1}{gcd(k, n)} = n ∑_{k=1}^{n}(−1)^{k−1}k ∑_{d|gcd(k,n)}(id_{−1} ∗μ)(d)

= n ∑_{d|n} β(d) ∑_{j=1}^{n/d}(−1)^{dj−1}j.

Now using that ∑_{k=1}^{n}(−1)^{k−1}k = (−1)^{n−1}⌊(n + 1)/2⌋ (n ∈ ℕ) the given formulae are obtained along the same lines with the proof of Proposition 3.

Proposition 18. For every n ∈ ℕ,

(∏_{k=1}^{n} k^{lcm[k,n]})^{1/n} = ∏_{d|n} h(n/d)^{β(d)} (∏_{d|n} d^{β(d)/d})^{n/2} (∏_{d|n} d^{β(d)/d^{2}} )^{n^{2}/2} .  (46)

Proof. Similar to the proofs of above,

∑_{k=1}^{n}(log k) lcm[k, n] = n ∑_{k=1}^{n}(k log k)\frac{1}{gcd(k, n)}

= n ∑_{k=1}^{n}(k log k) ∑_{d|gcd(k,n)}(id_{−1} ∗μ)(d) = n ∑_{d|n}(id_{−1} ∗μ)(d) ∑_{j=1}^{n/d} jd log(jd)

= n ∑_{d|n} β(d) log h(n/d) + \frac{n^{2}}{2} ∑_{d|n} β(d)\frac{log d}{d} + \frac{n^{3}}{2} ∑_{d|n} β(d)\frac{log d}{d^{2}},

equivalent to (46).

References

[1] L. Comtet, Advanced Combinatorics. The Art of Finite and Infinite Expansions, D. Reidel Publishing Co., 1974.

[2] I. Niven, H. S. Zuckerman and H. L. Montgomery, An Introduction to the Theory of Numbers, 5th ed., John Wiley & Sons, 1991.

[3] J. Sándor and L. Tóth, A remark on the gamma function, Elem. Math. 44 (1989), 73–76.

[4] W. Schramm, The Fourier transform of functions of the greatest common divisor, Integers 8 (2008), #A50.

[5] L. Tóth, A survey of gcd-sum functions, J. Integer Sequences 13 (2010), Article 109.8.1.

[6] L. Tóth and P. Haukkanen, The discrete Fourier transform of r-even functions, submit-

    ted, http://arxiv.org/abs/1009.5281v1

2010 Mathematics Subject Classification: Primary 11A25; Secondary 05A10, 33B15. Keywords: gcd-sum function, lcm-sum function, Euler’s function, Möbius function, binomial coefficient, Gamma function.

(Concerned with sequences \underline{A001783}, \underline{A002109}, \underline{A018804}, \underline{A051193}, \underline{A056188}, and \underline{A159068}.)

Received May 11 2011; revised version received July 18 2011. Published in Journal of Integer Sequences, September 5 2011.

Return to Journal of Integer Sequences home page.