% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{ Multiplicative Partitions}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 




\author{Marc Chamberland, Colin Johnson, Alice Nadeau, and Bingxi Wu \\
\small Department of Mathematics and Statistics\\[-0.8ex]
\small Grinnell College\\[-0.8ex] 
\small Grinnell, IA, U.S.A.\\
\small\tt chamberl@math.grinnell.edu\\
% \and
% Forgotten Second Author \qquad  Forgotten Third Author\\
% \small School of Hard Knocks\\[-0.8ex]
% \small University of Western Nowhere\\[-0.8ex]
% \small Nowhere, Australasiaopia\\
% \small\tt \{fsa,fta\}@uwn.edu.ao
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}



\date{\dateline{Dec 12, 2012}{June 10, 2013}\\
\small Mathematics Subject Classifications: 05A17, 11B99, 11M06, 11P82, 11N99}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
New formulas for the multiplicative partition function are developed. 
Besides giving a fast algorithm for generating these partitions,
new identities for additive partitions and the 
Riemann zeta function are also produced. 

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} 
Partitions, Riemann zeta function, sigma function, 
Gamma function, Selberg formula.

\end{abstract}





\section{Introduction} \label{sec-intro}
\setcounter{equation}{0}

A phenomenal amount of research has been conducted on the (additive) 
partition function over the last 100 years, with striking classical
results due to Hardy, Ramanujan, and others.
In contrast, the topic of multiplicative partitions
--- sometimes referred to as ``factorisatio numerorum" --- has
received little attention. Counting the number of multiplicative
partitions is a natural question since it lies between 
the two most common questions concerning primes: ``Is $n$ prime?" 
and ``What is the prime factorization of $n$?"

Let $a_n$ denote the number of multiplicative partitions
of the natural number $n$. For example, $a_{12} = 4$ since
$$
12 = 2\cdot 6 = 2\cdot 2\cdot 3 = 3 \cdot 4.
$$
The sequence $\{ a_n\}$ is listed in Sloane A001055.
The Dirichlet generating function for this sequence is
\begin{equation}
\label{eqn_gen_func}
f(s) = \prod_{k=2}^\infty \frac{1}{1-k^{-s} }
= \sum_{n=1}^\infty \frac{a_n}{n^s} .
\end{equation}
For special choices of $n$, the value of $a_n$ can be
determined in closed form. If $n=p^k$ where $p$ is a 
prime, then $a_n = p(k)$, the number of additive
partitions of the number $k$. If $n=p_1 p_2 \cdots p_k$,
a product of $k$ distinct primes, then $a_n = B(k)$, the 
$k^{th}$ Bell number. Lastly, it is important to note that
if $n=p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$
where $p_1,p_2,\cdots, p_k$ are distinct primes,
then $a_n$ depends only on $e_1, e_2, \ldots, e_k$.
More on multiplicative partitions, including 
results on bounds and asymptotics of $a_n$ and algorithms
for calculating the values, can be found in \cite{CAP},
\cite{Harris}, \cite{Knopfmacher}, and \cite{MD}.

The goal of this paper is to exploit the generating 
function (\ref{eqn_gen_func}) to determine new identities involving $a_n$.
One of the new formulas can be implemented recursively 
to perform quick calculations. Moreover, connections are 
made to additive partitions and the Riemann zeta function.

\section{ Generating Function}

It will be useful to consider the reciprocal of the
generating function $f(s)$. Define
$$
g(s) = \prod_{k=2}^\infty \left( 1-k^{-s} \right)
= \sum_{n=1}^\infty \frac{b_n}{n^s} .
$$
The product $f(s)g(s)$ produces 
\begin{equation}
\label{eqn_a_and_b_easy}
\sum_{d|n} a_d b_{n/d} = \delta_{n,1}
\end{equation}
where $\delta$ is the Kronecker delta function.
An important auxiliary sequence is defined as 
$m_n = \sigma(r)/r$ where 
$r=\gcd ( e_1, e_2, \ldots, e_k)$, 
$n= p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$,
and $\sigma$ is the sum of divisors function.
For example, $m_{36}=3/2$ since $36=2^2\cdot 3^2$.
We now offer several theorems which shed light on the 
generating function $f(s)$.

