ON PRIMITIVE 3-SMOOTH PARTITIONS OF n

Michael R. Avidon

Submitted: September 30, 1996, Accepted: December 2, 1996

This paper is dedicated to Paul Erdős, on the sad occasion of his recent death.

Abstract. A primitive 3-smooth partition of n is a representation of n as the sum of numbers of the form 2^{a}3^{b}, where no summand divides another. Partial results are obtained in the problem of determining the maximal and average order of the number of such representations. Results are also obtained regarding the size of the terms in such a representation, resolving questions of Erdős and Selfridge.

0. Introduction

Recently Erdős proposed the following problem: let r(n) be the number of representations of n as the sum of 3-smooth numbers (integers of the form 2^{a}3^{b} with a, b ≥ 0), which are primitive (no summand divides another). Determine

i. the maximal order of r(n), ii. the average order of r(n).

It is easy to show that r(n) ≥ 1 for all n (see[1],[2]). In this paper partial results are obtained for both of these problems. Specifically, we prove:

Theorem 1. For n ≥ 5,

r(n) ≤ \frac{1}{2} · n^{α},

where α = log 2/ log 3 (≈ 0.631).

Theorem 2. Let R(x) = ∑_{n≤x} r(n). Then

\frac{x^{β}}{(log x)^{β+3/2}} ≪ R(x) ≪ \frac{x^{β}}{(log x)^{3/2}}

where

β = \frac{1}{log 3} · log(\frac{log 6}{log 2}) + \frac{1}{log 2} · log(\frac{log 6}{log 3}) (≈ 1.570).

Define g(n) as the maximum, over all representations, of the minimum term (e.g. 11=8+3=9+2, so g(11) = 3). Erdős has asked if lim_{n→∞} g(n) = ∞. We answer this in the affirmative by proving:

Typeset by AMS-TEX

1991 Mathematics Subject Classification. Primary 11P85, Secondary 05A17.

Theorem 3. g(n) ≥ \frac{3}{5} · n^{γ}, where γ = \frac{log 2}{log 5}(≈ 0.431).

Concerning g(n), Selfridge has asked if, for each n, g(n) appears as the least term in exactly one representation of n. We answer this in the negative by providing an infinite number of counter-examples where it appears in two representations.

The author would like to thank Professor Carl Pomerance for suggesting these problems, and also for his counsel as the work progressed.

1. Proof of theorem 1

Lemma 1. r(2^{a}3^{b}m) = r(m)

Proof. It is enough to show that r(2m) = r(m) and r(3m) = r(m). There cannot exist a term 3^{β} in any representation of 2m, for that would make the sum odd. Thus all terms are even. Dividing through by 2 gives a 1-1 correspondence between representations of 2m and m. Likewise, for 3m, a term 2^{α} would mean the sum is not divisible by 3. Thus all terms are divisible by 3. Dividing by 3 gives a similar correspondence between 3m and m.

The above lemma tells us that we need only deal with n coprime to 6 to determine an upper bound. Each representation of a number coprime to 6 must have a term 3^{j}. Define

k = [log_{3} n]

and for these n, define r_{j}(n) = the number of representations with summand 3^{j}, for j ≥ 0. Note that

r(n) = ∑_{j=0}^{k} r_{j}(n).

Also define

s_{j}(n) = ∑_{i=0}^{j} r_{i}(n),

(so that r(n) = s_{j}(n) for j ≥ k).

Lemma 2. For n ≥ 5, and i = 1, 2, ..., k

s_{i}(n) ≤ 2^{i−1}.

[Note that s_{0}(n) = r_{0}(n) = 0 if n ≠ 1, and is 1 if n = 1.]

Proof. We use complete induction on n. For n=5 or 7, we have k = 1. Since 5=3+2, and 7=3+4 are their only representations,

s_{1}(n) = r_{1}(n) = 1 = 2^{0}

so the inequalities hold. Note that for n > 1, s_{1}(n) = r_{1}(n) = the number of representations of n in the form 3 + 2^{a}. Obviously, then

