3
$\begingroup$

Edit [2023 Dec 7]: One of my specific wonders, along with that of students, is around when a recursive formula might have – or be expected to have – an explicit or closed formula. What is the mathematical intuition or relevant theorem around the existence of such formulae, and how would that apply to this specific example?


The following question concerns a natural generalization of the following problem and, as relevant, a wonder around when a recursive formula can/not be written in an explicit form:

enter image description here

In exploring this problem, (secondary school) students and I generated enough examples of prime structures to find the following, relevant paper:

Miller, Michael D. "A Recursively Defined Divisor Function." The Fibonacci Quarterly, 13(3), pages 199-204. Accessible at https://www.fq.math.ca/Scanned/13-3/miller.pdf.

Define $\gamma: \mathbb{Z}^+ \rightarrow \mathbb{Z}^+$ by $\gamma(1) = 1$ and, for $N > 1$, let $\gamma(N)$ be the total number of ones in $N$'s factor family.

Question: For $N$ with prime factorization $\prod_i p_i^{\alpha_i}$, what is an explicit formula for $\gamma(N)$? If an explicit formula cannot be written for this function, then what is the barrier – articulated "rigorously" or heuristically – preventing it from being written as such?

Theorem 4 in the linked paper gives a recursive method for computing $\gamma(N)$, but, in the paper's own words:

This theorem, although giving much information about the nature of the function $\gamma$, does not explicitly give us a formula from which we can calculate $\gamma(N)$ for various values of $N$ (page 201).

Hence the question above. Re-tagging and pointers to other references are all welcome!

$\endgroup$

3 Answers 3

6
$\begingroup$

This seems to be Sloane's A002033, namely the number of perfect partitions of $n-1$. Since the OEIS doesn't give any closed formula, there probably isn't one, but it's probably worth checking the references pointed to there.

$\endgroup$
2
  • 1
    $\begingroup$ See also A074206. $\endgroup$ Dec 6, 2023 at 21:51
  • 1
    $\begingroup$ Interesting that A074206 is a separate OEIS entry... we missed both entries by not simply listing out the totals for 1, 2, 3, etc. Thanks for the reference pointer! $\endgroup$ Dec 7, 2023 at 19:22
5
$\begingroup$

Take the formal product $g(x_1,x_2,\ldots)=\prod_{i\ge 1} (1-x_i)$ and define $$f(x_1,x_2,\ldots) = \frac{g(x_1,x_2,\ldots)}{2g(x_1,x_2,\ldots)-1}.$$ Then $\gamma(\prod_i p_i^{\alpha_i})$ is the coefficient of $\prod_i x_i^{\alpha_i}$ in the Taylor expansion of $f(x_1,x_2,\ldots)$.

This is elementary and I don't see how it gives an "explicit" formula except in simple cases.

$\endgroup$
1
  • $\begingroup$ Is there a way (formal theorem/criterion or informal intuition/heuristic) to determine whether a closed formula exists? $\endgroup$ Dec 7, 2023 at 19:20
5
$\begingroup$

A simple generating function, though not a closed formula, for $\gamma(N)$ is given by $\sum_{N\geq 1}\frac{\gamma(N)}{N^s} = \frac{1}{2-\zeta(s)}$, where $\zeta(s)$ is the Riemann zeta function. See e.g. page 7 of E. C. Titchmarsh, The Zeta Function of Riemann.

$\endgroup$
1
  • $\begingroup$ Very cool. This connection allowed me to find Ordered Factorization as a term that connects your answer with Dave Benson's latter OEIS link. Is there some way to see from this, even if it's just heuristic, why there might not be a closed formula? $\endgroup$ Dec 7, 2023 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.