Relatively Prime Sets, Divisor Sums, and Partial Sums

Prapanpong Pongsriiam Department of Mathematics, Faculty of Science Silpakorn University Ratchamankanai Rd, Nakornpathom Thailand, 73000

                     prapanpong@gmail.com

Abstract We study the functions counting the number of certain relatively prime sets. We calculate partial sums and divisor sums of these functions. We give some open questions at the end of this article.

1 Introduction

Unless stated otherwise, we let d, k, n, N be positive integers, A a nonempty finite set of positive integers, gcd (A) the greatest common divisor of the elements of A, ⌊x⌋ the greatest integer less than or equal to x, and μ the Möbius function.

A set A is said to be relatively prime if gcd (A) = 1 and is said to be relatively prime to n if gcd (A ∪ {n}) = 1. Let f (n) and Φ (n) denote, respectively, the number of relatively prime subsets of {1, 2, …, n}, and the number of nonempty subsets of {1, 2, …, n} relatively prime to n. In addition, we let D (n) = ∑_{d|n} f (d) be the divisor sum of f (n). The first 15 values of f (n), Φ (n), and D (n) are given in Table 1.

The purpose of this article is to obtain partial sums associated with f (n), Φ (n), and D (n) and use them to explain some phenomena appearing in Table 1. We will also obtain a combinatorial interpretation and a congruence property of D (n). An open problem arising from an observation on the values of Φ (n) and D (n) is also given. By way of example, the formulas of the partial sums of f (n), Φ (n), and D (n) lead to the following results: (see Corollary 5 for the proof),

lim sup_{N→∞} \frac{|∑_{n≤N} f (n) − 2^{N+1}|}{2^{\frac{N}{2}}} = 3  (1)

\begin{matrix}n & f (n) & Φ (n) & D (n) & 2^{n} \\ 1 & 1 & 1 & 1 & 2 \\ 2 & 2 & 2 & 3 & 4 \\ 3 & 5 & 6 & 6 & 8 \\ 4 & 11 & 12 & 14 & 16 \\ 5 & 26 & 30 & 27 & 32 \\ 6 & 53 & 54 & 61 & 64 \\ 7 & 116 & 126 & 117 & 128 \\ 8 & 236 & 240 & 250 & 256 \\ 9 & 488 & 504 & 494 & 512 \\ 10 & 983 & 990 & 1012 & 1024 \\ 11 & 2006 & 2046 & 2007 & 2048 \\ 12 & 4016 & 4020 & 4088 & 4096 \\ 13 & 8111 & 8190 & 8112 & 8192 \\ 14 & 16238 & 16254 & 16357 & 16384 \\ 15 & 32603 & 32730 & 32635 & 32768 \end{matrix}

Table 1: The first 15 values of f (n), Φ (n), and D (n).

lim inf_{N→∞} \frac{|∑_{n≤N} f (n) − 2^{N+1}|}{2^{\frac{N}{2}}} = 2\sqrt{2}  (2)
lim sup_{N→∞} \frac{|∑_{n≤N} Φ (n) − 2^{N+1}|}{2^{\frac{N}{2}}} = 2  (3)
lim inf_{N→∞} \frac{|∑_{n≤N} Φ (n) − 2^{N+1}|}{2^{\frac{N}{2}}} = \sqrt{2}  (4)
lim sup_{N→∞} \frac{|∑_{n≤N} D (n) − 2^{N+1}|}{2^{\frac{N}{2}}} = \sqrt{2}  (5)
lim inf_{N→∞} \frac{|∑_{n≤N} D (n) − 2^{N+1}|}{2^{\frac{N}{2}}} = 1  (6)

2 Preliminaries and Lemmas

Let E (n) = ∑_{d|n} Φ (d) be the divisor sum of Φ (n). By the definition of f (n), Φ (n), D (n) and E (n) and the results obtained by Nathanson [9], the following holds:

f (n) ≤ min{Φ (n) , D (n)} ≤ max{Φ (n) , D (n)} ≤ E (n) = 2^{n} − 1 ≤ 2^{n}.  (7)

Moreover, f (n) is asymptotic to 2^{n}. So all functions above are asymptotic to 2^{n}. In other words,