s_{1}(n) = 0 or 1 ≤ 2^{0}.

Now assume for all m < n and i = 1, 2, ..., k = k(m) that

s_{i}(m) ≤ 2^{i−1}.

It is easy to see that, for j ≥ 2,

r_{j}(n) = s_{j−1} (\frac{n − 3^{j}}{2^{a_{j}}} )

where a_{j} is defined by 2^{a_{j}}||n − 3^{j}. Therefore, from the inductive hypothesis, we deduce that for j ≥ 2

r_{j}(n) ≤ 2^{j−2}.

Thus, for n ≥ 5 and i ≥ 2

s_{i}(n) = ∑_{j=1}^{i} r_{j}(n) ≤ 1 + ∑_{j=2}^{i} 2^{j−2} = 2^{i−1}.

This completes the proof of the lemma.

The above lemma yields

r(n) = s_{k}(n) ≤ 2^{k−1} ≤ \frac{1}{2} · 2^{log_{3}(n)} = \frac{1}{2} · n^{α}

which completes the proof of Theorem 1.

2. Proof of theorem 2

We introduce the following notation:

• ∑^{∗} indicates a sum over numbers prime to 6,

• R^{∗}(x) = ∑_{n≤x}^{∗} r(n),

• S(x) = the number of primitive sums ∑ 2^{a}3^{b} = n with each term 2^{a}3^{b} ≤ x and (n, 6) = 1,

• S_{j}(x) = the number of sums described above that have the summand 3^{j},

• α = \frac{log 2}{log 3}.

For any x ≥ 3, there exists L ∈ ℕ such that 3^{L} ≤ x < 3^{L+1}. Obviously, if we prove the theorem for x = 3^{L}, the general result will follow from R(3^{L}) ≤ R(x) ≤ R(3^{L+1}). Therefore, we henceforth assume that x = 3^{L}.

Note that every n ≤ x can be uniquely written as n = 2^{a}3^{b}m with (m, 6) = 1, and m ≤ x/2^{a}3^{b}. Since r(n) = r(m), by lemma 1, it follows that

R(x) = ∑_{{a,b≥0 \atop 2^{a}3^{b}≤x}} R^{∗} (\frac{x}{2^{a}3^{b}} ) .

Using this fact, the theorem will follow once we prove, for x ≥ 2,

(2.1)  \frac{x^{β}}{(log x)^{β+3/2}} ≪ R^{∗}(x) ≪ \frac{x^{β}}{(log x)^{3/2}} .

Specifically, the theorem’s lower bound follows trivially from this, and on the other hand we would have

R(x) ≪ ∑_{2^{a}3^{b}≤\sqrt{x}} (\frac{x}{2^{a}3^{b}} )^{β} · (log x)^{−3/2} + ∑_{\sqrt{x}<2^{a}·3^{b}≤x} x^{β/2}

≪ x^{β} · (log x)^{−3/2} + log^{2} x · x^{β/2}
≪ x^{β} · (log x)^{−3/2}.

Consider S(x/L). This counts primitive sums ∑ 2^{a}3^{b} with 2^{a}3^{b} ≤ x/L. Then b ≤ L−1, and we have at most L terms. Thus, it follows from the definitions that

S (\frac{x}{L}) ≤ R^{∗}(x) ≤ S(x).

This will imply (2.1) once we prove:

S(x) ≍ (log x)^{−3/2} · x^{β},

and this would follow from

(2.2)  S(x) ≍ \frac{1}{L} · \binom{[L/α] + L}{L},

since, by Stirling’s formula, the binomial coefficient above equals

exp{([L/α] + L + 1/2) log([L/α] + L) − (L + 1/2) log L − ([L/α] + 1/2) log([L/α]) + O(1)}

= exp{[L/α] · log(1 + α) + L · log(1 + 1/α) − 1/2 · log L + O(1)}

≍ x^{β} · (log x)^{−1/2}.

It is easy to see that

S (\frac{x}{3}) ≤ S_{L}(x) < S(x).

