% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P57}{20(2)}{2013} % 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{\vskip-40pt \bf 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 13, 2012}{Jun 11, 2013}{Jun 21, 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 % 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} $\;$ \quad \phantom{ Why? } \vskip-20pt \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 \bigg( \sum_{{d|r}} \frac{1}{d} \bigg) \frac{1}{n^s} \\ & = & \sum_{n=2}^\infty \bigg( \frac{1}{r} \sum_{{d|r}} d \bigg) \frac{1}{n^s} \\ & = & \sum_{n=2}^\infty \frac{m_n}{n^s}. \end{eqnarray*} \vskip-20pt \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 \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}