lim_{n→∞} \frac{f (n)}{2^{n}} = lim_{n→∞} \frac{Φ (n)}{2^{n}} = lim_{n→∞} \frac{D (n)}{2^{n}} = lim_{n→∞} \frac{E (n)}{2^{n}} = 1  (8)

So basically, f (n), Φ (n), D (n), and E (n) are very closed to 2^{n} as n → ∞. Which one is closer? We see from (7) that Φ (n) and D (n) are closer to 2^{n} than f (n). In addition, E (n) is closer to 2^{n} than Φ (n) and D (n). But it is not clear (see Table 1) which of Φ (n) or D (n) is closer to 2^{n}. One way to answer this, at least on average, is to calculate the partial sums ∑_{n≤N} Φ (n) and ∑_{n≤N} D (n) and compare them with the expected value ∑_{n≤N} 2^{n} = 2^{N+1} − 2. To accomplish this task, we will use the following results.

Lemma 1. (Nathanson, [9]) The following holds:

(i) f (n) = ∑_{d≤n} μ (d) (2^{⌊^{\frac{n}{d}}⌋} − 1) for every n ≥ 1, and

(ii) Φ (n) = ∑_{d|n} μ (d) (2^{\frac{n}{d}} − 1) for every n ≥ 1.

Lemma 2. (Ayad and Kihel [4]) The following holds:

(i) Φ(n + 1) = 2(f(n + 1) − f (n)) for every n ≥ 1, and

(ii) Φ (n) ≡ 0 (mod 3) for every n ≥ 3.

Notes

1) The functions f (n) and Φ (n) were introduced by Nathanson [9] and generalized by many authors [2, 3, 10, 11, 12, 15]. We refer the reader to Pongsriiam’s article [10] for a unified approach and the shortest calculation of the formulas for f (n), Φ (n) and their generalizations. Other related results can be found, for example, in the article of El Bachraoui [5], El Bachraoui and Salim [7], and Tang [14].

2) The sequences f (n) and Φ (n) are, respectively, Sloane’s sequence \underline{A038199} and \underline{A085945}. Note also that \underline{A027375} and \underline{A038199} coincide for all n ≥ 2 (see the comments at the end of this article).

3 Partial Sums and Limits

In this section, we compute the partial sums of f (n), Φ (n), and D (n). Then we show how to obtain the limits shown in (1) to (6). Throughout, for a real value function f and a positive function g, f = O (g) or f ≪ g means that there exists a positive constant c such that |f (x)| ≤ cg (x) for all large numbers x.

Theorem 3. The following estimates hold uniformly for N ≥ 1:

(i) ∑_{n≤N} f (n) = ∑_{d≤N} dμ (d) 2^{⌊^{\frac{N}{d}} ⌋} + ∑_{d≤N} μ (d) 2^{⌊^{\frac{N}{d}} ⌋}(N − d ⌊\frac{N}{d} ⌋ + 1) + O (N^{2})

= 2^{N+1} − 2^{⌊^{\frac{N}{2}} ⌋} (N − 2 ⌊\frac{N}{2} ⌋ + 3) − 2^{⌊^{\frac{N}{3}} ⌋} (N − 3 ⌊\frac{N}{3} ⌋ + 4) + O (2^{\frac{N}{5}} ),

(ii) ∑_{n≤N} Φ (n) = 2f(N) − 1 = 2^{N+1} − 2 · 2^{⌊^{\frac{N}{2}} ⌋} − 2 · 2^{⌊^{\frac{N}{3}} ⌋} + O (2^{\frac{N}{5}} ), and

(iii) ∑_{n≤N} D (n) = 2^{N+1} − 2^{⌊^{\frac{N}{2}} ⌋}(N − 2 ⌊\frac{N}{2} ⌋ + 1) + O (N2^{\frac{N}{3}} ).

Proof. Let N be a large positive integer. Then

∑_{n≤N} f (n) = ∑_{n≤N} ∑_{d≤n} μ (d) (2^{⌊^{\frac{n}{d}}⌋} − 1)

= ∑_{n≤N} ∑_{d≤n} μ (d) 2^{⌊^{\frac{n}{d}}⌋} + O (N^{2}) .

Changing the order of summation, we obtain