The second inequality trivially follows from the definitions. Since x = 3^{L}, no sum counted by S(x/3) has a term divisible by 3^{L}. Thus, if we take any such sum, multiply through by 2 and add 3^{L}, we obtain a sum counted by S_{L}(x). Hence, the first inequality holds, and (2.2) would follow from

(2.3)  S_{L}(x) ≍ \frac{1}{L} · \binom{[L/α] + L}{L}.

We now establish a recursive formula for the S_{j} and use it to prove (2.3).

The sums counted by S_{j}(x) can all be written in the form

3^{j} + 2^{l} · (3^{i} + ...)

where 0 ≤ i ≤ j − 1, and 1 ≤ l ≤ [(L − i)/α]. If 0 ≤ i ≤ j − 2, replacing 3^{j} by 3^{j−1} yields a 1-1 correspondence with precisely those sums counted by S_{j−1}(x). If i = j −1, the number of different sums in the parentheses, for a given l, is S_{j−1}(x/2^{l}). Therefore

(2.4)  S_{j}(x) = ∑_{l=0}^{[(L−j+1)/α]} S_{j−1} (\frac{x}{2^{l}} ) .

In particular

S_{L}(x) = S_{L−1}(x) + S_{L−1} (\frac{x}{2}) .

We can generalize this to a relationship of the form

(2.5)  S_{L}(x) = ∑_{l=0}^{[j/α]} A_{j}(l) · S_{L−j} (\frac{x}{2^{l}} )

via (2.4), where A_{1}(0) = A_{1}(1) = 1 by the above. Note that the sums counted by S_{L−j−1}(x/2^{l+λ}) have 3^{L−j−1} ≤ 3^{L}/2^{l+λ}, which implies λ ≤ [(j + 1)/α] − l. Now if we combine the above with (2.4) we obtain

\begin{matrix}S_{L}(x) = ∑_{l=0}^{[j/α]} A_{j}(l) ∑_{λ=0}^{[\frac{j+1}{α}]−l} S_{L−j−1} (\frac{x}{2^{l+λ}} ) \\ = \begin{matrix}[ & \frac{j+1}{α} & ] \\ ∑ \\ m=0 \end{matrix} S_{L−j−1} (\frac{x}{2^{m}} ) ∑_{l=0}^{min(m,[\frac{j}{α}])} A_{j}(l), \end{matrix}

so we conclude

(2.6)  A_{j+1}(m) = ∑_{l=0}^{min(m,[j/α])} A_{j}(l).

It is trivially true that S_{0}(x) = 1 for x ≥ 1, so with j = L, (2.5) yields

(2.7)  S_{L}(x) = ∑_{l=0}^{[L/α]} A_{L}(l).

Now let B_{j}(l) = \binom{l+j}{l} − α · \binom{l+j}{l−1} (with the conventions that \binom{0}{0} = 1 and \binom{n}{−1} = 0).

\underline{Claim}: B_{j−1}(l) ≤ A_{j}(l) ≤ B_{j+1}(l).

Once this claim is proved, (2.3) will follow, and the proof will be complete. Specifically, since ∑_{l=0}^{m} \binom{l+j}{l} = \binom{m+j+1}{m},

(2.8)  ∑_{l=0}^{m} B_{j}(l) = B_{j+1}(m).

Therefore, combining this with (2.7) and the claim,

B_{L}([L/α]) ≤ S_{L}(x) ≤ B_{L+2}([L/α]).

This is the same as

\binom{[L/α] + L}{[L/α]} · (1 − α · \frac{[L/α]}{L + 1}) ≤ S_{L}(x) ≤ \binom{[L/α] + L + 2}{[L/α]} · (1 − α · \frac{[L/α]}{L + 3})

and (2.3) follows at once.

\underline{Proof of claim}: We use induction on j. For j = 1 the inequalities follow immediately from the fact that A_{1}(0) = A_{1}(1) = 1.