\begin{theorem}
If $\Re s >1$, then 
\begin{equation}
\label{eqn_log_f(s)}
\log f(s) = \sum_{n=2}^\infty \frac{m_n}{n^s}
\end{equation}
\end{theorem}

\begin{proof}

\begin{eqnarray*}
\log f(s) & = &
-\sum_{k=2}^\infty \log (1-k^{-s}) \\
& = & 
\sum_{k=2}^\infty \left( k^{-s} + \frac{k^{-2s}}{2}
+ \frac{k^{-3s}}{3} + \cdots \right) \\
& = & 
\frac{1}{2^s} + \frac{1}{3^s} + \frac{1}{4^s}\left( 1 + \frac{1}{2} \right) +
\frac{1}{5^s} + \frac{1}{6^s} + \frac{1}{7^s} \\
& & \mbox{\hspace{0.5in}} 
+ \frac{1}{8^s}\left( 1 + \frac{1}{3} \right) +
\frac{1}{9^s}\left( 1 + \frac{1}{2} \right) +
\frac{1}{{10}^s} + \cdots \\
& = &
\sum_{n=2}^\infty \left( \sum_{d|r} \frac{1}{d} \right) \frac{1}{n^s} \\
& = &
\sum_{n=2}^\infty \left( \frac{1}{r} \sum_{d|r} d \right) \frac{1}{n^s} \\
& = &
\sum_{n=2}^\infty \frac{m_n}{n^s} .
\end{eqnarray*}
\end{proof}

Equation (\ref{eqn_log_f(s)}) can be used to produce a more 
sophisticated relationship connecting 
$a_n$ and $b_n$ than equation (\ref{eqn_a_and_b_easy}). If $p$ is a prime, 
let $\nu_p (n)$ denote the number of powers of $p$ in the number $n$.


\begin{theorem}
\label{thm_nu}
For any prime $p$ and natural number $n$,
\begin{equation}
\label{eqn_nu_1}
\nu_p (n) m_n = 
\sum_{d|n} \nu_p (d) a_d b_{n/d}
\end{equation}
\end{theorem}

\begin{proof}

\begin{eqnarray*}
( \log f(s) )^\prime & = & f^\prime (s)\cdot \frac{1}{f(s)} \\
& = &
-\left( \sum_{n=2}^\infty \frac{a_n \log n}{n^s} \right)
\left( \sum_{n=1}^\infty \frac{b_n}{n^s} \right) \\
& = & 
-\sum_{n=2}^\infty \frac{1}{n^s} \sum_{d|n} (\log d) a_d b_{n/d} .
\end{eqnarray*}
Integrating with respect to $s$ and noting that the constant 
of integration must be zero by considering the terms as $s$ tends
to infinity, one finds 
$$
\log f(s) = 
\sum_{n=2}^\infty \frac{1}{n^s} \sum_{d|n} 
\left( \frac{\log d}{\log n} \right) a_d b_{n/d}  .
$$
Using equation (\ref{eqn_log_f(s)}), one has 
$$
(\log n) m_n  = \sum_{d|n} (\log d) a_d b_{n/d}  .
$$
Writing $n$ as its prime decomposition and applying 
$\nu_p$, the linear independence of any finite subset of 
$\{ \log(p):~$p$~\mbox{prime} \}$ implies
$$
\nu_p (n) m_n  = \sum_{d|n} \nu_p (d) a_d b_{n/d} .
$$

\end{proof}

There are now two formulas which relate $a_n$ and
$b_n$. For computational reasons, it would be useful to have 
a formula with only $a_n$ terms.

\begin{theorem}
For any prime $p$, one has 
\begin{equation}
\label{eqn_nu_2}
\nu_p (n) a_n = \sum_{d|n} \nu_p (d) m_d a_{n/d}
\end{equation}
\end{theorem}