∑_{n≤N} f (n) = ∑_{d≤N} μ (d) ∑_{d≤n≤N} 2^{⌊^{\frac{n}{d}}⌋} + O(N^{2})  (9)

Consider the inner sum above. We divide the interval of summation [d, N] into ⋃_{k=1}^{⌊\frac{N}{d} ⌋−1}[kd, (k+ 1)d) ∪ [⌊\frac{N}{d} ⌋ d, N]. If n ∈ [kd, (k + 1)d), then ⌊\frac{n}{d}⌋ = k. So (9) becomes

∑_{d≤N} μ (d) ( ∑_{k=1}^{⌊\frac{N}{d} ⌋−1} ∑_{kd≤n<(k+1)d} 2^{⌊^{\frac{n}{d}}⌋} + ∑_{⌊\frac{N}{d} ⌋d≤n≤N} 2^{⌊^{\frac{n}{d}}⌋}) + O(N^{2})

= ∑_{d≤N} μ (d) (d ∑_{k=1}^{⌊\frac{N}{d} ⌋−1} 2^{k} + 2^{⌊^{\frac{N}{d}} ⌋} (N − d ⌊\frac{N}{d} ⌋ + 1)) + O(N^{2})

= ∑_{d≤N} dμ (d) 2^{⌊^{\frac{N}{d}} ⌋} + ∑_{d≤N} μ (d) 2^{⌊^{\frac{N}{d}} ⌋} (N − d ⌊\frac{N}{d} ⌋ + 1) + O (N^{2})  (10)

We see from (10) that the main terms can be obtained from the small value of d. Expanding the sum for d = 1, 2, 3, 4, we obtain

2^{N+1} − 2^{⌊^{\frac{N}{2}} ⌋} (N − 2 ⌊\frac{N}{2} ⌋ + 3) − 2^{⌊^{\frac{N}{3}} ⌋} (N − 3 ⌊\frac{N}{3} ⌋ + 4) + O ( ∑_{5≤d≤N} d2^{⌊^{\frac{N}{d}} ⌋}) (11)

We have

∑_{5≤d≤N} d2^{⌊^{\frac{N}{d}} ⌋} ≪ 2^{⌊^{\frac{N}{5}} ⌋} + ∑_{6≤d≤N} N2^{⌊^{\frac{N}{6}} ⌋} ≪ 2^{\frac{N}{5}}  (12)

We obtain (i) from (10), (11), and (12). Applying Lemmas 2(i), and 1(i), we obtain

∑_{n≤N} Φ (n) = 1 + ∑_{n≤N−1} Φ (n + 1)

= 1 + 2 ∑_{n≤N−1} (f (n + 1) − f (n))

= 2f(N) − 1

= 2 (∑_{d≤N} μ (d) (2^{⌊^{\frac{N}{d}} ⌋} − 1)) − 1

Similar to the proof of (i), we expand the sum for d = 1, 2, 3, 4 to obtain (ii). Next we write,

∑_{n≤N} D (n) = ∑_{n≤N} ∑_{d|n} f (d) = ∑_{dk≤N} f (d) = ∑_{k≤N} ∑_{d≤ \frac{N}{k}} f (d) .

Recall that ⌊\frac{⌊x⌋}{n}⌋ = ⌊\frac{x}{n}⌋ for every x ∈ ℝ. Applying (i) to the above sum, we get

∑_{n≤N} D (n) = ∑_{k≤N} 2^{⌊^{\frac{N}{k}} ⌋+1} − 2^{⌊^{\frac{N}{2k}}⌋} (⌊\frac{N}{k} ⌋ − 2 ⌊\frac{N}{2k} ⌋ + 3) + O (N2^{\frac{N}{3}} )  (13)

Now ∑_{3≤k≤N} 2^{⌊^{\frac{N}{k}} ⌋+1} − 2^{⌊^{\frac{N}{2k}}⌋}(⌊\frac{N}{k} ⌋ − 2 ⌊\frac{N}{2k}⌋ + 3) ≪∑_{k≤N} 2^{\frac{N}{3}} ≪N2^{\frac{N}{3}} . So (13) becomes