Now assume the inequalities hold for a given j ≥ 1 and 0 ≤ l ≤ [j/α]. Suppose first that 0 ≤ m ≤ [j/α]. Summing the inequalities over l ∈ [0, m], applying (2.6) and (2.8) yields the corresponding inequalities for A_{j+1}(m).

We are left to handle the [j/α] < m ≤ [(j + 1)/α], so that m = [j/α] + i, where i = 1 or possibly 2. For these m, (2.6) tells us that A_{j+1}(m) = A_{j+1}([j/α]). The already established inequalities from the preceding paragraph yield

B_{j}([j/α]) ≤ A_{j+1}(m) ≤ B_{j+2}([j/α]).

The proof of the claim will be complete if we show

(i) B_{j+2}([j/α]) < B_{j+2}([j/α] + 1) < B_{j+2}([j/α] + 2) and

(ii) B_{j}([j/α]) > B_{j}([j/α] + 1) > B_{j}([j/α] + 2). Towards this, note that for i = 1 or 2, and j ∈ ℕ,

α · \frac{1}{j + 2} < \frac{1}{[j/α] + i} < α · \frac{1}{j}.

These two inequalities respectively imply

B_{j+1}([j/α] + i) > 0

and

B_{j−1}([j/α] + i) < 0.

Noting that \binom{n}{k} = \binom{n+1}{k+1} − \binom{n}{k+1}, the definition of B_{j}(l) yields

B_{j}(l) = B_{j}(l + 1) − B_{j−1}(l + 1).

Combined with the above inequalities, this establishes the validity of (i) and (ii), hence the claim, and hence we have theorem 2.

3. Proof of theorem 3

Since g(2^{a}3^{b}n) = 2^{a}3^{b} · g(n) (from the proof of lemma 1), we may assume (n, 6) = 1. It is easy to check that the theorem holds for n =1,5,7. We proceed inductively. We may now assume

(3.1)  3^{L} < n < 3^{L+1}, L ≥ 2

so that

(3.2)  n = 3^{L} + 2^{a}k, a ≥ 1, k ≡ 1(2), k < 3^{L}.

Evidently

g(n) ≥ min(3^{L}, 2^{a} · g(k)).

If g(n) ≥ 3^{L}, then g(n) > n/3 and the theorem holds. Otherwise

g(n) ≥ 2^{a} · \frac{3}{5} · k^{γ}

by the inductive hypothesis.

Case I: k ≥ 3^{L−a}

We wish to show that

2^{a} · k^{γ} ≥ n^{γ}

the electronic journal of combinatorics 4 (1997), #R2 8

or

k ≥ \frac{n}{2^{a/γ}} = \frac{3^{L} + 2^{a} · k}{2^{a/γ}}

or

k ≥ \frac{3^{L}}{2^{a/γ} − 2^{a}} .

Thus it is enough to have

3^{L−a} ≥ \frac{3^{L}}{2^{a/γ} − 2^{a}}

or

γ ≤ min_{a≥1} \frac{a · log 2}{log(3^{a} + 2^{a})} = \frac{log 2}{log 5},

so the theorem holds. Note that if a ≥ L, we certainly have k ≥ 3^{L−a}, so that in particular the theorem holds in that situation. Case II: k < 3^{L−a} and 1 ≤ a ≤ L − 1

From (3.2):

n = (3^{L} − 3^{L} · (2/3)^{a}) + (2^{a} · 3^{L−a} + 2^{a} · k)

= (3^{L−1} + 2 · 3^{L−2} + 2^{2} · 3^{L−3} + ... + 2^{a−1} · 3^{L−a}) + 2^{a+1} (\frac{3^{L−a} + k}{2} ) .

Now either

g (2^{a+1} (\frac{3^{L−a} + k}{2} )) ≥ 2^{a−1} · 3^{L−a}

or

g (2^{a+1} (\frac{3^{L−a} + k}{2} )) < 2^{a−1} · 3^{L−a}.

In the former circumstance

g(n) ≥ 2^{a−1} · 3^{L−a}

≥ \frac{3}{4} · 2^{L}

= \frac{3}{4} · (3^{L})^{log 2/ log 3}

> \frac{3}{8} · n^{log 2/ log 3}

≥ \frac{3}{5} · n^{log 2/ log 5}

(using (3.1) and n ≥ 11 in the last two lines respectively). In the latter circumstance

g(n) ≥ 2^{a+1} · \frac{3}{5} (\frac{3^{L−a} + k}{2} )^{γ}

by the inductive hypothesis. To complete the proof, it is enough to show that

2^{a+1} ≥ (\frac{2 · (3^{L} + 2^{a} · k)}{3^{L−a} + k})^{γ}

(which combined with the above and (3.2) yields the result).

The right side is maximized at k = 1, so it is

≤ (\frac{2(3^{L} + 2^{a})}{3^{L−a} + 1})^{γ}

< (2 · 3^{a})^{γ}
< 2^{a+1}.

4. Non-uniqueness of representation with g(n)

Lastly, we show the counter-examples to Selfridge’s question. Let

n = 3^{b} + 11 · 2^{a}

with a ≥ 5, and

(4.1)  11 · 2^{a−3} < 3^{b} < 99 · 2^{a−6}.

For any given a, there are 0 or 1 values of b satisfying (4.1). However, for an infinite number of values of a, there exists a value of b satisfying (4.1). This is because it is equivalent to

\frac{log 11}{log 3} + (a − 3) · \frac{log 2}{log 3} < b < \frac{log 99}{log 3} + (a − 6) · \frac{log 2}{log 3},

or

\frac{log(64/33)}{log 3} < a · \frac{log 2}{log 3} − (b − 1) < \frac{log(24/11)}{log 3}.

Since the number log2/log3 is irrational, the fractional part of a·log2/log3 is thus dense in [0,1] and so lies between log(64/33)/log3 and log(24/11)/log3 for infinitely many values of n.

We will show that g(n) = 3^{b}. This will suffice since

\begin{matrix}n = 3^{b} + 3 · 2^{a} + 2^{a+3} \\ = 3^{b} + 9 · 2^{a} + 2^{a+1} \end{matrix}

and (4.1) implies that 3^{b} is the smallest term in both representations.

We must now demonstrate that there does not exist a representation of n with all its terms > 3^{b}. Suppose that such a representation exists. Since n is odd, any representation must have a term 3^{j}, and since (4.1) implies that n < 3^{b+2}, this representation must have the term 3^{b+1}. Thus it is in the form

n = 3^{b+1} + 2 · n_{1}

where

n_{1} = 11 · 2^{a−1} − 3^{b}.

Since n_{1} is odd, its corresponding representation has a term 3^{j}. Since n < 3^{b+2}, we have n_{1} < 3^{b+1}, and thus j ≤ b. If j were less than b, the corresponding term 2 · 3^{j} in the representation of n would contradict our assumption that all the terms in that representation are greater than 3^{b}. Following this same line of reasoning, the alleged representation unfolds as follows:

n = 3^{b+1} + 2 · 3^{b} + 4(11 · 2^{a−2} − 3^{b})
= 3^{b+1} + 2 · 3^{b} + 4 · 3^{b−1} + 16(11 · 2^{a−4} − 3^{b−1})
= 3^{b+1} + 2 · 3^{b} + 4 · 3^{b−1} + 16 · 3^{b−2} + 16(11 · 2^{a−4} − 4 · 3^{b−2}).

However

m =: 16(11 · 2^{a−4} − 4 · 3^{b−2})

= 11 · 2^{a} − \frac{64}{9} · 3^{b}

< 8 · 3^{b} − \frac{64}{9} · 3^{b}

= \frac{8}{9} · 3^{b},

and clearly m ≠ 0. This contradicts the assumption that all terms are > 3^{b}, and completes the proof.

References

1. P. Erdős, Problem Q814, Mathematics Magazine 67 (1994), 67,74.

2. P. Erdős and M. Lewin, d-Complete sequences of integers, Math. of Computation 65 (1996), 837–840.