\input amstex
\documentstyle{amsppt}
%\hsize6in
%\vsize9in
\magnification1200

\topmatter
\title
On primitive 3-smooth partitions of $n$
\endtitle
\author
Michael R. Avidon
\endauthor

\document

\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\H os and Selfridge.
\endabstract
\subjclass Primary 11P85, Secondary 05A17
\endsubjclass
\date {Submitted: September 30, 1996, Accepted: December 2, 1996} \enddate

\dedicatory {\it This paper is dedicated to Paul Erd\H os, on the sad occasion of his recent death.} \enddedicatory

\endtopmatter

\font\smcp=cmcsc8
\headline={\ifnum\pageno>1 {\smcp the electronic journal of  
combinatorics 4 (1997), \#R2\hfill\folio} \fi}

\head 0. Introduction
\endhead

Recently Erd\H os 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\ge 0$),
which are primitive (no summand divides another).  Determine
\medskip
\item{i.} the maximal order of $r(n)$,
\item{ii.} the average order of $r(n)$.
\medskip
It is easy to show that $r(n)\ge1$ for all $n$ (see[1],[2]).
In this paper partial results are obtained for both of these problems.  Specifically, we prove:

\proclaim{Theorem 1} For $n\ge5$, 
$$r(n)\le\frac{1}{2}\cdot n^\alpha,$$
where $\alpha=\log2/\log3 \ (\approx0.631)$.
\endproclaim

\proclaim{Theorem 2} Let $R(x)= \sum_{n\le x}  r(n)$.  Then
$$\frac{x^\beta}{(\log x)^{\beta+3/2}}\ll R(x) \ll \frac{x^\beta}{(\log x)^{3/2}}$$
where
$$\beta = \frac{1}{\log 3}\cdot\log (\frac{\log6}{\log2}) + \frac{1}{\log2}\cdot\log (\frac{\log6}{\log3} ) \ (\approx1.570).$$
\endproclaim

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\H os has asked if $\lim_{n
\to\infty} g(n) = \infty$.  We answer this in the affirmative by proving:

\proclaim{Theorem 3}  $g(n)\ge \frac{3}{5}\cdot n^\gamma$, where $\gamma = \frac{\log2}{\log5} (\approx0.431)$.
\endproclaim

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.

\head 1. Proof of theorem 1
\endhead

\proclaim{Lemma 1} $r(2^a 3^b m) = r(m)$
\endproclaim

\demo{Proof}
It is enough to show that $r(2m)=r(m)$ and $r(3m)=r(m)$.  There cannot exist a term $3^\beta$ 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^\alpha$ 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$.
\enddemo

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\ge0$.


Note that

$$r(n) = \sum^k_{j=0}r_j (n) .$$

Also define

$$s_j (n) = \sum^j_{i=0} r_i (n) ,$$
(so that $r(n) = s_j (n)$ for $j\ge k$).

\proclaim{Lemma 2} For $n \ge 5$, and $i=1,2,...,k$
$$s_i (n) \le 2^{i-1} .$$
\endproclaim
\noindent [Note that $s_0 (n) = r_0 (n) = 0$ if $n \not=1$, and is 1 if $n=1$.]

\demo{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 \le 2^0 .$$
Now assume for all $m<n$ and $i = 1,2,..., k=k(m)$ that
$$s_i (m) \le 2^{i-1} .$$
It is easy to see that, for $j\ge2$,
$$r_j (n) = s_{j-1} \left ( \frac{n-3^j}{2^{a_j}}  \right )$$
where $a_j$ is defined by $2^{a_j} || n-3^j$.
Therefore, from the inductive hypothesis, we deduce that for $j\ge2$
$$r_j (n) \le 2^{j-2} .$$
Thus, for $n\ge5$ and $i\ge2$
$$s_i (n) = \sum^i_{j=1}r_j (n)\le1+\sum^i_{j=2}2^{j-2} =2^{i-1}.$$
This completes the proof of the lemma.
\enddemo

The above lemma yields
$$r(n) = s_k (n)\le2^{k-1}\le\frac{1}{2}\cdot2^{\log_3 (n)}=\frac{1}{2}\cdot n^\alpha$$
which completes the proof of Theorem 1.

\head 2. Proof of theorem 2
\endhead

\def\BB{\item{$\bullet$}}

We introduce the following notation:
\smallskip

\BB $\sum^*$ indicates a sum over numbers prime to 6,

\BB $R^* (x) = \sum^*_{n\le x} r(n)$,

\BB $S (x) =$ the number of primitive sums $\sum 2^a 3^b = n$ with each term $2^a 3^b \le x$ and $(n,6)=1$,

\BB $S_j (x) =$ the number of sums described above that have the summand $3^j$,

\BB $\alpha = \frac{\log2}{\log3}$.
\medskip

For any $x\ge3$, there exists $L\in{\Bbb N}$ such that $3^L \le x < 3^{L+1}$.  Obviously, if we prove the theorem for $x = 3^L$, the general result
will follow from $R(3^L ) \le R(x) \le R(3^{L+1})$.  Therefore, we henceforth assume that $x = 3^L$.

Note that every $n \le x$ can be uniquely written as $n = 2^a 3^b m$ with $(m,6)=1$, and $m\le x/2^a 3^b$.  Since $r(n)=r(m)$, by lemma 1,
it follows that
$$R(x) = \sum_{\scriptstyle {a,b\ge0} \atop \scriptstyle {2^a 3^b\le x}}R^* \left ( \frac{x}{2^a 3^b} \right ) .$$

Using this fact, the theorem will follow once we prove, for $x\ge2$,

$$\frac{x^\beta}{(\log x)^{\beta+3/2}} \ll R^* (x) \ll \frac{x^\beta}{(\log x)^{3/2}} . \tag2.1$$

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

$$\eqalign{R(x) \ll \sum_{2^a 3^b\le\sqrt{x}} \left ( \frac{x}{2^a 3^b} \right ) ^\beta \cdot (\log x)^{-3/2} + \sum_{\sqrt{x}<2^a\cdot3^b\le x} x^{\beta/2} \cr \ll x^\beta\cdot (\log x)^{-3/2} + \log ^2 x\cdot x^{\beta/2} \cr \ll x^\beta \cdot (\log x)^{-3/2} .\cr}$$

Consider $S(x/L)$.  This counts primitive sums $\sum 2^a 3^b$ with $2^a 3^b \le x/L$.  Then $b\le L-1$, and we have at most $L$ terms.
Thus, it follows from the definitions that

$$S \left ( \frac{x}{L} \right ) \le R^* (x) \le S(x).$$

This will imply (2.1) once we prove:

$$S(x) \asymp  (\log x)^{-3/2}\cdot x^\beta ,$$
and this would follow from

$$S(x) \asymp \frac{1}{L}\cdot {[L/\alpha ] + L \choose L} , \tag2.2$$
since, by Stirling's formula, the binomial coefficient above equals

$$\exp\{ ([L/\alpha]+L+1/2)\log([L/\alpha]+L) - (L+1/2)\log L - ([L/\alpha]+1/2)\log([L/\alpha]) + O(1) \}$$

$$= \exp\{ [L/\alpha]\cdot\log (1+\alpha) + L\cdot\log (1+1/\alpha) - 1/2\cdot\log L + O(1) \}$$

$$\asymp  x^\beta\cdot (\log x)^{-1/2} . $$

It is easy to see that

$$S \left ( \frac{x}{3} \right ) \le 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

$$S_L (x) \asymp \frac{1}{L}\cdot {[L/\alpha] + L \choose L} . \tag2.3$$

We now establish a recursive formula for the $S_j$ and use it to prove (2.3).
\medskip

The sums counted by $S_j (x)$ can all be written in the form

$$3^j + 2^l\cdot(3^i + ...) \,$$
where $0 \le i \le j-1$, and $1 \le l \le [(L-i)/\alpha]$.  If $0 \le i \le 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

$$S_j (x) = \sum^{[(L-j+1)/\alpha]}_{l=0} S_{j-1} \left ( \frac {x}{2^l} \right ) . \tag2.4$$

In particular

$$S_L (x) = S_{L-1} (x) + S_{L-1} \left ( \frac{x}{2} \right ) .$$

We can generalize this to a relationship of the form

$$S_L (x) = \sum^{[j/\alpha]}_{l=0} A_j (l)\cdot S_{L-j} \left ( \frac{x}{2^l} \right ) \, \tag2.5$$
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+\lambda})$ have $3^{L-j-1} \le 3^L
/2^{l+\lambda}$, which implies $\lambda \le [(j+1)/\alpha] - l$.  Now if we combine the above with (2.4) we obtain