∑_{n≤N} D (n) = 2^{N+1} − 2^{⌊^{\frac{N}{2}} ⌋} (N − 2 ⌊\frac{N}{2} ⌋ + 3) + 2^{⌊^{\frac{N}{2}} ⌋+1} + O (N2^{\frac{N}{3}} )

= 2^{N+1} − 2^{⌊^{\frac{N}{2}} ⌋} (N − 2 ⌊\frac{N}{2} ⌋ + 1) + O (N2^{\frac{N}{3}} ) .

This completes the proof. Corollary 4. We obtain the following limits:

(i) lim_{\begin{matrix}N→∞ \\ N odd \end{matrix}} \frac{|∑_{n≤N} f (n) − 2^{N+1}|}{2^{⌊^{\frac{N}{2}} ⌋}} = 4,

(ii) lim_{\begin{matrix}N→∞ \\ N even \end{matrix}} \frac{|∑_{n≤N} f (n) − 2^{N+1}|}{2^{⌊^{\frac{N}{2}} ⌋}} = 3,

(iii) lim_{N→∞} \frac{|∑_{n≤N} Φ (n) − 2^{N+1}|}{2^{⌊^{\frac{N}{2}} ⌋}} = 2,

(iv) lim_{\begin{matrix}N→∞ \\ N odd \end{matrix}} \frac{|∑_{n≤N} D (n) − 2^{N+1}|}{2^{⌊^{\frac{N}{2}} ⌋}} = 2, and

(v) lim_{\begin{matrix}N→∞ \\ N even \end{matrix}} \frac{|∑_{n≤N} D (n) − 2^{N+1}|}{2^{⌊^{\frac{N}{2}} ⌋}} = 1.

Proof. By Theorem 3(i), we see that

\frac{|∑_{n≤N} f (n) − 2^{N+1}|}{2^{⌊^{\frac{N}{2}} ⌋}} = N − 2 ⌊\frac{N}{2} ⌋ + 3 + O (2^{\frac{N}{3} −⌊\frac{N}{2} ⌋}) .

Note that

N − 2 ⌊\frac{N}{2} ⌋ + 3 = \begin{cases}3, & if N is even; \\ 4, & if N is odd, \end{cases}

and 2^{\frac{N}{3} −⌊\frac{N}{2} ⌋} → 0 as N → ∞. So we obtain (i) and (ii). Similarly, we can apply Theorem 3(ii) and 3(iii) to obtain (iii), (iv) and (v). Corollary 5. The limits given in (1) to (6) hold.

Proof. By Corollary 4(ii), we see that lim_{\begin{matrix}N→∞ \\ N even \end{matrix}} \frac{|∑_{n≤N} f (n) − 2^{N+1}|}{2^{\frac{N}{2}}} = 3, and by Corollary 4(i), we have

lim_{\begin{matrix}N→∞ \\ N odd \end{matrix}} \frac{|∑_{n≤N} f (n) − 2^{N+1}|}{2^{\frac{N}{2}}} = lim_{\begin{matrix}N→∞ \\ N odd \end{matrix}} \frac{|∑_{n≤N} f (n) − 2^{N+1}|}{2^{\frac{N−1}{2}} \sqrt{2}}

= \frac{1}{\sqrt{2}} lim_{\begin{matrix}N→∞ \\ N odd \end{matrix}} \frac{|∑_{n≤N} f (n) − 2^{N+1}|}{2^{⌊^{\frac{N}{2}} ⌋}}

= \frac{4}{\sqrt{2}} = 2\sqrt{2}.

This gives (1) and (2). The proof of (3), (4), (5), and (6) is similar.

We know from (8) that f (n), Φ (n) and D (n) are asymptotic to 2^{n}. So we expect that ∑_{n≤N} \frac{f(n)}{2^{n}}, ∑_{n≤N} \frac{Φ(n)}{2^{n}}, and ∑_{n≤N} \frac{D(n)}{2^{n}} are asymptotic to N. But this does not give much the information on the error terms |∑_{n≤N} \frac{f(n)}{2^{n}} − N|, |∑_{n≤N} \frac{Φ(n)}{2^{n}} − N|, and |∑_{n≤N} \frac{D(n)}{2^{n}} − N|. We show in the next corollary that the error terms are small. Corollary 6. The following estimates hold:

