0
$\begingroup$

Let $p_i$ be the $i^{\rm th}$ prime number (i.e. $p_1=2,\ p_2=3,\ p_3=5,\cdots$)

What is the function of number of combinations of $c_1,\cdots,c_n$ in terms of $n$ such that,

$$\sum_{i=1}^{n}c_ip_i\ =\ \sum_{i=1}^{n}p_i\quad {\rm where}\ c_i \in \{0,\cdots,n\}\ {\rm and}\ \sum_{i=1}^{n}c_i = n$$

For example, a combination of $c_1..c_4$ for $n=4$ is $c_1=1, c_2=0, c_3=3, c_4=0$, because,

$$\sum_{i=1}^{4}c_ip_i\ =\ 1\times 2\ +\ 0\times 3\ +\ 3\times 5\ +\ 0\times 7 = 17\ \ \ \ \&$$

$$\sum_{i=1}^{4}p_i\ =\ 2\ +\ 3\ +\ 5\ +\ 7 = 17\ \ \ \ \&$$

$$ \sum_{i=1}^{4}c_i\ =\ 1\ +\ 0\ +\ 3\ +\ 0 = 4$$

Improve this question
$\endgroup$
5
  • $\begingroup$ What kind of answer you are looking for? Most likely, there is no simple expression for this function. $\endgroup$
    – Max Alekseyev
    Commented Sep 25 at 12:09
  • $\begingroup$ An asymptotic tight bound on the function would be very helpful ! $\endgroup$
    – yash vinayvanshi
    Commented Sep 25 at 14:46
  • 1
    $\begingroup$ It's not clear to me what you're asking. Obviously $c_i=1$ is a solution. So for $n=4$ is $2$ the result you're looking for? $\endgroup$
    – Steven Clark
    Commented Sep 25 at 15:05
  • $\begingroup$ You are right, $c_i = 1$ is the solution for any $n$ and indeed for $n=4$, only two combinations exist, $c_1=1,\ c_2=1,\ c_3=1,\ c_4=1\ \&\ c_1=1,\ c_2=0,\ c_3=3,\ c_4=0$. The sequence of number of such combinations starting from $n=1$ is $<1,1,1,2,5,...>$. I am curious about how this sequence grows asymptotically in terms of $n$. $\endgroup$
    – yash vinayvanshi
    Commented Sep 25 at 16:10
  • $\begingroup$ Have you computed this for all $n$ up to, say, $100$, to get some idea of the growth rate? or even up to $n=10$, to look it up at the Online Encyclopedia of Integer Sequences? $\endgroup$
    – Gerry Myerson
    Commented Sep 26 at 1:02

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .