product of exactly $50$ primes if the only prime factors we can use are $2,3,5,7$. [closed]
$begingroup$
To find the number of positive integers that can be written as a product of exactly $50$ primes if the only prime factors we can use are $2,3,5,7$.
The product of $50$ primes means that $n = p_1 times p_2 timescdots times p_{50}$, here are repetions allowed.
combinatorics number-theory prime-numbers recreational-mathematics
asked Jan 25 at 23:20
user8795user8795
5,73162047
$endgroup$
closed as unclear what you're asking by Rob Arthan, Cesareo, Gibbs, xbh, metamorphy Jan 26 at 6:36
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
To find the number of positive integers that can be written as a product of exactly $50$ primes if the only prime factors we can use are $2,3,5,7$.
The product of $50$ primes means that $n = p_1 times p_2 timescdots times p_{50}$, here are repetions allowed.
combinatorics number-theory prime-numbers recreational-mathematics
asked Jan 25 at 23:20
user8795user8795
5,73162047
$endgroup$
closed as unclear what you're asking by Rob Arthan, Cesareo, Gibbs, xbh, metamorphy Jan 26 at 6:36
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
It would be 4 multichoise 50, which is $binom{53}{3}$.
$endgroup$
– Zachary Hunter
Jan 25 at 23:23
$begingroup$
can you explain why? @ZacharyHunter
$endgroup$
– user8795
Jan 25 at 23:27
$begingroup$
we can have repetitions also as we can have $2^{50}$
$endgroup$
– user8795
Jan 25 at 23:29
1
$begingroup$
Try a simpler case first e.g. a product of $3$ primes and only $2$ and $3$ are allowed. Is the answer $2^3 = 8$? However, these $8$ include $2 times 2 times 3$, $2 times 3 times 2$, and $3 times 2 times 2$ which are all $12$.
$endgroup$
– badjohn
Jan 25 at 23:37
1
$begingroup$
The definition of n multichoose k is number of ways to choose k objects from a set of n with repititions. There are 4 primes we are choosing between, hence n=4, and we choose 50, meaning k=50. Generally, n multichoose k is $binom{n+k-1}{k}$ and there are many proofs of that online.
$endgroup$
– Zachary Hunter
Jan 25 at 23:39
add a comment |
$begingroup$
To find the number of positive integers that can be written as a product of exactly $50$ primes if the only prime factors we can use are $2,3,5,7$.
The product of $50$ primes means that $n = p_1 times p_2 timescdots times p_{50}$, here are repetions allowed.
combinatorics number-theory prime-numbers recreational-mathematics
asked Jan 25 at 23:20
user8795user8795
5,73162047
$endgroup$
To find the number of positive integers that can be written as a product of exactly $50$ primes if the only prime factors we can use are $2,3,5,7$.
The product of $50$ primes means that $n = p_1 times p_2 timescdots times p_{50}$, here are repetions allowed.
combinatorics number-theory prime-numbers recreational-mathematics
combinatorics number-theory prime-numbers recreational-mathematics
asked Jan 25 at 23:20
user8795user8795
5,73162047
asked Jan 25 at 23:20
user8795user8795
5,73162047
edited Jan 25 at 23:47
user8795
asked Jan 25 at 23:20
user8795user8795
5,73162047
asked Jan 25 at 23:20
user8795user8795
5,73162047
asked Jan 25 at 23:20
user8795user8795
5,73162047
5,73162047
closed as unclear what you're asking by Rob Arthan, Cesareo, Gibbs, xbh, metamorphy Jan 26 at 6:36
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
closed as unclear what you're asking by Rob Arthan, Cesareo, Gibbs, xbh, metamorphy Jan 26 at 6:36
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
It would be 4 multichoise 50, which is $binom{53}{3}$.
$endgroup$
– Zachary Hunter
Jan 25 at 23:23
$begingroup$
can you explain why? @ZacharyHunter
$endgroup$
– user8795
Jan 25 at 23:27
$begingroup$
we can have repetitions also as we can have $2^{50}$
$endgroup$
– user8795
Jan 25 at 23:29
1
$begingroup$
Try a simpler case first e.g. a product of $3$ primes and only $2$ and $3$ are allowed. Is the answer $2^3 = 8$? However, these $8$ include $2 times 2 times 3$, $2 times 3 times 2$, and $3 times 2 times 2$ which are all $12$.
$endgroup$
– badjohn
Jan 25 at 23:37
1
$begingroup$
The definition of n multichoose k is number of ways to choose k objects from a set of n with repititions. There are 4 primes we are choosing between, hence n=4, and we choose 50, meaning k=50. Generally, n multichoose k is $binom{n+k-1}{k}$ and there are many proofs of that online.
$endgroup$
– Zachary Hunter
Jan 25 at 23:39
add a comment |
$begingroup$
It would be 4 multichoise 50, which is $binom{53}{3}$.
$endgroup$
– Zachary Hunter
Jan 25 at 23:23
$begingroup$
can you explain why? @ZacharyHunter
$endgroup$
– user8795
Jan 25 at 23:27
$begingroup$
we can have repetitions also as we can have $2^{50}$
$endgroup$
– user8795
Jan 25 at 23:29
1
$begingroup$
Try a simpler case first e.g. a product of $3$ primes and only $2$ and $3$ are allowed. Is the answer $2^3 = 8$? However, these $8$ include $2 times 2 times 3$, $2 times 3 times 2$, and $3 times 2 times 2$ which are all $12$.
$endgroup$
– badjohn
Jan 25 at 23:37
1
$begingroup$
The definition of n multichoose k is number of ways to choose k objects from a set of n with repititions. There are 4 primes we are choosing between, hence n=4, and we choose 50, meaning k=50. Generally, n multichoose k is $binom{n+k-1}{k}$ and there are many proofs of that online.
$endgroup$
– Zachary Hunter
Jan 25 at 23:39
$begingroup$
It would be 4 multichoise 50, which is $binom{53}{3}$.
$endgroup$
– Zachary Hunter
Jan 25 at 23:23
$begingroup$
It would be 4 multichoise 50, which is $binom{53}{3}$.
$endgroup$
– Zachary Hunter
Jan 25 at 23:23
$begingroup$
can you explain why? @ZacharyHunter
$endgroup$
– user8795
Jan 25 at 23:27
$begingroup$
can you explain why? @ZacharyHunter
$endgroup$
– user8795
Jan 25 at 23:27
$begingroup$
we can have repetitions also as we can have $2^{50}$
$endgroup$
– user8795
Jan 25 at 23:29
$begingroup$
we can have repetitions also as we can have $2^{50}$
$endgroup$
– user8795
Jan 25 at 23:29
1
1
$begingroup$
Try a simpler case first e.g. a product of $3$ primes and only $2$ and $3$ are allowed. Is the answer $2^3 = 8$? However, these $8$ include $2 times 2 times 3$, $2 times 3 times 2$, and $3 times 2 times 2$ which are all $12$.
$endgroup$
– badjohn
Jan 25 at 23:37
$begingroup$
Try a simpler case first e.g. a product of $3$ primes and only $2$ and $3$ are allowed. Is the answer $2^3 = 8$? However, these $8$ include $2 times 2 times 3$, $2 times 3 times 2$, and $3 times 2 times 2$ which are all $12$.
$endgroup$
– badjohn
Jan 25 at 23:37
1
1
$begingroup$
The definition of n multichoose k is number of ways to choose k objects from a set of n with repititions. There are 4 primes we are choosing between, hence n=4, and we choose 50, meaning k=50. Generally, n multichoose k is $binom{n+k-1}{k}$ and there are many proofs of that online.
$endgroup$
– Zachary Hunter
Jan 25 at 23:39
$begingroup$
The definition of n multichoose k is number of ways to choose k objects from a set of n with repititions. There are 4 primes we are choosing between, hence n=4, and we choose 50, meaning k=50. Generally, n multichoose k is $binom{n+k-1}{k}$ and there are many proofs of that online.
$endgroup$
– Zachary Hunter
Jan 25 at 23:39
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Your solution overcounts because it takes into account the order of the primes in the product. For instance, if the question were about products of $5$ primes, then your solution counts the following products as different:
$$2cdot 3 cdot 5 cdot 7 cdot 7, qquad 2 cdot 7 cdot 3 cdot 7 cdot 5$$
but they are in fact the same number.
The question can be translated into the following problem: how many different ways can we write $x_1+x_2+x_3+x_4=50$ where each $x_i$ is a nonnegative integer. This is equivalent because we can form the product $2^{x_1}3^{x_2}5^{x_3}7^{x_4}$, and these will be distinct for distinct values of the $x_i$.
Set $y_i=x_i+1$. Then we are looking for how many ways we can write $y_1+y_2+y_3+y_4=54$ and all the $y_i$ are positive integers. This is the stars and bars problem with $n=54$ and $k=4$, so the answer is $binom{53}{3}$.
answered Jan 25 at 23:35
kccukccu
10.6k11229
$endgroup$
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Your solution overcounts because it takes into account the order of the primes in the product. For instance, if the question were about products of $5$ primes, then your solution counts the following products as different:
$$2cdot 3 cdot 5 cdot 7 cdot 7, qquad 2 cdot 7 cdot 3 cdot 7 cdot 5$$
but they are in fact the same number.
The question can be translated into the following problem: how many different ways can we write $x_1+x_2+x_3+x_4=50$ where each $x_i$ is a nonnegative integer. This is equivalent because we can form the product $2^{x_1}3^{x_2}5^{x_3}7^{x_4}$, and these will be distinct for distinct values of the $x_i$.
Set $y_i=x_i+1$. Then we are looking for how many ways we can write $y_1+y_2+y_3+y_4=54$ and all the $y_i$ are positive integers. This is the stars and bars problem with $n=54$ and $k=4$, so the answer is $binom{53}{3}$.
answered Jan 25 at 23:35
kccukccu
10.6k11229
$endgroup$
add a comment |
$begingroup$
Your solution overcounts because it takes into account the order of the primes in the product. For instance, if the question were about products of $5$ primes, then your solution counts the following products as different:
$$2cdot 3 cdot 5 cdot 7 cdot 7, qquad 2 cdot 7 cdot 3 cdot 7 cdot 5$$
but they are in fact the same number.
The question can be translated into the following problem: how many different ways can we write $x_1+x_2+x_3+x_4=50$ where each $x_i$ is a nonnegative integer. This is equivalent because we can form the product $2^{x_1}3^{x_2}5^{x_3}7^{x_4}$, and these will be distinct for distinct values of the $x_i$.
Set $y_i=x_i+1$. Then we are looking for how many ways we can write $y_1+y_2+y_3+y_4=54$ and all the $y_i$ are positive integers. This is the stars and bars problem with $n=54$ and $k=4$, so the answer is $binom{53}{3}$.
answered Jan 25 at 23:35
kccukccu
10.6k11229
$endgroup$
add a comment |
$begingroup$
Your solution overcounts because it takes into account the order of the primes in the product. For instance, if the question were about products of $5$ primes, then your solution counts the following products as different:
$$2cdot 3 cdot 5 cdot 7 cdot 7, qquad 2 cdot 7 cdot 3 cdot 7 cdot 5$$
but they are in fact the same number.
The question can be translated into the following problem: how many different ways can we write $x_1+x_2+x_3+x_4=50$ where each $x_i$ is a nonnegative integer. This is equivalent because we can form the product $2^{x_1}3^{x_2}5^{x_3}7^{x_4}$, and these will be distinct for distinct values of the $x_i$.
Set $y_i=x_i+1$. Then we are looking for how many ways we can write $y_1+y_2+y_3+y_4=54$ and all the $y_i$ are positive integers. This is the stars and bars problem with $n=54$ and $k=4$, so the answer is $binom{53}{3}$.
answered Jan 25 at 23:35
kccukccu
10.6k11229
$endgroup$
Your solution overcounts because it takes into account the order of the primes in the product. For instance, if the question were about products of $5$ primes, then your solution counts the following products as different:
$$2cdot 3 cdot 5 cdot 7 cdot 7, qquad 2 cdot 7 cdot 3 cdot 7 cdot 5$$
but they are in fact the same number.
The question can be translated into the following problem: how many different ways can we write $x_1+x_2+x_3+x_4=50$ where each $x_i$ is a nonnegative integer. This is equivalent because we can form the product $2^{x_1}3^{x_2}5^{x_3}7^{x_4}$, and these will be distinct for distinct values of the $x_i$.
Set $y_i=x_i+1$. Then we are looking for how many ways we can write $y_1+y_2+y_3+y_4=54$ and all the $y_i$ are positive integers. This is the stars and bars problem with $n=54$ and $k=4$, so the answer is $binom{53}{3}$.
answered Jan 25 at 23:35
kccukccu
10.6k11229
answered Jan 25 at 23:35
kccukccu
10.6k11229
answered Jan 25 at 23:35
kccukccu
10.6k11229
answered Jan 25 at 23:35
kccukccu
10.6k11229
10.6k11229
add a comment |
add a comment |
$begingroup$
It would be 4 multichoise 50, which is $binom{53}{3}$.
$endgroup$
– Zachary Hunter
Jan 25 at 23:23
$begingroup$
can you explain why? @ZacharyHunter
$endgroup$
– user8795
Jan 25 at 23:27
$begingroup$
we can have repetitions also as we can have $2^{50}$
$endgroup$
– user8795
Jan 25 at 23:29
1
$begingroup$
Try a simpler case first e.g. a product of $3$ primes and only $2$ and $3$ are allowed. Is the answer $2^3 = 8$? However, these $8$ include $2 times 2 times 3$, $2 times 3 times 2$, and $3 times 2 times 2$ which are all $12$.
$endgroup$
– badjohn
Jan 25 at 23:37
1
$begingroup$
The definition of n multichoose k is number of ways to choose k objects from a set of n with repititions. There are 4 primes we are choosing between, hence n=4, and we choose 50, meaning k=50. Generally, n multichoose k is $binom{n+k-1}{k}$ and there are many proofs of that online.
$endgroup$
– Zachary Hunter
Jan 25 at 23:39