(i) ∑_{n≤N} \frac{f (n)}{2^{n}} = N + 1 + (log 2) ∫_{1}^{∞} \frac{∑_{n≤t} f (n) − 2^{⌊t⌋+1}}{2^{t}} dt + O (2^{− \frac{N}{2}} ),

(ii) ∑_{n≤N} \frac{Φ (n)}{2^{n}} = N + 1 + (log 2) ∫_{1}^{∞} \frac{∑_{n≤t} Φ (n) − 2^{⌊t⌋+1}}{2^{t}} dt + O (2^{− \frac{N}{2}} ), and

(iii) ∑_{n≤N} \frac{D (n)}{2^{n}} = N + 1 + (log 2) ∫_{1}^{∞} \frac{∑_{n≤t} D (n) − 2^{⌊t⌋+1}}{2^{t}} dt + O (2^{− \frac{N}{2}} ).

Proof. Let F (t) = ∑_{n≤t} f (n). Then by partial summation ([1, p. 77] or [8, p. 488]), we see

that

∑_{n≤N} \frac{f (n)}{2^{n}} = \frac{F (N)}{2^{N}} + (log 2) ∫_{1}^{N} \frac{F (t)}{2^{t}}dt  (14)

By Theorem 3(i), for t ≥ 1, we can write F (t) = 2^{⌊t⌋+1} + g (t) where g (t) = O (2^{\frac{t}{2}} ). Then (14) becomes

∑_{n≤N} \frac{f (n)}{2^{n}} = 2 + (log 2) ∫_{1}^{N} \frac{2^{⌊t⌋+1}}{2^{t}} + \frac{g(t)}{2^{t}}dt + O (2^{− \frac{N}{2}} )  (15)

Consider

∫_{1}^{N} \frac{2^{⌊t⌋+1}}{2^{t}} dt = ∑_{k=1}^{N−1} ∫_{k}^{k+1} \frac{2^{⌊t⌋+1}}{2^{t}} dt

= ∑_{k=1}^{N−1} ∫_{k}^{k+1} \frac{2^{k+1}}{2^{t}} dt

= ∑_{k=1}^{N−1} 2^{k+1} [\frac{−2^{−t}}{log 2} ]_{k}^{k+1} = \frac{N − 1}{log 2}  (16)

Since g(t) = O (2^{\frac{t}{2}} ), ∫_{1}^{∞} \frac{g(t)}{2^{t}}dt converges and ∫_{N}^{∞} \frac{g(t)}{2^{t}}dt ≪ ∫_{N}^{∞} 2^{− \frac{t}{2}} dt ≪ 2^{− \frac{N}{2}} . So

∫_{1}^{N} \frac{g(t)}{2^{t}}dt = ∫_{1}^{∞} \frac{g(t)}{2^{t}}dt + O (2^{− \frac{N}{2}} )  (17)

From (15), (16) and (17), we obtain

∑_{n≤N} \frac{f (n)}{2^{n}} = 2 + (log 2) (\frac{N − 1}{log 2} + ∫_{1}^{∞} \frac{g(t)}{2^{t}}dt) + O (2^{− \frac{N}{2}} )

= N + 1 + (log 2) ∫_{1}^{∞} \frac{g(t)}{2^{t}}dt + O (2^{− \frac{N}{2}} ) .

The proof of (ii) and (iii) is similar.

We investigate some combinatorial properties of D (n) in the next section.

4 Combinatorial properties

We will give a combinatorial interpretation of D (n). But it may be useful later to do it in a more general setting. So we introduce the following definition. Throughout, let X, X_{d}, and \frac{1}{d}X denote, respectively, a nonempty finite set of positive integers, \{x ∈ X : d | x\} and \{\frac{x}{d} : x ∈ X\}.

Definition 7. Let D (X, n) denote the number of nonempty subsets A of X such that gcd (A) | n, and let f (X) denote the number of relatively prime subsets of X.

Theorem 8. Let X be a nonempty finite set of positive integers. Then

D (X, n) = ∑_{d|n} f (\frac{1}{d}X_{d}) .

Proof. We begin with

D (X, n) = ∑_{\begin{matrix}∅≠A⊆X \\ gcd(A)|n \end{matrix}} 1 = ∑_{d|n} ∑_{\begin{matrix}∅≠A⊆X \\ gcd(A)=d \end{matrix}} 1  (18)