\begin{proof}
The proof involves both convolution and deconvolution.
Starting with Theorem \ref{thm_nu},
\begin{eqnarray*}
\sum_{n=1}^\infty \frac{1}{n^s} \nu_p (n) m_n
& = & 
\sum_{n=1}^\infty \frac{1}{n^s} \sum_{d|n} \nu_p (d) a_d b_{n/d} \\
& = & 
\left( \sum_{n=1}^\infty \frac{\nu_p (n) a_n }{n^s}  \right)
\left( \sum_{n=1}^\infty \frac{b_n }{n^s} \right) \\
& = & 
\frac{1}{f(s)}
\sum_{n=1}^\infty \frac{\nu_p (n) a_n }{n^s}  .
\end{eqnarray*}
Rearranging, one has 
\begin{eqnarray*}
\sum_{n=1}^\infty \frac{\nu_p (n) a_n }{n^s} 
& = &
f(s) \sum_{n=1}^\infty \frac{1}{n^s} \nu_p (n)  m_n \\
& = &
\left( \sum_{n=1}^\infty \frac{a_n }{n^s} \right)
\left( \sum_{n=1}^\infty \frac{1}{n^s} \nu_p (n)  m_n \right) \\
& = &
\sum_{n=1}^\infty \frac{1}{n^s} 
\sum_{d|n} \nu_p (d) a_{n/d}  m_d  .
\end{eqnarray*}
Extracting the coefficients in the generating functions implies
$$
\nu_p (n) a_n = \sum_{d|n} \nu_p (d) m_d  a_{n/d} .
$$
\end{proof}



The generating function $f(s)$, particularly when written in product form, 
bears an obvious resemblance to the Riemann zeta function. 
With this in view, it is natural to look for parallels. 
The following result resembles the Selberg identity (see
\cite[p.46]{Apostol}).

\begin{theorem}
For any natural number $n$, 
\begin{equation}
\label{eqn_selberg}
m_n (\log n)^2 = 
\sum_{d|n} a_d b_{n/d} (\log d)^2
- \sum_{d|n} m_d m_{n/d} (\log d) (\log n/d )
\end{equation}
\end{theorem}

\begin{proof}

\begin{eqnarray*}
( \log f(s) )^{\prime\prime} & = & 
\frac{ f^{\prime\prime}(s) }{f(s)} 
- \left( \frac{f^\prime (s) }{f(s)} \right)^2 \\
& = & 
\left( \sum_{n=1}^\infty \frac{a_n (\log n)^2}{n^s} \right)
\left(\sum_{n=1}^\infty \frac{b_n}{n^s} \right)
-\left( \sum_{n=1}^\infty \frac{m_n \log n}{n^s} \right)^2 \\
& = & 
\sum_{n=1}^\infty \frac{1}{n^s}\sum_{d|n} a_d b_{n/d} (\log d)^2 
- \sum_{n=1}^\infty \frac{1}{n^s}\sum_{d|n} m_d m_{n/d} (\log d) (\log n/d) .
\end{eqnarray*}
Integrating with respect to $s$, noting the constants of integration
equal zero by considering the functions as $s$ approaches infinity,
and extracting coefficients in the power series yields
the desired result.
\end{proof}




\section{ Formulas for Additive Partitions}

It was noted earlier that if $n=p^k$ for some prime $k$,
then $a_n = p(k)$ where $p(k)$ is the number of 
additive partitions of the number $k$. While this paper's 
fundamental objective is to explore 
multiplicative partitions, the formulas of the last section
enable one to derive identities for the additive partition.

\begin{lemma}
\label{lemma}
If $n=p^k$ for some prime $p$, then $b_n = t_k$ where
$t_k$ is the coefficient of $x^k$ in the function
$\sum_{j=-\infty}^\infty (-1)^j x^{j(3j+1)/2} 
= \prod_{j=1}^\infty \left( 1-x^j \right) $.
\end{lemma}
\begin{proof}
Equation (\ref{eqn_a_and_b_easy}) can be written as 
$$
0 = \sum_{j=0}^k p(k-j) b_{p^j} .
$$
A basic result of additive partitions\cite{Andrews} states
$$
0 = \sum_{j=0}^\infty p(k-j) t_j .
$$
An inductive argument using these two equations proves
that $b_{p^j}=t_j$.
\end{proof}

