3
$\begingroup$

Consider integer partitions of $x \in \mathbb{N}$ of size $k$ under the constraint that the partition elements are distinct and the ratio of any element to each smaller element is a natural number.

Example $f(x,k)$:

  • $f(17,3) = \{ 1, 4, 12\}$
  • $f(14,3) = \{ 2, 4, 8 \}$
  • $f(101,4) = \{ 1, 2, 14, 84 \}$
  • $f(4,3) = \emptyset$

As pointed out by @Henrik, one can express one constraint as: $x = a_1 + a_1 a_2 + \ldots + a_1\cdots a_k$ and then factor $x$, $x-a_1$, $x - a_1 - a_1 a_2$, etc. to find candidates for successive $a_i$. (In the special case of $x$ being prime and $k>1$, then $a_1 = 1$.) However, because there are typically several choices for each successive $a_i$, perhaps one must use some sophisticated search (with backtracking) or variant on linear programming.

Have these partitions (or series) been studied? Is there an efficient algorithm or method for finding them, given $x$ and $k$? When might $f(x,k)$ be empty or not unique?

Influenced by the comment from @Gerhard "always has a clever middle name" Paseman, I thought I'd plot candidates for the case $f(28,2)$. The abscissa is $a_1$ (whose value must be a factor of $28$, i.e., $1, 2, 4, 7, 14, 28$), and the ordinate $a_1 a_2$. Because $a_1 + a_1 a_2$ must ultimately equal $n = 28$, we need consider the smallest partition in the range $0 < a_1 \leq \lfloor {n \over k+1} \rfloor = 9$ (marked by the non-gray region). Because the $a_2 \geq 2$, the region of candidates for $a_1 a_2$ must be $\geq 2 a_1$, as shown in yellow.

Thus we seek a point $(a_1, a_1 a_2)$ on the line $a_1 + a_1 a_2 = n$, as shown by the black line.

For this case, the only solution is $(1, 27)$.

I'm not quite sure how this helps in finding an efficient algorithm, but my problem-solving style is to visualize or graph as much as possible, so perhaps this will shed light for someone else.

Integer partition candidates for f(28,2)

Here's a table of candidates for $f(25,3)$, showing there are four solutions: $\{ 1, 6, 18\}$, $\{ 1, 2, 22\}$, $\{ 1, 4, 20\}$, $\{ 1, 8, 16 \}$. (Actually, we can eliminate the case $a_1 = 5$ a priori, but I include it for completeness.)

$$ \begin{array}{|r|c|l|} \hline a_1 & a_1 a_2 & a_1 a_2 a_3 \\ \hline 1 & 2 & 4,8, 12, 16, 20, {\bf 22} \\ & 4 & 8, 12, 16, {\bf 20} \\ & 6 & 12, {\bf 18} \\ & 8 & {\bf 16} \\ \hline 5 & 10 & 20 \\ \hline \end{array} $$

$\endgroup$
  • $\begingroup$ Perhaps analyze the case k=2 and describe all of those, and then use that to understand the case k=3. There may be an alternate characterization which allows you to avoid much backtracking. Gerhard "Don't Go Far On Branch" Paseman, 2018.11.16. $\endgroup$ – Gerhard Paseman Nov 16 '18 at 22:02
  • 2
    $\begingroup$ $k=2$ is just the pure factoring problem. So I'm not sure how efficient it can be... $\endgroup$ – fedja Nov 16 '18 at 22:36
  • $\begingroup$ @fedja Maybe not possible to efficiently get the exact value, but getting estimates from $\sum_{x} f(x,2) y^x = \sum \sigma_0 (n) y^n$ or analogous for $k \neq 2$. $\endgroup$ – AHusain Nov 16 '18 at 22:46
  • 1
    $\begingroup$ One of us is not understanding the situation. For f(25,3) I get 4,20 and 2,22 as continuations. For f(28,2), any divisor of 28 less than 28/3 can be a first candidate. The idea was to use k=2 to simplify analysis, as f(n,3) is a , af(n/a,2) over all appropriate divisors a of n. Gerhard "Need To Avoid Prime Quotients" Paseman, 2018.11.16. $\endgroup$ – Gerhard Paseman Nov 17 '18 at 1:18
  • $\begingroup$ @GerhardPaseman: Oops... I didn't continue my list far enough to find the cases you gave. (Thanks.) . There might indeed be some recursive method as you suggest. I'll go back to thinking about it. $\endgroup$ – David G. Stork Nov 17 '18 at 1:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.