The condition gcd (A) = d means that d divides all elements of A and gcd (\frac{1}{d}A) = 1. So ∅ ≠ A ⊆ X and gcd (A) = d if and only if ∅ ≠ A ⊆ X_{d} and gcd (\frac{1}{d}A) = 1. Therefore the inner sum in (18) is equal to

∑_{\begin{matrix}∅≠A⊆X_{d} \\ gcd(\frac{1}{d} A)=1 \end{matrix}} 1 = ∑_{\begin{matrix}∅≠ \frac{1}{d} A⊆ \frac{1}{d} X_{d} \\ gcd(\frac{1}{d} A)=1 \end{matrix}} 1 = ∑_{\begin{matrix}∅≠B⊆ \frac{1}{d} X_{d} \\ gcd(B)=1 \end{matrix}} 1 = f (\frac{1}{d}X_{d}) .

Hence

D (X, n) = ∑_{d|n} f (\frac{1}{d}X_{d}) .

Corollary 9. We have D (n) is equal to the number of subsets A of {1, 2, …, n} such that gcd (A) | n. In other words, D (n) = D ({1, 2, …, n} , n).

Proof. Let X = \{1, 2, …, n\}. Then X_{d} = \{d, 2d, …, ⌊\frac{n}{d}⌋ d\}. Therefore \frac{1}{d}X_{d} = \{1, 2, …, ⌊\frac{n}{d}⌋\}. By the definition, we see that

f (\frac{1}{d}X_{d}) = f (\{1, 2, …, ⌊\frac{n}{d}⌋\}) = f (⌊\frac{n}{d}⌋) .

Then by Theorem 8, we see that

D (X, n) = ∑_{d|n} f (⌊\frac{n}{d}⌋) = ∑_{d|n} f (d) = D (n) .

Therefore D (n) is equal to the number of subsets A of {1, 2, …, n} such that gcd (A) | n.

Theorem 10. Let d (n) be the number of positive divisors of n. Then D (n) + d (n) + 1 ≡ 0 (mod 3) for every n ≥ 1.

Proof. By Lemma 2(i) and 2(ii), we see that

f(n + 1) ≡ f (n) (mod 3) for every n ≥ 2.

This implies that f (n) ≡ f(2) ≡ 2 (mod 3) for every n ≥ 2. Then

D (n) = ∑_{d|n} f (d) = f(1) + ∑_{\begin{matrix}d|n \\ d≥2 \end{matrix}} f (d) ≡ 1 + 2(d (n) − 1) (mod 3).

This implies that D (n) + d (n) + 1 ≡ 0 (mod 3).

Comments and Open Questions

1) There is a small miscalculation in the formulas for Φ (n) and its generalizations in the literature. The right one is Φ (n) = ∑_{d|n} μ (d) (2^{\frac{n}{d}} − 1) (Lemma 1(ii)) which corresponds to \underline{A038199} in Sloane’s On-Line Encyclopedia of Integer Sequences [13]. The wrong one is Φ (n) = ∑_{d|n} μ (d) 2^{\frac{n}{d}} which is usually referred to as \underline{A027375}. Fortunately, there is little danger since both sequences coincide for all n ≥ 2. This is because we have the well known identity

∑_{d|n} μ (d) = \begin{cases}1, & if n = 1; \\ 0, & if n > 1. \end{cases}

2) The sequence D (n) is new and appears as A224840 in Sloane’s On-Line Encyclopedia of Integer Sequences [13].

3) As suggested by the limits given in (3) to (6), on average, the sequence D (n) lies closer to 2^{n} than Φ (n). But for certain n, Φ (n) may lie closer to 2^{n} than D (n). Considering Table 1 more carefully, we see that Φ (n) lies closer to 2^{n} for all odd n from 5 to 15. Therefore

the sign of D (n) − Φ (n) is alternating for 4 ≤ n ≤ 15.  (19)

So natural questions arise:

3.1 Does (19) hold for all n ≥ 4? We check that (19) holds for 4 ≤ n ≤ 30. But we do not have a proof for n ≥ 31. It is possible that (19) does not hold for some n ≥ 31. In this case, we may ask a weaker question:

3.2 Does D (n) − Φ (n) change sign infinitely often?

Other possible research questions are the following: 3.3 Can we say something about lim sup_{n→∞} \frac{2^{n}−D(n)}{2^{n}−Φ(n)}, lim inf_{n→∞} \frac{2^{n}−D(n)}{2^{n}−Φ(n)}, ∑_{n≤N} \frac{2^{n}−D(n)}{2^{n}−Φ(n)},

or ∑_{n≤N} \frac{2^{n}−Φ(n)}{2^{n}−D(n)}?

3.4 Is D (n) a perfect power for some n ≥ 2? (Ayad and Kihel [4] prove that f (n) is never a square for n ≥ 2. El Bachraoui and Luca [6] prove that Φ(n) is never a square for n ≥ 2, and f(n) and Φ(n) are perfect powers for at most finitely many n ∈ ℕ).

3.5 Are the sequences D (n) and Φ (n) periodic modulo a prime p? (Ayad and Kihel [4] show that the sequence f (n) is not periodic modulo p for any p ≠ 3).

5 Acknowledgment

The author received financial support from Faculty of Science, Silpakorn University, Thailand, contract number RGP 2555-07. The author would like to thank the referee for his/her suggestions, which improved the quality this article. Finally, the author wishes to thank Professor Luca for sending him his article, which also improved the presentation of this article.

References

[1] T. M. Apostol, Introduction to Analytic Number Theory, Springer, 1976.

[2] M. Ayad and O. Kihel, On the number of subsets relatively prime to an integer, J. Integer Seq. 11 (2008), Article 08.5.5.

[3] M. Ayad and O. Kihel, On relatively prime sets, Integers 9 (2009), A28, 343–352.

Available electronically at http://www.integers-ejcnt.org/vol9.html.

[4] M. Ayad and O. Kihel, The number of relatively prime subsets of {1, 2, …, N}, Integers

9 (2009), A14, 163–166. Available at http://www.integers-ejcnt.org/vol9.html.

[5] M. El Bachraoui, On relatively prime subsets, combinatorial identities, and Diophantine equations, J. Integer Seq. 15 (2012), Article 12.3.6.

[6] M. El Bachraoui and F. Luca, On a Diophantine equation of Ayad and Kihel, Quaest. Math. 35(2) (2012), 235–243.

[7] M. El Bachraoui and M. Salim, Combinatorial identities involving the Möbius function, J. Integer Seq. 13 (2010), Article 10.8.6.

[8] H. L. Montgomery and R. C. Vaughan, Multiplicative Number Theory, Cambridge University Press, 2006.

[9] M. B. Nathanson, Affine invariants, relatively prime sets, and a phi function for subsets of {1, 2, …, n}, Integers 7 (2007), A1. Available electronically at

http://www.integers-ejcnt.org/vol7.html.

[10] P. Pongsriiam, A remark on relatively prime sets, Integers 13 (2013), A49. Available

electronically at http://www.integers-ejcnt.org/vol13.html.

[11] T. Shonhiwa, On relatively prime sets counting functions, Integers 10 (2010), A39,

465–476. Available electronically at http://www.integers-ejcnt.org/vol10.html.

[12] T. Shonhiwa, A generalization of the Euler and Jordan totient functions, Fibonacci Quart. 37 (1999), 67–76.

[13] N. J. A. Sloane, On-Line Encyclopedia of Integer Sequences, http://oeis.org/.

[14] M. Tang, Relatively prime sets and a phi function for subsets of {1, 2, …, n}, J. Integer Seq. 13 (2010), Article 10.7.6.

[15] L. Tóth, On the number of certain relatively prime subsets of {1, 2, …, n}, Integers 10

    (2010), A35, 407–421. Available at http://www.integers-ejcnt.org/vol10.html.

2010 Mathematics Subject Classification: Primary 11A25; Secondary 11B75. Keywords: relatively prime set, divisor sum, partial sum, combinatorial identity, Euler phi function.

(Concerned with sequences \underline{A027375}, \underline{A038199}, \underline{A085945}, and \underline{A224840}.)

Received June 20 2013; revised version received September 20 2013. Published in Journal of Integer Sequences, October 12 2013.

Return to Journal of Integer Sequences home page.