\begin{theorem}
The following equations hold for all natural numbers $k$:
\begin{equation}
\label{eqn_add_1}
k\cdot p(k) = \sum_{j=1}^k \sigma(j)p(k-j)
\end{equation}
\begin{equation}
\label{eqn_add_2}
\sigma(k) = \sum_{j=1}^k j\cdot p(j)t_{k-j}
\end{equation}
\begin{equation}
\label{eqn_add_3}
k\cdot \sigma(k) = \sum_{j=1}^k j^2 p(j)t_{k-j}
- \sum_{j=1}^{k-1} \sigma(j) \sigma(k-j)
\end{equation}
\end{theorem}

\begin{proof}

Let $n=p^k$ for some prime $p$. This forces
$\nu_p (n) = k$ and $m_n = \sigma(k)/k$. Since the divisors of $n$ take 
the form $d=p^j$, $j=0,\ldots, k$, one has $\nu_p (d) = j$,
$a_d = p(j)$, and Lemma \ref{lemma} implies $b_{n/d} = t_{k-j}$.
Substituting these values into equations (\ref{eqn_nu_1}),
(\ref{eqn_nu_2}) and (\ref{eqn_selberg}), one produces the 
three desired equations.
\end{proof}

Equation (\ref{eqn_add_1}) is well-known in the 
theory of partitions, equation (\ref{eqn_add_2}) is
essentially derived in \cite{Osler}, while equation
(\ref{eqn_add_3}) appears to be new.


\section{ Connections to the Riemann zeta function }

The relationship between the generating functions
$f(s)$ and $\zeta (s)$ is more than just a meta comparison.
Let $\mu (n)$ denote the M\"obius function.

\begin{theorem}

If $\Re s > 1$, then 
\begin{equation}
\label{eqn_zeta}
\zeta (s) = 1 + \sum_{n=1}^\infty \frac{\mu(n)}{n}\log f(ns) .
\end{equation}

\end{theorem}

\begin{proof}

Starting with work seen in the proof of
equation (\ref{eqn_a_and_b_easy}), one has 
\begin{eqnarray*}
\log f(s) & = & \sum_{k=2}^\infty \sum_{n=1}^\infty \frac{1}{n\cdot (k^s)^n}\\
& = & 
\sum_{n=1}^\infty \frac{1}{n} ( \zeta(ns)-1 ).
\end{eqnarray*}
Applying M\"obius inversion concludes the proof.

\end{proof}

This new formula converges quickly. For large $s$, 
$$
\log f(ns) = \log \left( 1+ \frac{1}{2^{ns}} + \frac{1}{3^{ns}} + \cdots\right)
= \frac{1}{2^{ns}} + \cdots
$$
Comparing successive terms in equation (\ref{eqn_zeta}) --- assuming
the M\"obius function is non-zero --- their ratio approaches 
$1/2^s$ as $s\rightarrow\infty$. This implies that larger choices
of $s$ require fewer terms in the series to achieve the same accuracy.
The formulas usually used to compute approximations of
$\zeta(s)$ when $s$ is odd (see \cite{Cohen}) are due to Ramanujan and
the terms in the series have a ratio of $1/e^{2\pi}$.
The ratio from equation (\ref{eqn_zeta}) is smaller for $s>10$.
For an extensive article on computing $\zeta (s)$, see \cite{Borwein}.

Using equation (\ref{eqn_log_f(s)}), one can construct a formula
for $\zeta (s)$ which is independent of the multiplicative partitions:
\begin{eqnarray*}
\zeta (s) & = & 1 + \sum_{n=1}^\infty \frac{\mu(n)}{n}\log f(ns) \\
& = & 1 + \sum_{n=1}^\infty \frac{\mu(n)}{n}
\sum_{k=2}^\infty \frac{m_k}{k^{ns}} \\
& = & 1 + 
\sum_{k=2}^\infty m_k
\sum_{n=1}^\infty \frac{\mu(n)}{n} \frac{1}{k^{ns}}  .
\end{eqnarray*}

When $s>1$ is an integer, a closed form expression for $f(ns)$ can be found.
\begin{theorem}
\label{thm_gamma}
If $n>1$ is a natural number, then
$$
f(n) = \prod_{j=1}^{n-1} \Gamma(2-\omega^j)
$$
where $\Gamma (z)$ is the Gamma function and 
$\omega = \exp ( 2\pi i/n)$.
\end{theorem}

\begin{proof}
Starting with equation (\ref{eqn_gen_func}), 
repeated use of $\Gamma (x+1) = x\Gamma(x)$ produces
\begin{eqnarray*}
f(n) & = & 
\lim_{N\rightarrow\infty} \prod_{k=2}^N \frac{k^n}{k^n-1} \\
& = & \lim_{N\rightarrow\infty} \prod_{k=2}^N \prod_{j=1}^n 
\frac{k}{k-\omega^j} \\
& = & \lim_{N\rightarrow\infty} 
\prod_{j=1}^n 
\frac{ \Gamma(N+1)\Gamma(2-\omega^j)}{ \Gamma(N+1-\omega^j)} \\
& = & \prod_{j=1}^{n-1} \Gamma(2-\omega^j)
\lim_{N\rightarrow\infty} 
\prod_{j=1}^n 
\frac{ \Gamma(N+1)}{ \Gamma(N+1-\omega^j)} 
\end{eqnarray*}
To evaluate the limit, one uses the lesser-known identity \cite{AS}
$$
\lim_{n\rightarrow\infty} n^{b-a} \frac{\Gamma (n+a)}{\Gamma(n+b)} = 1 .
$$
Then 
\begin{eqnarray*}
\lim_{N\rightarrow\infty} 
\prod_{j=1}^n \frac{ \Gamma(N+1)}{ \Gamma(N+1-\omega^j)} 
& = & 
\lim_{N\rightarrow\infty} 
\left( \prod_{j=1}^n \frac{1}{N^{-\omega^j}}  \right)
\left( \prod_{j=1}^n \frac{ N^{-\omega^j} \Gamma(N+1)}
{ \Gamma(N+1-\omega^j)}  \right) \\
& = & 
\lim_{N\rightarrow\infty} 
\frac{1}{N^{-\omega - \omega^2 - \cdots - \omega^{n-1}-1}}\cdot 1 \\
& = & 1 .
\end{eqnarray*}
\end{proof}

When $s>1$ is an integer, Theorem \ref{thm_gamma} may be
used in conjunction with equation (\ref{eqn_zeta}) to yield
\begin{equation}
\zeta (s) = 1 + \sum_{n=1}^\infty \frac{\mu(n)}{n}
\sum_{j=1}^{ns-1} \log \Gamma(2-\omega^j) .
\end{equation}
where $\omega = \exp( 2\pi i/ns)$.


\section{ Numerical Explorations }

Values of $a_n$ for small $n$ can be found in Sloane A001055.
Hughs and Shallit\cite{HS} built a recursive formula for $a_n$ which
employs the finer multiplicative partitions $a_{n,m}$, the 
number of partitions of $n$ with all elements bounded by $m$.
This approach was programmed by Knopfmacher and Mays\cite{KM3} in Mathematica. 

Using equation \ref{eqn_nu_2}, we implemented a recursive
algorithm which appears significantly faster than the previous approach. 
Two important features in the implementation should be mentioned.
First, the recursive nature of this approach implies that the
procedure to calculate $a_n$ may be called many times for the 
same value of $n$, particularly if $n$ is small. To avoid 
this duplication in calculations, the procedures which calculate
$a_n$ and $m_n$ employed Maple's {\tt remember} option which caches
values and will not redo a calculation. Indeed, instead of 
using Maple's built-in function for $\nu_p (n)$, we constructed our
own which also caches the values. Secondly, we took advantage of
the observation that $a_n$ depends only on the exponents in the 
prime decomposition of $n$. To calculate $a_n$, the value of 
$n$ was replaced by the smallest number which had the same exponents
(for some $n$, the new value is no smaller).
These two features worked in tandem to blitz through the 
calculations: using Maple 14 on a Mac Book Pro, all the values 
of $a_n$ for $n<2,000,000$ were calculated in 141 CPU seconds.