$$\eqalign{S_L (x) = \sum^{[j/\alpha]}_{l=0} A_j (l)\sum^{\left [ \frac{j+1}{\alpha} \right ] -l}_{\lambda =0} S_{L-j-1} \left (
\frac{x}{2^{l+\lambda}} \right ) \cr = \sum^{\left [ \frac{j+1}{\alpha} \right ]}_{m=0} S_{L-j-1} \left ( \frac{x}{2^m} \right ) \sum^{\min (m,
\left [ \frac{j}{\alpha} \right ] )}_{l=0} A_j (l) , \cr}$$
so we conclude

$$A_{j+1} (m) = \sum^{\min (m,[j/\alpha])}_{l=0} A_j (l) . \tag2.6$$

It is trivially true that $S_0 (x) =1$ for $x\ge1$, so with $j=L$, (2.5) yields

$$S_L (x) = \sum^{[L/\alpha]}_{l=0} A_L (l) . \tag2.7$$

Now let $B_j (l) = {l+j \choose l} - \alpha \cdot {l+j \choose l-1}$ (with the conventions that ${0 \choose 0} =1$ and ${n \choose -1} =0$).
\medskip

\underbar{Claim}:  $B_{j-1} (l) \le A_j (l) \le B_{j+1} (l)$.
\medskip

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

