Full Subsets of ℕ

Lila Naranjani Islamic Azad University Dolatabad Branch Isfahan Iran

                 lnaranjani@yahoo.com

Madjid Mirzavaziri Department of Pure Mathematics Ferdowsi University of Mashhad P. O. Box 1159–91775 Iran

                 mirzavaziri@gmail.com

Abstract

Let A be a subset of ℕ. We say that A is m-full if ∑ A = [m] for a positive integer m, where ∑ A is the set of all positive integers which are a sum of distinct elements of A and [m] = {1, …, m}. In this paper, we show that a set A = {a_{1}, …, a_{k}} with a_{1} < ⋯ < a_{k} is full if and only if a_{1} = 1 and a_{i} ≤ a_{1}+⋯+a_{i−1}+1 for each i, 2 ≤ i ≤ k. We also prove that for each positive integer m ∉ {2, 4, 5, 8, 9} there is an m-full set. We determine the numbers α(m) = min{|A| : ∑ A = [m]}, β(m) = max{|A| : ∑ A = [m]}, L(m) = min{max A : ∑ A = [m]} and U(m) = max{max A : ∑ A = [m]} in terms of m. We also give a formula for F (m), the number of m-full sets.

1 Introduction

Let n be a positive integer and denote by D(n) and σ(n) the set of its positive divisors and the sum of its positive divisors, respectively. A positive integer n is called perfect if σ(n) = 2n. Euclid proved that the formula 2^{p−1}(2^{p} − 1) gives an even perfect number whenever 2^{p} − 1 is prime. It has been proved for the first time by Euler that if an even positive integer n is perfect then n = 2^{p−1}q, where p and q = 2^{p} − 1 are primes. In this case

D(n) = {1, 2, 2^{2}, …, 2^{p−1}, q, 2q, 2^{2}q, …, 2^{p−1}q}.

A simple argument shows that each 1 ≤ ℓ ≤ 2n = 2^{p}q can be written as a sum of distinct elements of D(n). To see this, note that each ℓ, 1 ≤ ℓ ≤ 2^{p} − 1, can be written as a sum 2^{ℓ_{1}} + ⋯ + 2^{ℓ_{r}}, where r ≥ 1 and 0 ≤ ℓ_{1} < ⋯ < ℓ_{r} ≤ p − 1. Now if 2^{p} ≤ ℓ ≤ 2^{p}q, then we can write ℓ = αq + β, where 0 ≤ β ≤ 2^{p} − 1 and 1 ≤ α ≤ 2^{p} − 1. Thus we can write α = 2^{α_{1}} + ⋯ + 2^{α_{i}} and β = 2^{β_{1}} + ⋯ + 2^{β_{j}}, where i ≥ 1, j ≥ 0, 0 ≤ α_{1} < ⋯ < α_{i} ≤ p − 1 and 0 ≤ β_{1} < ⋯ < β_{j} ≤ p − 1. Hence

ℓ = 2^{α_{1}}q + ⋯ + 2^{α_{i}}q + 2^{β_{1}} + ⋯ + 2^{β_{j}}

is a sum of distinct elements of D(n).

These considerations motivate us to find all positive integers n having the property that each 1 ≤ ℓ ≤ σ(n) can be written as a sum of distinct elements of D(n). This leads us to the following problem:

Let A = {a_{1}, …, a_{k}} be a subset of ℕ. Define the sum set of A, denoted by ∑ A, by

∑ A = {a_{i_{1}} + ⋯ + a_{i_{r}} : a_{i_{1}} < ⋯ < a_{i_{r}}, 1 ≤ r ≤ k}.

For what positive integer m does there exist a set A with ∑ A = [m], where [m] = {1, …, m}?

We show that each positive integer m ∉ {2, 4, 5, 8, 9} has this property and determine the numbers

α(m) = min{|A| : ∑ A = [m]},
β(m) = max{|A| : ∑ A = [m]},
L(m) = min{max A : ∑ A = [m]},
U(m) = max{max A : ∑ A = [m]}.

2 The Results

Definition 1. Let m be a positive integer. A subset A of ℕ is called m-full if ∑ A = [m]. A is called full if it is m-full for some positive integer m.

Theorem 2. A subset A = {a_{1}, …, a_{k}} of ℕ with a_{1} < ⋯ < a_{k} is full if and only if a_{1} = 1 and a_{i} ≤ a_{1} + ⋯ + a_{i−1} + 1 for each i, 2 ≤ i ≤ k.

Proof. Let A be full and ∑ A = [m] for a positive integer m. Clearly a_{1} = 1. If a_{j} > a_{1} + ⋯ + a_{j−1} + 1 for some j, 2 ≤ j ≤ k, then a_{1} + ⋯ + a_{j−1} + 1 is not a sum of distinct elements of A. But 1 ≤ a_{1} + ⋯ + a_{j−1} + 1 ≤ a_{1} + ⋯ + a_{k} = m. This contradicts to the fact that ∑ A = [m].

Conversely, suppose that a_{1} = 1 and a_{i} ≤ a_{1} + ⋯ + a_{i−1} + 1 for each i, 2 ≤ i ≤ k. We claim that ∑ A = [a_{1} + ⋯ + a_{k}]. We prove this by induction on k. For k = 1 the result is obvious. Suppose that the result is true for k − 1. Then ∑ A \ {a_{k}} = [a_{1} + ⋯ + a_{k−1}]. Now suppose that a_{1} + ⋯ + a_{k−1} + 1 ≤ ℓ ≤ a_{1} + ⋯ + a_{k} and write ℓ = a_{k} + a. Then a belongs to {0, 1, …, a_{1} + ⋯ + a_{k−1}} since a_{k} ≤ a_{1} + ⋯ + a_{k−1} + 1. If a = 0 then ℓ = a_{k} ∈ ∑ A and if a ≠ 0 then a ∈ [a_{1} + ⋯ + a_{k−1}] = ∑ A \ {a_{k}} can be written as a_{i_{1}} + ⋯ + a_{i_{r}}. Thus ℓ = a_{i_{1}} + ⋯ + a_{i_{r}} + a_{k} ∈ ∑ A.

Proposition 3. Let n = p_{1}^{α_{1}} ⋯ p_{r}^{α_{r}}, with p_{1} < ⋯ < p_{r} primes, be a positive integer. Then D(n) = {d : d|n} is full if and only if p_{1} = 2 and p_{i} ≤ σ(p_{1}^{α_{1}} ⋯ p_{i−1}^{α_{i−1}})+1 for each i, 2 ≤ i ≤ r.

Proof. If D(n) is m-full then m = σ(n). Since p_{1}^{α_{1}} ⋯ p_{i−1}^{α_{i−1}}|n and p_{1}^{α_{1}} ⋯ p_{i−1}^{α_{i−1}} ≠ n, we have σ(p_{1}^{α_{1}} ⋯ p_{i−1}^{α_{i−1}}) < σ(n). Hence σ(p_{1}^{α_{1}} ⋯ p_{i−1}^{α_{i−1}}) + 1 is a member of [σ(n)]. Thus if p_{i} > σ(p_{1}^{α_{1}} ⋯ p_{i−1}^{α_{i−1}}) + 1 for some i, then the number σ(p_{1}^{α_{1}} ⋯ p_{i−1}^{α_{i−1}}) + 1 is a member of [σ(n)] which is not a sum of distinct elements of D(n). On the other hand, if the condition p_{i} ≤ σ(p_{1}^{α_{1}} ⋯ p_{i−1}^{α_{i−1}}) + 1 for each i, 2 ≤ i ≤ r, is satisfied, then using an argument similar to the one used in Theorem 2, we can inductively prove that each element of [σ(n)] can be written as a sum of distinct elements of D(n).

In the next theorem, we characterize all m for which there is an A with ∑ A = [m].

Theorem 4. Let m be a positive integer. There is a set A such that ∑ A = [m] if and only if m ∉ {2, 4, 5, 8, 9}.

Proof. By simple inspection, there is no A with ∑ A = [m] for m = 2, 4, 5, 8, 9 . Conversely, for m = 1, 3, 6, 7, 10 note that A = {1}, {1, 2}, {1, 2, 3}, {1, 2, 4}, {1, 2, 3, 4} are m-full. The recursive construction below shows us that for each m ≥ 10 there is an A with ∑ A = [m].

Suppose there is an A = {a_{1}, …, a_{k}} with a_{1} < ⋯ < a_{k} such that ∑ A = [m], for some m ≥ 10. If a_{k} < a_{1} + ⋯ + a_{k−1} + 1 then ∑(A \ {a_{k}}) ∪ {a_{k} + 1} = [m + 1], and there remains nothing to prove. If a_{i} < a_{1} + ⋯ + a_{i−1} + 1 for some i, 3 ≤ i < k, then choose j as the greatest i with this property. In this case we have

a_{j} < a_{1} + ⋯ + a_{j−1} + 1, a_{j+1} = a_{1} + ⋯ + a_{j−1} + a_{j} + 1.

Notice that j ≥ 3 since a_{1} = 1, a_{2} = a_{1} + 1 = 2 and a_{3} ∈ {3, 4}. Hence a_{j} + 1 ≠ a_{j+1} and if we omit a_{j} from A and add a_{j} + 1 to it, then the resulting set is still full and its sum set is [m + 1]. Otherwise, there is no i with the property a_{i} < a_{1} + ⋯ + a_{i−1} + 1 and so a_{i} = a_{1} + ⋯ + a_{i−1} + 1 for each i, 2 ≤ i ≤ k. We can therefore deduce that A = {1, 2, 4, …, 2^{k−1}}. Whence m = 2^{k} − 1 and we must give a class of sets B with ∑ B = [2^{k}], k ≥ 4, to complete the proof.

The class of sets B is defined by a recursive construction. For k = 4 choose the set B = {1, 2, 3, 4, 6}. If ∑ B = [2^{k}] for B = {b_{1}, …, b_{s}} then the set B′ = {1, 2b_{1}, …, 2b_{s−1}, 2b_{s} − 1} is clearly full and since 1 + 2b_{1} + ⋯ + 2b_{s−1} + 2b_{s} − 1 = 2(b_{1} + ⋯ + b_{s}) = 2 · 2^{k} = 2^{k+1}, we have ∑ B′ = [2^{k+1}] and the proof is complete.

A natural question is to determine the number of m-full sets for a given positive integer m. We denote this number by F (m). As an example, a straightforward argument shows that F (12) = 2 and the two 12-full sets are {1, 2, 3, 6} and {1, 2, 4, 5}. We give a formula for F (m), but prior to that we discuss some related problems.

Proposition 5. Let m ∉ {2, 4, 5, 8, 9} be a positive integer and

α(m) = min{|A| : ∑ A = [m]},
β(m) = max{|A| : ∑ A = [m]}.

Then

α(m) = min{ℓ : m ≤ 2^{ℓ} − 1} = ⌈log_{2}(m + 1)⌉
β(m) = max\{ℓ : \frac{ℓ(ℓ + 1)}{2} ≤ m\}.

Proof. Let A = {a_{1}, …, a_{k}} be an arbitrary m-full set. Then, by Theorem 2,

m = a_{1} + ⋯ + a_{k} ≤ 1 + 2 + 4 + ⋯ + 2^{k−1} = 2^{k} − 1.

We claim that if n = min{ℓ : m ≤ 2^{ℓ} − 1} then k ≥ n. In contrary, suppose that k < n. Then 2^{k} − 1 < m. Thus m = a_{1} + ⋯ + a_{k} ≤ 2^{k} − 1 < m which is a contradiction. Hence k ≥ n and, since A was arbitrary, we therefore have α(m) ≥ n.

On the other hand, we show that the minimum is attained. At first we show this when m is a power of 2. For m = 16 we can choose A = {1, 2, 3, 4, 6}. Suppose that for m = 2^{n−1} there is an m-full set A = {a_{1}, a_{2}, …, a_{n}}. Then A′ = {1, 2a_{1}, 2a_{2}, …, 2a_{n−1}, 2a_{n} − 1} is a 2^{n}-full set with n + 1 elements.

We now suppose that m = 2^{n−1} + r, where r belongs to {0, 1, 2, …, 2^{n−1} − 1} and we prove the existence of an m-full set with n elements by induction on r. This is proved for r = 0. Suppose that this is true for r − 1; namely there is a (2^{n−1} + r − 1)-full set A = {a_{1}, a_{2}, …, a_{n}}. If m = 2^{n−1} + r is a power of 2 then there is nothing to prove. We may thus assume that there is an i for which a_{i} < a_{1} + ⋯ + a_{i−1} + 1. Now if there is the least j with a_{i+j} ≠ a_{i} + j then the set {a_{1}, …, a_{i+j−2}, a_{i+j−1} + 1, a_{i+j}, …, a_{n}} is an m-full set with n elements. Otherwise, the set {a_{1}, …, a_{n−1}, a_{n} + 1} is an m-full set with n elements.

To prove the other assertion, let n′ = max\{ℓ : \frac{ℓ(ℓ+1)}{2} ≤ m\}. We claim that if A = {a_{1}, …, a_{k}} is an arbitrary m-full set, then k ≤ n′. On the contrary, suppose that k > n′. Then \frac{k(k+1)}{2} > m. Hence m = a_{1} + a_{2} + ⋯ + a_{k} ≥ 1 + 2 + ⋯ + k = \frac{k(k+1)}{2} > m which is a contradiction. Thus k ≤ n′ and, since A was arbitrary, we therefore have β(m) ≤ n′.

On the other hand, we show that the maximum is attained. Let m = \frac{n′(n′+1)}{2} + r, where r belongs to {0, 1, …, n′}. Then A = {1, 2, 3, …, n′ − 1, n′ + r} is an m-full set with n′ elements.

Remark 6. The direct problem for subset sums is to find lower bounds for | ∑ A| in terms of |A| . The inverse problem for subset sums is to determine the structure of the extremal sets A of integers for which | ∑ A| is minimal. M. B. Nathanson gives a complete solution for the direct and the inverse problem for subset sums in [1] and proves that if A is a set of positive integers with |A| ≥ 2 then | ∑ A| ≥ \binom{|A|+1}{2}. This immediately implies the last part of Proposition 5.

Theorem 7. Let m ∉ {2, 4, 5, 8, 9, 14} be a positive integer and denote min{max A : ∑ A = [m]\} by L(m). If m = \frac{n(n+1)}{2} + r, where r = 0, 1, …, n then

L(m) = \begin{cases}n, & if r = 0; \\ n + 1, & if 1 ≤ r ≤ n − 2; \\ n + 2, & if 1 ≤ r = n − 1 or n. \end{cases}

Proof. Let m = \frac{n(n+1)}{2} + r, where r = 0, 1, …, n. Then there are 3 cases:

Case 1: r = 0. Let A = \{1, …, n\}. Since ∑ A = [\frac{n(n+1)}{2}] and max A has the minimum possible value, L(m) = n.

Case 2: r = 1, …, n − 2. We can consider the set

A = {1, …, n, n + 1} \ {n + 1 − r}

which is m-full, since n + 1 − r ≥ 3 and 1 + ⋯ + n + (n + 1) − (n + 1 − r) = \frac{n(n+1)}{2} + r = m. Hence L(m) = n + 1.

Case 3: r = n−1 or n. In this case we cannot omit n+1−r from the set {1, …, n, n+1}, because n + 1 − r is 1 or 2 and the resulting set is not full. Thus we have to add n + 2 and omit some other element. In fact for r = n − 1 the suitable set with minimum possible value for its maximum is {1, …, n, n + 2} \ {3}, and for r = n the desired set is {1, …, n − 1, n + 1, n + 2} \ {3} (note that in this case we have n ≠ 4 since m ≠ 14 and we can therefore deduce that the latter set is full). We can therefore deduce that L(m) = n + 2.

For the remaining case m = 14, it can be easily verified that L(14) = 7. The first few values of L(m), Sloane’s OEIS [2, \underline{A188429}], are

\begin{matrix}m & 1 & 3 & 6 & 7 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\ L(m) & 1 & 2 & 3 & 4 & 4 & 5 & 5 & 6 & 7 & 5 & 6 & 6 & 6 & 7 & 7 \end{matrix}

Theorem 8. Let m ≥ 20 be a positive integer and denote max{max A : ∑ A = [m]} by U(m). Then

U(m) = ⌈\frac{m}{2}⌉.

Proof. Let A = {a_{1}, …, a_{k}} with a_{1} < ⋯ < a_{k} be m-full. By Theorem 2, a_{k} ≤ a_{1}+⋯+a_{k−1}, which is equivalent to a_{k} ≤ m − a_{k} since A is m-full. Therefore a_{k} ≤ ⌈\frac{m}{2}⌉ holds.

Now put b = ⌈\frac{m}{2}⌉. Since m − ⌈\frac{m}{2}⌉ ≥ 10, by Theorem 4 we can find a B′ with ∑ B′ = [m − ⌈\frac{m}{2}⌉]. Whence B = B′ ∪ \{b\} satisfies the properties ∑ B = [m] and max B = ⌈\frac{m}{2}⌉.

For the remaining cases, it can be easily verified that the values of U(m), Sloane’s OEIS [2, \underline{A188430}], are

\begin{matrix}m & 1 & 3 & 6 & 7 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 \\ U(m) & 1 & 2 & 3 & 4 & 4 & 5 & 6 & 7 & 7 & 8 & 6 & 7 & 8 & 9 \end{matrix}

We can now determine the value of F (m) for each positive integer m. We assume that L(m) = U(m) = 0 whenever m ∈ {2, 4, 5, 8, 9}.

Lemma 9. Let m be a positive integer and F (m, i) denote the number of m-full sets A with max A = i, where L(m) ≤ i ≤ U(m). Then

F (m, i) = ∑_{j=L(m−i)}^{min{U(m−i),i−1}} F (m − i, j).

Proof. Let A = {a_{1}, …, a_{k}} with a_{1} < ⋯ < a_{k} = i be an m-full set. Then A′ = A \ {a_{k}} is an (m − i)-full set such that j = max A′ < i. Thus L(m − i) ≤ j ≤ min{U(m − i), i − 1} and the result follows.

Theorem 10. Let m be a positive integer and denote the number of m-full sets by F (m). Then F (m) = ∑_{i=L(m)}^{U(m)} F (m, i).

Proof. Let A = {a_{1}, …, a_{k}} with a_{1} < ⋯ < a_{k} be an m-full set. Then L(m) ≤ a_{k} ≤ U(m) and the result is now obvious.

The first few values of F (m), Sloane’s OEIS [2, \underline{A188431}], are

\begin{matrix}m & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\ F (m) & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 2 & 2 & 1 & 2 & 1 & 2 & 3 & 4 & 5 \end{matrix}

Example 11. We evaluate F (21). Using Theorem 7 and Theorem 8, L(21) = 6 and U(21) = 12. Thus

F (21) = F (21, 6) + F (21, 7) + F (21, 8) + F (21, 9) + F (21, 10) + F (21, 11) + F (21, 12).

We need to compute L(m) and U(m) for m = 15, 14, 13, 12, 11, 10, 9. We have

\begin{matrix}m & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ L(m) & 0 & 4 & 5 & 5 & 6 & 7 & 5 \\ U(m) & 0 & 4 & 5 & 6 & 7 & 7 & 8 \end{matrix}

Noting the facts that L(6) = U(6) = 3 and L(7) = U(7) = 4 we therefore have

F (21) = F (15, 5) + F (13, 6) + F (13, 7) + F (12, 5) + F (12, 6) + F (11, 5) + F (10, 4)
= F (10, 4) + F (7, 4) + F (6, 3) + F (7, 4) + F (6, 3) + F (6, 3) + F (6, 3)
= F (6, 3) + F (7, 4) + F (6, 3) + F (7, 4) + F (6, 3) + F (6, 3) + F (6, 3)
= 7.

The seven 21-full sets are

{1, 2, 3, 4, 5, 6}, {1, 2, 4, 6, 8}, {1, 2, 3, 7, 8}, {1, 2, 4, 5, 9},
{1, 2, 3, 6, 9}, {1, 2, 3, 5, 10}, {1, 2, 3, 4, 11}.

3 Acknowledgement

The second author of this research was supported by a grant from Ferdowsi University of Mashhad; No. MP89177MIZ. The authors wish to acknowledge the referees for their valuable comments and suggestions.

References

[1] M. B. Nathanson, Inverse theorems for subset sums, Trans. Amer. Math. Soc. 347 (1995), 1409–1418.

[2] N. J. A. Sloane, The On-Line Encylopedia of Integer Sequences, 2011.

2010 Mathematics Subject Classification: Primary 05A17; Secondary 11P81. Keywords: perfect number, m-full set, partition of a positive integer.

(Concerned with sequences \underline{A188429}, \underline{A188430}, and \underline{A188431}.)

Received June 3 2010; revised versions received December 3 2010; April 20 2011. Published in Journal of Integer Sequences, April 22 2011.

Return to Journal of Integer Sequences home page.