As is evident from earlier formulas, an understanding of
the sequence $\{ a_n \}$ is bolstered by more insight into 
the sequence $\{b_n \}$. Continuing the metaphorical comparison
of $f(s)$ to the Riemann zeta function, one compares 
$b_n$ to the M\"obius function $\mu (n)$. Initial calculations
yield the following values for $b_n$:

\vspace{0.1in}

\begin{tabular}{||c|c|c|c|c|c|c|c|c|c|c|c||}
\hline 
Form of n & 1 & $p_1$ & $p_1^2$ & $p_1 p_2$ & $p_1^3$ & $p_1^2 p_2$ 
& $p_1 p_2 p_3$ & $p_1 ^4$ & $p_1^3 p_2$ & $p_1^2 p_2^2$ & $p_1^2 p_2 p_3$ \\ 
\hline
$b_n$ & 1 & -1 & -1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1  \\
\hline
\end{tabular}

\vspace{0.1in}

Just as the M\"obius function takes only the values $\{-1,0,1\}$,
the table suggests the values of $b_n$ are similarly restricted.
Lemma \ref{lemma} extends this list to infinitely many cases,
all with $b_n = \pm 1$. One more piece of evidence is 
of a combinatorial nature. Let $d_n^e$ denote the number of 
multiplicative partitions of $n$ into an even number of distinct parts and
$d_n^o$ the number of 
multiplicative partitions of $n$ into an odd number of distinct parts.
For example, since $12 = 2\cdot 6 = 2\cdot 2\cdot 3 = 3 \cdot 4$,
$d_{12}^e = 2$ and $d_{12}^0 = 1$.

\begin{theorem}
For all natural numbers $n$, $b_n = d_n^e - d_n^o$.
\end{theorem}

\begin{proof}

\begin{eqnarray*}
\sum_{n=1}^\infty \frac{b_n}{n^s} & = & 
\prod_{k=2}^\infty \left( 1-k^{-s}\right) \\
& = & 
\left( 1 - 2^{-s} \right) \left( 1 - 3^{-s} \right) 
\left( 1 - 4^{-s} \right) \cdots  \\
& = & 
% \left( 1 + 2^{-s}\cdot 3^{-s} + 2^{-s}\cdot 4^{-s} +
% 3^{-s}\cdot 4^{-s} + \cdots  \right)  \\
% & & ~~~~ 
% - \left( 2^{-s} + 3^{-s} + 4^{-s} 
% 2^{-s} \cdot  3^{-s} \cdot 4^{-s}  + \cdots \right)  \\
% & = & 
\sum_{n=1}^\infty \frac{d_n^e}{n^s} - \sum_{n=1}^\infty \frac{d_n^o}{n^s}  
\end{eqnarray*}

\end{proof}

Since one would expect a balance between the even and odd partitions, 
having $b_n\in\{-1,0,1\}$ seems reasonable. 
However, one finds (see \cite{KM2}) that $b_{360}=-2$. 
Indeed, using the two million values of $a_n$ which were computed with
equation (\ref{eqn_a_and_b_easy}) found wilder extremes:
the minimum value of $b_n$ is -29 and the maximum
value is 87. Alas, it seems the tight structure of the M\"obius 
function does not extend to $b_n$.

% Figure 1 shows shows all the values.
% 
% \begin{figure}
% % \begin{center}
% \centering
% \scalebox{.5}{
% \includegraphics[0in,0in][8in,10in]{b_n.eps}
% }
% % \end{center}
% \caption{First two million values of $b_n$.}
% \end{figure}
% 
% To emphasize how one can misjudge the behavior of $b_n$, Figures
% 2a and 2b display the function $\sum_{i|n} b_i$. Note that Figure 2a
% suggests the values $b_n$ (up to $n=500$) seem to grow steadily
% while Figure 2b suggests the opposite (up to $n=2,000,000$).
% 
% \begin{figure}
% % \begin{center}
% \centering
% \scalebox{.5}{
% \includegraphics[0in,0in][8in,10in]{sum_b_n_1.eps}
% \hspace{-3in}
% \includegraphics[0in,0in][8in,10in]{sum_b_n_2.eps}
% }
% % \end{center}
% \caption{First 500  and 2,000,000 values of $\sum_{i|n} b_i$.}
% \end{figure}
% 
% 
% % Ideas:
% % \begin{itemize}
% % \item
% % If one takes a large value for $n$, how many correct values
% % of $a_n$ can be constructed? To automate this comparison, one
% % needs to program the exact value of $a_n$. Comparing 
% % computation times may also be helpful.
% % 
% % \item
% % Since $a_n = n+1$ if and only if $n$ is a prime, can 
% % the theorem above give any insight into primes? 
% % Twin primes?
% % \end{itemize}
% 
% 



