0
$\begingroup$

I am trying to solve the following problem: I have an ordered list of integers $L = \{v_1,\ldots ,v_{14}\}$ with fourteen elements, satisfying the following two conditions: $v_i \geq v_{i+1}\geq 0$ and $\sum _{i=1}^{14}(v_i) \leq 54$. So in particular every $0\leq v_i \leq 54$. How many different lists $L$ satisfying the conditions exists? Here is some background on the problem.

I am trying to solve something on the computer that boils down to the following problem: find the minimum number $n=p_1^{v_1}\cdot \ldots \cdot p_{k}^{v_k}$ (its prime factorization) such that $S(n)=\frac12\left(\prod _{i=1}^{k}(2v_i+1)+1\right)>1000000$. Now by the fact that $n$ is minimum we see that $v_i \geq v_{i+1}$. If not we would have something like $n = 2\cdot 3^2$ but $S(2\cdot 3^2) = S(2^2 \cdot 3)$ so if some $v_{i} \leq v_{i+1}$ we have not minimized $n$.

Now if we set all $v_i =1$ we get $n=p_1\cdot \ldots \cdot p_k$ and $S(n)=\frac12(3^k+1)>1000000$ or equivalently $3^k \geq 20000000 $ so that $k \geq \log_{3}(2000000) \approx 13.2$. So that for every number $n$ with a prime factorization of at least $14$ distinct primes we see that $S(n) > 1000000$. So, in order to minimize $n$ we look for a number $n$ that has a prime factorization of at most $14$ primes to some power. Also we see that $n$ has a prime factorization that includes not 14 random primes, but the first 14 primes. This is because we can swap primes in the factorization without changing $S(n)$ but this will change $n$, so we choose the smallest primes to minimize $n$. This is the reason the list has $14$ elements.

Now by the minimization of $n$ we see that our minimal $n$ is either equal to or smaller than $p_1\cdot p_2\cdot \ldots p_{14} = 2\cdot 3\cdot \ldots \cdot 43 \approx 1.3\cdot 10^{16}$. Also, for any $n$ we have $n = p_1^{v_1}\cdot \ldots \cdot p_{14}^{v_{14}}> 2^{\sum v_{i}}$ so that again by the minimization of $n$ we have $2^{\sum v_{i}} \leq 1.3\cdot 10^{16}$ implying that $\sum v_i \leq \log_2( 1.3\cdot 10^{16})\approx 53.5$. Thus $\sum v_i \leq 54$.

Thus we have set up the conditions specified at the beginning. Now this is as far as I got, I tried to look at the list $L$ as number base $55$ but this hasn't helped much. Also, I fear that the amount of possible lists is enormous but I am not sure. I am looking for a way to see how many there are and possible an algorithm to generate them in succession. Thanks in advance for any tips or help!

$\endgroup$
1
$\begingroup$

We consider a smaller case: $x_1 + x_2 + x_3 \le 5$. We look at all the of partitions of $1, 2, 3, 4, 5$ into at most $3$ parts. The possible partitions are:

1 = 1            (1, 0, 0)
2 = 2            (2, 0, 0)
  = 1 + 1        (1, 1, 0)
3 = 3            (3, 0, 0)
  = 2 + 1        (2, 1, 0)
  = 1 + 1 + 1    (1, 1, 1)
4 = 4            (4, 0, 0)
  = 3 + 1        (3, 1, 0)
  = 2 + 2        (2, 2, 0)
  = 2 + 1 + 1    (2, 1, 0)
5 = 5            (5, 0, 0)
  = 4 + 1        (4, 1, 0)
  = 3 + 2        (3, 2, 0)
  = 3 + 1 + 1    (3, 1, 1)
  = 2 + 2 + 1    (2, 2, 1)

Each of these partitions corresponding to an ordered solution for $(x_1, x_2, x_3)$. They also represent all the solutions that exist.


Essentially, what we're looking for in the context of the question is the total number of ways to partition $n$ into at most $14$ parts for $0 \le n \le 54$.

Define the number of ways to partition $n$ into $k$ parts as $p_k(n)$. Then, we need

$$\sum_{n = 0}^{54}\sum_{k = 0}^{14}p_k(n)$$

where $p_0(0) = 1$ and $p_k(n) = 0$ if either $k \le 0$ or $n \le 0$. From this link on Wikipedia, we have the following recurrence relation for $p_k(n)$:

$$p_k(n) = p_k(n-k) + p_{k-1}(n-1)$$

Below is a PARI-GP script that computes the required number of list using the aforementioned method:

partition(n, k) =
{
    if(n == 0 && k == 0, 
        1,
        if(n <= 0 || k <= 0,
            0,
            partition(n - k, k) + partition(n - 1, k - 1)
        )
    )
}

total = 0;
for(n = 0, 54, for(k = 0, 14, total += partition(n, k)));
print(total);

The script gives $1627035$ as the required number of lists.

$\endgroup$

Your Answer

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

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