$$\sum^m_{l=0} B_j (l) = B_{j+1} (m) . \tag2.8$$

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

$$B_L ([L/\alpha]) \le S_L (x) \le B_{L+2} ([L/\alpha]).$$

This is the same as

$${[L/\alpha]+L \choose [L/\alpha] } \cdot \left ( 1 - \alpha \cdot \frac{[L/\alpha]}{L+1} \right )  \le  S_L (x)  \le  {[L/\alpha]+L+2  \choose [L/\alpha
] }  \cdot  \left ( 1 - \alpha \cdot \frac{[L/\alpha]}{L+3} \right ) $$
and (2.3) follows at once.
\medskip

\underbar{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\ge1$ and $0\le l \le [j/\alpha]$.  Suppose first that $0\le m \le [j/\alpha]$.  Summing the
inequalities over $l\in [0,m]$, applying (2.6) and (2.8) yields the corresponding inequalities for $A_{j+1} (m)$.

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

$$B_j ([j/\alpha]) \le A_{j+1} (m) \le B_{j+2} ([j/\alpha]) .$$

The proof of the claim will be complete if we show
\smallskip

(i)  $B_{j+2} ([j/\alpha]) < B_{j+2} ([j/\alpha]+1) < B_{j+2} ([j/\alpha]+2)$

\noindent and

(ii) $B_j ([j/\alpha]) > B_j ([j/\alpha]+1) > B_j ([j/\alpha]+2)$.
\smallskip

Towards this, note that for $i = 1$ or 2, and $j\in{\Bbb N}$,

$$\alpha \cdot \frac{1}{j+2} < \frac{1}{[j/\alpha]+i} < \alpha \cdot \frac{1}{j} .$$

These two inequalities respectively imply

$$B_{j+1} ([j/\alpha]+i) > 0$$
and
$$B_{j-1} ([j/\alpha]+i) < 0 .$$

Noting that ${n \choose k} = {n+1 \choose k+1} - {n \choose 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.

\head 3. Proof of theorem 3
\endhead

Since $g(2^a 3^b n) = 2^a 3^b \cdot 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^L < n < 3^{L+1} ,\    L\ge2 \tag3.1$$ 
so that
$$n = 3^L + 2^a k , \quad a\ge1, k\equiv1(2), k<3^L . \tag3.2$$     

Evidently
$$g(n) \ge \min (3^L , 2^a \cdot g(k)) .$$

If $g(n) \ge3^L$, then $g(n) > n/3$ and the theorem holds.  Otherwise

$$g(n) \ge 2^a \cdot \frac{3}{5} \cdot k^\gamma$$

by the inductive hypothesis.
\medskip

\noindent Case I:  $k \ge 3^{L-a}$
\smallskip
We wish to show that
$$2^a \cdot k^\gamma \ge n^\gamma$$
or
$$k \ge \frac{n}{2^{a/\gamma}} = \frac{3^L +2^a \cdot k}{2^{a/\gamma}} $$
or
$$k \ge \frac{3^L}{2^{a/\gamma} -2^a} .$$

Thus it is enough to have
$$3^{L-a} \ge \frac{3^L}{2^{a/\gamma} -2^a}$$
or
$$\gamma \le \min_{a\ge1} \frac{a \cdot \log2}{\log (3^a +2^a)} = \frac{\log2}{\log5} ,$$
so the theorem holds.
Note that if $a \ge L$, we certainly have $k \ge 3^{L-a}$, so that in particular the theorem holds in that situation.
\medskip
\noindent Case II:  $k<3^{L-a}$ and $1 \le a \le L-1$
\smallskip
 From (3.2):
$$n = (3^L - 3^L \cdot (2/3)^a ) + (2^a \cdot 3^{L-a} + 2^a \cdot k)$$
$$=(3^{L-1} + 2 \cdot 3^{L-2} + 2^2 \cdot 3^{L-3} + ... +
2^{a-1} \cdot 3^{L-a} ) + 2^{a+1} \left ( \frac{3^{L-a} +k}{2} \right ) .$$
Now either
$$g \left ( 2^{a+1} \left ( \frac{3^{L-a} +k}{2} \right ) \right ) \ge 2^{a-1} \cdot 3^{L-a}$$
or
$$g \left ( 2^{a+1} \left ( \frac{3^{L-a} +k}{2} \right ) \right ) < 2^{a-1} \cdot 3^{L-a} .$$
In the former circumstance
$$\eqalign{g(n) \ge 2^{a-1} \cdot 3^{L-a} \cr \ge \frac{3}{4} \cdot 2^L \cr = \frac{3}{4} \cdot (3^L )^{\log2/\log3} \cr > \frac{3}{8} \cdot
n^{\log2/\log3} \cr \ge \frac {3}{5} \cdot n^{\log2/\log5} \cr}$$
(using (3.1) and $n \ge11$ in the last two lines respectively).  In the latter circumstance
$$g(n) \ge 2^{a+1} \cdot \frac{3}{5} \left ( \frac{3^{L-a} +k}{2} \right ) ^\gamma$$
by the inductive hypothesis.
To complete the proof, it is enough to show that
$$2^{a+1} \ge \left ( \frac{2 \cdot (3^L +2^a \cdot k)}{3^{L-a} +k} \right ) ^\gamma$$
(which combined with the above and (3.2) yields the result).

The right side is maximized at $k=1$, so it is
$$\eqalign{\le \left ( \frac{2(3^L +2^a )}{3^{L-a} +1} \right ) ^\gamma \cr < (2 \cdot 3^a )^\gamma \cr < 2^{a+1} . \cr}$$

\head 4. Non-uniqueness of representation with $g(n)$
\endhead

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

$$n = 3^b + 11 \cdot 2^a$$
with $a \ge5$, and

$$11 \cdot 2^{a-3} < 3^b < 99 \cdot 2^{a-6} . \tag4.1$$

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{\log11}{\log3} + (a-3) \cdot \frac{\log2}{\log3} < b < \frac{\log99}{\log3} + (a-6) \cdot \frac{\log2}{\log3} ,$$
or
$$\frac{\log (64/33)}{\log3} < a \cdot \frac{\log2}{\log3} - (b-1) < \frac{\log (24/11)}{\log3} .$$
Since the number log2/log3 is irrational, the fractional part of $a \cdot$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

$$\eqalign{n = 3^b + 3 \cdot 2^a + 2^{a+3} \cr =3^b + 9 \cdot 2^a + 2^{a+1} \cr}$$
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 \cdot n_1$$
where
$$n_1 = 11 \cdot 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 \le b$.  If $j$ were less than $b$, the corresponding term $2 \cdot 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 \cdot 3^b + 4(11 \cdot 2^{a-2} -3^b )$$
$$=3^{b+1} +2 \cdot 3^b + 4 \cdot 3^{b-1} +16(11 \cdot 2^{a-4} - 3^{b-1} )$$
$$= 3^{b+1} + 2 \cdot 3^b + 4 \cdot 3^{b-1} + 16 \cdot 3^{b-2} + 16(11 \cdot 2^{a-4} - 4 \cdot 3^{b-2} ) .$$

However
$$\eqalign{m =: 16(11 \cdot 2^{a-4} - 4 \cdot 3^{b-2} ) \cr = 11 \cdot 2^a - \frac{64}{9} \cdot 3^b \cr < 8 \cdot 3^b - \frac{64}{9} \cdot 3^b
\cr = \frac{8}{9} \cdot 3^b ,  \cr}$$
and clearly $m \not= 0$.  This contradicts the assumption that all terms are $> 3^b$, and completes the proof.

\Refs

\ref \no 1
\by P. Erd\H os
\paper Problem Q814
\jour Mathematics Magazine
\vol 67
\yr 1994
\pages 67,74
\endref

\ref \no 2
\by P. Erd\H os and M. Lewin
\paper d-Complete sequences of integers
\jour Math. of Computation
\vol 65
\yr 1996
\pages 837--840
\endref

\endRefs


\enddocument