\subsection*{Acknowledgements}
Authors Johnson, Nadeau, and Wu are grateful to Grinnell College for
supporting them to work on this research with the first author during 
the summer of 2011. 


% \bibliographystyle{plain} 
% \bibliography{myBibFile} 
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file


\begin{thebibliography}{99}


\bibitem{Andrews}
Andrews,~G.E. and Eriksson,~K.
\newblock {\em Integer Partitions, 2nd edition}. 
\newblock Cambridge University Press, Cambridge, (1984).


\bibitem{Apostol}
Apostol,~T.M.
\newblock {\em Introduction to Analytic Number Theory}. 
\newblock Springer, New York, (1976).

\bibitem{AS}
Abramowitz,~M. and Stegun,~I.A.
\newblock {\em Handbook of Mathematical Functions}, ninth edition.
\newblock Dover, New York, (1972).

\bibitem{Borwein}
Borwein,~J., Bradley,~D.M. and Crandall,~R.
\newblock Computational strategies for the Riemann zeta function
\newblock {\em Journal of Computational and Applied Mathematics}, 
\underline{121}:247--296,(2000).

\bibitem{CAP}
Canfield,~R.E., Erd\H{o}s,~P. and Pomerance,~C. 
\newblock 
On a problem of Oppenheim concerning ``factorisatio numerorum”. 
\newblock {\em Journal of Number Theory}, 
\underline{17}:1--28,(1983).

\bibitem{Cohen}
Cohen,~H.
\newblock High precision computation of Hardy-Littlewood constants.
\newblock Preprint,
{\tt http://www.math.u-bordeaux1.fr/$\tilde{\mbox{ }}$hecohen/}.


\bibitem{Harris}
Harris,~V.C. and Subbarao,~M.V.
\newblock On product partitions of integers.
\newblock {\em Canadian Mathematical Bulletin}, 
\underline{34}(4):474--479,(1991).

\bibitem{HS}
Hughs,~J.F. and Shallit,~J.O.
\newblock On the Number of Multiplicative Partitions.
\newblock {\em American Mathematical Monthly}, 
\underline{90}(7):468--471,(1983).

\bibitem{Knopfmacher}
Knopfmacher,~A. and Mays,~M.E.
\newblock A survey of factorization counting functions.
\newblock {\em International Journal of Number Theory}, 
\underline{1}(4):563--581,(2005).

\bibitem{KM2}
Knopfmacher,~A. and Mays,~M.E.
\newblock Dirichlet generating functions and factorization identities.
\newblock 36th Southeastern International Conference on 
Combinatorics, Graph Theory, and Computing.
Congr. Numer. \underline{173}, 117–-127, (2005).

\bibitem{KM3}
Knopfmacher,~A. and Mays,~M.E.
\newblock Ordered and Unordered Factorizations of Integers.
\newblock {\em The Mathematica Journal},
\underline{10}(1), (2006).


\bibitem{MD}
Mattics,~L.E. and Dodd,~F.W.
\newblock Estimating the number of multiplicative partitions.
\newblock {\em Rocky Mountain Journal of Mathematics}, 
\underline{17}(4):797--813,(1987).

\bibitem{Osler}
Osler,~T.J., Hassen,~A., and Chandrupatla,~T.
\newblock 
Surprising Connections between Partitions and Divisors.
\newblock {\em College Mathematics Journal}, 
\underline{38}(4):277-287, (2007).



\end{thebibliography}










\end{document}
