Define $g(n):=f(n!)$. We want to find a closed formula for $g(n)$ [closed]
Clash Royale CLAN TAG#URR8PPP
up vote
-3
down vote
favorite
I am trying to understand the following question, and honestly have no idea from where to start it seems like it asking for factorial of $n$ terms in a form of $g(n)$?
Define $g(n):=f(n!)$. We want to find a closed formula for $g(n)$. First of all, we want to find a recurrence for $g(n)$. If n is odd, then it is pretty easy to see that $g(n)=g(n−1)$. If n is even, try to write $g(n)$ in terms of $g(n/2)$.
Can someone help thanks.
That the only definition of f given
That the only definition of f I have from above question which basically like a remainder of 0 in a binary number
like how many 0 are after last 1
Here is the screen shot of the question 
recurrence-relations binomial-coefficients closed-form
edited Aug 12 at 7:08
Sil
5,14121443
asked Aug 11 at 22:36
COLD TOLD
1026
closed as unclear what you're asking by JMoravitz, WW1, Clayton, Zain Patel, Taroccoesbrocco Aug 12 at 8:25
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.
 |Â
show 4 more comments
up vote
-3
down vote
favorite
I am trying to understand the following question, and honestly have no idea from where to start it seems like it asking for factorial of $n$ terms in a form of $g(n)$?
Define $g(n):=f(n!)$. We want to find a closed formula for $g(n)$. First of all, we want to find a recurrence for $g(n)$. If n is odd, then it is pretty easy to see that $g(n)=g(n−1)$. If n is even, try to write $g(n)$ in terms of $g(n/2)$.
Can someone help thanks.
That the only definition of f given
That the only definition of f I have from above question which basically like a remainder of 0 in a binary number
like how many 0 are after last 1
Here is the screen shot of the question
recurrence-relations binomial-coefficients closed-form
edited Aug 12 at 7:08
Sil
5,14121443
asked Aug 11 at 22:36
COLD TOLD
1026
closed as unclear what you're asking by JMoravitz, WW1, Clayton, Zain Patel, Taroccoesbrocco Aug 12 at 8:25
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.
5
To me this sounds like it could only make sense if you have a definition for $f$ first. Do you have a definition for the function $f$?
– alex.jordan
Aug 11 at 22:41
2
Surely there is more information given in the question or surrounding questions about the function $f$ and the function $g$. Until you provide us with more information the question is impossible to answer.
– JMoravitz
Aug 11 at 22:54
1
To emphasize the point, here are two extreme examples. Suppose that $f(n)=0$ for all $n$. Then we would have $g(n)=f(n!)=0$ for all $n$. For another example, suppose that $f(n)$ outputs the largest power of $2$ which divides $n$. In that case we would indeed have $g(n)=g(n-1)$ for every odd $n$ (something which isn't common), but in this example $g$ is much more complicated of a function than simply outputting zero for every result. These two functions are incredibly different, and until you tell us more about what $f$ is actually supposed to be, we can only use our imaginations.
– JMoravitz
Aug 11 at 23:02
1
You provided us with a screenshot of that one specific part of a question and $f$ is not defined there. What about the question before that? What about the beginning of the section of questions? If $f$ is not defined within the paragraph you screenshotted, then it must have been defined elsewhere.
– JMoravitz
Aug 11 at 23:04
2
Finally. Please provide such important definitions when you first post the question. Ironically, my second example in my second comment was almost the exact definition for $f$. Now, before working on solving the problem, we should work on making sure that you understand what is being asked. Do you understand what the function $f$ is and how to calculate for example, $f(4), f(6), f(9), f(24)$?
– JMoravitz
Aug 11 at 23:32
 |Â
show 4 more comments
up vote
-3
down vote
favorite
up vote
-3
down vote
favorite
I am trying to understand the following question, and honestly have no idea from where to start it seems like it asking for factorial of $n$ terms in a form of $g(n)$?
Define $g(n):=f(n!)$. We want to find a closed formula for $g(n)$. First of all, we want to find a recurrence for $g(n)$. If n is odd, then it is pretty easy to see that $g(n)=g(n−1)$. If n is even, try to write $g(n)$ in terms of $g(n/2)$.
Can someone help thanks.
That the only definition of f given
That the only definition of f I have from above question which basically like a remainder of 0 in a binary number
like how many 0 are after last 1
Here is the screen shot of the question
recurrence-relations binomial-coefficients closed-form
edited Aug 12 at 7:08
Sil
5,14121443
asked Aug 11 at 22:36
COLD TOLD
1026
I am trying to understand the following question, and honestly have no idea from where to start it seems like it asking for factorial of $n$ terms in a form of $g(n)$?
Define $g(n):=f(n!)$. We want to find a closed formula for $g(n)$. First of all, we want to find a recurrence for $g(n)$. If n is odd, then it is pretty easy to see that $g(n)=g(n−1)$. If n is even, try to write $g(n)$ in terms of $g(n/2)$.
Can someone help thanks.
That the only definition of f given
That the only definition of f I have from above question which basically like a remainder of 0 in a binary number
like how many 0 are after last 1
Here is the screen shot of the question
recurrence-relations binomial-coefficients closed-form
edited Aug 12 at 7:08
Sil
5,14121443
asked Aug 11 at 22:36
COLD TOLD
1026
edited Aug 12 at 7:08
Sil
5,14121443
edited Aug 12 at 7:08
Sil
5,14121443
edited Aug 12 at 7:08
Sil
5,14121443
5,14121443
asked Aug 11 at 22:36
COLD TOLD
1026
asked Aug 11 at 22:36
COLD TOLD
1026
asked Aug 11 at 22:36
COLD TOLD
1026
1026
closed as unclear what you're asking by JMoravitz, WW1, Clayton, Zain Patel, Taroccoesbrocco Aug 12 at 8:25
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 JMoravitz, WW1, Clayton, Zain Patel, Taroccoesbrocco Aug 12 at 8:25
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.
5
To me this sounds like it could only make sense if you have a definition for $f$ first. Do you have a definition for the function $f$?
– alex.jordan
Aug 11 at 22:41
2
Surely there is more information given in the question or surrounding questions about the function $f$ and the function $g$. Until you provide us with more information the question is impossible to answer.
– JMoravitz
Aug 11 at 22:54
1
To emphasize the point, here are two extreme examples. Suppose that $f(n)=0$ for all $n$. Then we would have $g(n)=f(n!)=0$ for all $n$. For another example, suppose that $f(n)$ outputs the largest power of $2$ which divides $n$. In that case we would indeed have $g(n)=g(n-1)$ for every odd $n$ (something which isn't common), but in this example $g$ is much more complicated of a function than simply outputting zero for every result. These two functions are incredibly different, and until you tell us more about what $f$ is actually supposed to be, we can only use our imaginations.
– JMoravitz
Aug 11 at 23:02
1
You provided us with a screenshot of that one specific part of a question and $f$ is not defined there. What about the question before that? What about the beginning of the section of questions? If $f$ is not defined within the paragraph you screenshotted, then it must have been defined elsewhere.
– JMoravitz
Aug 11 at 23:04
2
Finally. Please provide such important definitions when you first post the question. Ironically, my second example in my second comment was almost the exact definition for $f$. Now, before working on solving the problem, we should work on making sure that you understand what is being asked. Do you understand what the function $f$ is and how to calculate for example, $f(4), f(6), f(9), f(24)$?
– JMoravitz
Aug 11 at 23:32
 |Â
show 4 more comments
5
To me this sounds like it could only make sense if you have a definition for $f$ first. Do you have a definition for the function $f$?
– alex.jordan
Aug 11 at 22:41
2
Surely there is more information given in the question or surrounding questions about the function $f$ and the function $g$. Until you provide us with more information the question is impossible to answer.
– JMoravitz
Aug 11 at 22:54
1
To emphasize the point, here are two extreme examples. Suppose that $f(n)=0$ for all $n$. Then we would have $g(n)=f(n!)=0$ for all $n$. For another example, suppose that $f(n)$ outputs the largest power of $2$ which divides $n$. In that case we would indeed have $g(n)=g(n-1)$ for every odd $n$ (something which isn't common), but in this example $g$ is much more complicated of a function than simply outputting zero for every result. These two functions are incredibly different, and until you tell us more about what $f$ is actually supposed to be, we can only use our imaginations.
– JMoravitz
Aug 11 at 23:02
1
You provided us with a screenshot of that one specific part of a question and $f$ is not defined there. What about the question before that? What about the beginning of the section of questions? If $f$ is not defined within the paragraph you screenshotted, then it must have been defined elsewhere.
– JMoravitz
Aug 11 at 23:04
2
Finally. Please provide such important definitions when you first post the question. Ironically, my second example in my second comment was almost the exact definition for $f$. Now, before working on solving the problem, we should work on making sure that you understand what is being asked. Do you understand what the function $f$ is and how to calculate for example, $f(4), f(6), f(9), f(24)$?
– JMoravitz
Aug 11 at 23:32
5
5
To me this sounds like it could only make sense if you have a definition for $f$ first. Do you have a definition for the function $f$?
– alex.jordan
Aug 11 at 22:41
To me this sounds like it could only make sense if you have a definition for $f$ first. Do you have a definition for the function $f$?
– alex.jordan
Aug 11 at 22:41
2
2
Surely there is more information given in the question or surrounding questions about the function $f$ and the function $g$. Until you provide us with more information the question is impossible to answer.
– JMoravitz
Aug 11 at 22:54
Surely there is more information given in the question or surrounding questions about the function $f$ and the function $g$. Until you provide us with more information the question is impossible to answer.
– JMoravitz
Aug 11 at 22:54
1
1
To emphasize the point, here are two extreme examples. Suppose that $f(n)=0$ for all $n$. Then we would have $g(n)=f(n!)=0$ for all $n$. For another example, suppose that $f(n)$ outputs the largest power of $2$ which divides $n$. In that case we would indeed have $g(n)=g(n-1)$ for every odd $n$ (something which isn't common), but in this example $g$ is much more complicated of a function than simply outputting zero for every result. These two functions are incredibly different, and until you tell us more about what $f$ is actually supposed to be, we can only use our imaginations.
– JMoravitz
Aug 11 at 23:02
To emphasize the point, here are two extreme examples. Suppose that $f(n)=0$ for all $n$. Then we would have $g(n)=f(n!)=0$ for all $n$. For another example, suppose that $f(n)$ outputs the largest power of $2$ which divides $n$. In that case we would indeed have $g(n)=g(n-1)$ for every odd $n$ (something which isn't common), but in this example $g$ is much more complicated of a function than simply outputting zero for every result. These two functions are incredibly different, and until you tell us more about what $f$ is actually supposed to be, we can only use our imaginations.
– JMoravitz
Aug 11 at 23:02
1
1
You provided us with a screenshot of that one specific part of a question and $f$ is not defined there. What about the question before that? What about the beginning of the section of questions? If $f$ is not defined within the paragraph you screenshotted, then it must have been defined elsewhere.
– JMoravitz
Aug 11 at 23:04
You provided us with a screenshot of that one specific part of a question and $f$ is not defined there. What about the question before that? What about the beginning of the section of questions? If $f$ is not defined within the paragraph you screenshotted, then it must have been defined elsewhere.
– JMoravitz
Aug 11 at 23:04
2
2
Finally. Please provide such important definitions when you first post the question. Ironically, my second example in my second comment was almost the exact definition for $f$. Now, before working on solving the problem, we should work on making sure that you understand what is being asked. Do you understand what the function $f$ is and how to calculate for example, $f(4), f(6), f(9), f(24)$?
– JMoravitz
Aug 11 at 23:32
Finally. Please provide such important definitions when you first post the question. Ironically, my second example in my second comment was almost the exact definition for $f$. Now, before working on solving the problem, we should work on making sure that you understand what is being asked. Do you understand what the function $f$ is and how to calculate for example, $f(4), f(6), f(9), f(24)$?
– JMoravitz
Aug 11 at 23:32
 |Â
show 4 more comments
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
Hints:
$(2k+1)! = beginarraylcolorgrey1~~cdot 3~~cdot 5~~cdot 7~~cdots (2k-3)~~~~cdot (2k-1)~~~cdot(2k+1)\~~cdot 2~~cdot 4~~cdot 6~~cdot 8cdots~~~~cdot(2k-2)~~~~~cdot (2k)endarray$
Noting that the odd factors in grey contribute nothing to the largest power of $2$ which divides $(2k+1)!$ we see that $g(2n+1)=g(2n)$.
$(2k)! = beginarraylcolorgrey1~~cdot 3~~cdot 5~~cdot 7~~cdots (2k-3)~~~~cdot (2k-1)\~~cdot 2~~cdot 4~~cdot 6~~cdot 8cdots~~~~cdot(2k-2)~~~~cdot(2k)endarray$
$=colorgrey(1cdot 3cdot 5cdots (2k-3)cdot (2k-1))cdot (2cdot 4cdot 6cdots (2k-2)(2k))$
$=colorgrey(1cdot 3cdot 5cdots (2k-3)cdot (2k-1))cdot ((2cdot 1)cdot (2cdot 2)cdot (2cdot 3)cdots (2cdot(k-1))cdot (2cdot k))$
$=colorgrey(1cdot 3cdot 5cdots (2k-3)cdot (2k-1))cdot 2^kcdot k!$
Notice that the odd factors in grey contribute nothing to the largest power of $2$ which divides $(2k)!$
You should be able now to recognize the relationship between $g(2k)$ and $g(k)$. Armed with this knowledge, you should be able to find $g(8000000000000)-g(4000000000000)$ with almost no effort.
Additional hint:
Recognize that $g(2k)$ counts the number of factors of $2$ occurring in $(2k)!$ and $g(k)$ counts the number of factors of $2$ occurring in $k!$. Recognize that $(2k)!$ is equal to an odd number (which has no factors of $2$) times $2^k$ times $k!$. So, the only additional factors of $2$ which are present between $(2k)!$ and $k!$ are those that occur as a result of $2^k$.
Solution:
$g(2n)-g(n)=n$
The above helps us to come up with a recursive definition for $g$, but it is not particularly helpful for finding a closed form for $g$ (that I immediately see).
That being said, when calculating $g(n)$ notice that every multiple of $2$ less than or equal to $n$ will contribute one to the total of the largest exponent of $2$ that divides $n!$. Further, each multiple of four less than or equal to $n$ will contribute yet an additional one to the total, and further each multiple of eight will and so on.
You should be able to formalize these observations in order to express $g(n)$ in closed form using an infinite sum.
This should remind you a great deal of the problem of counting how many trailing zeroes are at the end of a factorial, see for example here.
answered Aug 12 at 0:57
JMoravitz
44.4k33481
As I was reading your comments I guess it makes me a little more confused lets me state the following that I do understand 1) $g(n)=textmaxkinBbb N~textsuch that~2^k~textdivides~ n!$ which i do get is the largest number in pover of 2 that divides n! which basically what you showed in the comment, does that mean that in order to solve $g(8000000000000)-g(4000000000000)$ I have to follow the same technique and find the larges power of 2 that divides 8000000000000?
– COLD TOLD
Aug 12 at 2:18
@COLDTOLD No. You don't actually need to know the value of $g(8000000000000)$ at all. Neither do you need to know the value of $g(4000000000000)$. Again, see if you can find the simplification of $g(2n)-g(n)$.
– JMoravitz
Aug 12 at 2:33
Thank you very much, I appreciate your effort in helping me a lot, I think it often gets confusing to me to see what problem is asking, if it written in a way like described, It also a little hard taking on-line course when you watch a video for 20 min which has clear example an explanation and then forced to solve something much more difficult, I might have some more question about other problem but, trying to solve it by myself. I am very glad to be able to find explanation and help on line. Thank You
– COLD TOLD
Aug 12 at 2:51
I wonder if you would have some time to help me with this problem, For $n in mathbbN$ let w(n) denote the number of 1s in the binary representation of n. For example, w(9)=2, since $9$ is 1001 in binary. Try to find a closed formula for g(n) in terms of n and w(n). I was trying to follow your explanation of above problem but everything I try seems to be wrong. If not it fine just don't want to be annoying.
– COLD TOLD
Aug 14 at 2:05
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
Hints:
$(2k+1)! = beginarraylcolorgrey1~~cdot 3~~cdot 5~~cdot 7~~cdots (2k-3)~~~~cdot (2k-1)~~~cdot(2k+1)\~~cdot 2~~cdot 4~~cdot 6~~cdot 8cdots~~~~cdot(2k-2)~~~~~cdot (2k)endarray$
Noting that the odd factors in grey contribute nothing to the largest power of $2$ which divides $(2k+1)!$ we see that $g(2n+1)=g(2n)$.
$(2k)! = beginarraylcolorgrey1~~cdot 3~~cdot 5~~cdot 7~~cdots (2k-3)~~~~cdot (2k-1)\~~cdot 2~~cdot 4~~cdot 6~~cdot 8cdots~~~~cdot(2k-2)~~~~cdot(2k)endarray$
$=colorgrey(1cdot 3cdot 5cdots (2k-3)cdot (2k-1))cdot (2cdot 4cdot 6cdots (2k-2)(2k))$
$=colorgrey(1cdot 3cdot 5cdots (2k-3)cdot (2k-1))cdot ((2cdot 1)cdot (2cdot 2)cdot (2cdot 3)cdots (2cdot(k-1))cdot (2cdot k))$
$=colorgrey(1cdot 3cdot 5cdots (2k-3)cdot (2k-1))cdot 2^kcdot k!$
Notice that the odd factors in grey contribute nothing to the largest power of $2$ which divides $(2k)!$
You should be able now to recognize the relationship between $g(2k)$ and $g(k)$. Armed with this knowledge, you should be able to find $g(8000000000000)-g(4000000000000)$ with almost no effort.
Additional hint:
Recognize that $g(2k)$ counts the number of factors of $2$ occurring in $(2k)!$ and $g(k)$ counts the number of factors of $2$ occurring in $k!$. Recognize that $(2k)!$ is equal to an odd number (which has no factors of $2$) times $2^k$ times $k!$. So, the only additional factors of $2$ which are present between $(2k)!$ and $k!$ are those that occur as a result of $2^k$.
Solution:
$g(2n)-g(n)=n$
The above helps us to come up with a recursive definition for $g$, but it is not particularly helpful for finding a closed form for $g$ (that I immediately see).
That being said, when calculating $g(n)$ notice that every multiple of $2$ less than or equal to $n$ will contribute one to the total of the largest exponent of $2$ that divides $n!$. Further, each multiple of four less than or equal to $n$ will contribute yet an additional one to the total, and further each multiple of eight will and so on.
You should be able to formalize these observations in order to express $g(n)$ in closed form using an infinite sum.
This should remind you a great deal of the problem of counting how many trailing zeroes are at the end of a factorial, see for example here.
answered Aug 12 at 0:57
JMoravitz
44.4k33481
As I was reading your comments I guess it makes me a little more confused lets me state the following that I do understand 1) $g(n)=textmaxkinBbb N~textsuch that~2^k~textdivides~ n!$ which i do get is the largest number in pover of 2 that divides n! which basically what you showed in the comment, does that mean that in order to solve $g(8000000000000)-g(4000000000000)$ I have to follow the same technique and find the larges power of 2 that divides 8000000000000?
– COLD TOLD
Aug 12 at 2:18
@COLDTOLD No. You don't actually need to know the value of $g(8000000000000)$ at all. Neither do you need to know the value of $g(4000000000000)$. Again, see if you can find the simplification of $g(2n)-g(n)$.
– JMoravitz
Aug 12 at 2:33
Thank you very much, I appreciate your effort in helping me a lot, I think it often gets confusing to me to see what problem is asking, if it written in a way like described, It also a little hard taking on-line course when you watch a video for 20 min which has clear example an explanation and then forced to solve something much more difficult, I might have some more question about other problem but, trying to solve it by myself. I am very glad to be able to find explanation and help on line. Thank You
– COLD TOLD
Aug 12 at 2:51
I wonder if you would have some time to help me with this problem, For $n in mathbbN$ let w(n) denote the number of 1s in the binary representation of n. For example, w(9)=2, since $9$ is 1001 in binary. Try to find a closed formula for g(n) in terms of n and w(n). I was trying to follow your explanation of above problem but everything I try seems to be wrong. If not it fine just don't want to be annoying.
– COLD TOLD
Aug 14 at 2:05
add a comment |Â
up vote
2
down vote
accepted
Hints:
$(2k+1)! = beginarraylcolorgrey1~~cdot 3~~cdot 5~~cdot 7~~cdots (2k-3)~~~~cdot (2k-1)~~~cdot(2k+1)\~~cdot 2~~cdot 4~~cdot 6~~cdot 8cdots~~~~cdot(2k-2)~~~~~cdot (2k)endarray$
Noting that the odd factors in grey contribute nothing to the largest power of $2$ which divides $(2k+1)!$ we see that $g(2n+1)=g(2n)$.
$(2k)! = beginarraylcolorgrey1~~cdot 3~~cdot 5~~cdot 7~~cdots (2k-3)~~~~cdot (2k-1)\~~cdot 2~~cdot 4~~cdot 6~~cdot 8cdots~~~~cdot(2k-2)~~~~cdot(2k)endarray$
$=colorgrey(1cdot 3cdot 5cdots (2k-3)cdot (2k-1))cdot (2cdot 4cdot 6cdots (2k-2)(2k))$
$=colorgrey(1cdot 3cdot 5cdots (2k-3)cdot (2k-1))cdot ((2cdot 1)cdot (2cdot 2)cdot (2cdot 3)cdots (2cdot(k-1))cdot (2cdot k))$
$=colorgrey(1cdot 3cdot 5cdots (2k-3)cdot (2k-1))cdot 2^kcdot k!$
Notice that the odd factors in grey contribute nothing to the largest power of $2$ which divides $(2k)!$
You should be able now to recognize the relationship between $g(2k)$ and $g(k)$. Armed with this knowledge, you should be able to find $g(8000000000000)-g(4000000000000)$ with almost no effort.
Additional hint:
Recognize that $g(2k)$ counts the number of factors of $2$ occurring in $(2k)!$ and $g(k)$ counts the number of factors of $2$ occurring in $k!$. Recognize that $(2k)!$ is equal to an odd number (which has no factors of $2$) times $2^k$ times $k!$. So, the only additional factors of $2$ which are present between $(2k)!$ and $k!$ are those that occur as a result of $2^k$.
Solution:
$g(2n)-g(n)=n$
The above helps us to come up with a recursive definition for $g$, but it is not particularly helpful for finding a closed form for $g$ (that I immediately see).
That being said, when calculating $g(n)$ notice that every multiple of $2$ less than or equal to $n$ will contribute one to the total of the largest exponent of $2$ that divides $n!$. Further, each multiple of four less than or equal to $n$ will contribute yet an additional one to the total, and further each multiple of eight will and so on.
You should be able to formalize these observations in order to express $g(n)$ in closed form using an infinite sum.
This should remind you a great deal of the problem of counting how many trailing zeroes are at the end of a factorial, see for example here.
answered Aug 12 at 0:57
JMoravitz
44.4k33481
As I was reading your comments I guess it makes me a little more confused lets me state the following that I do understand 1) $g(n)=textmaxkinBbb N~textsuch that~2^k~textdivides~ n!$ which i do get is the largest number in pover of 2 that divides n! which basically what you showed in the comment, does that mean that in order to solve $g(8000000000000)-g(4000000000000)$ I have to follow the same technique and find the larges power of 2 that divides 8000000000000?
– COLD TOLD
Aug 12 at 2:18
@COLDTOLD No. You don't actually need to know the value of $g(8000000000000)$ at all. Neither do you need to know the value of $g(4000000000000)$. Again, see if you can find the simplification of $g(2n)-g(n)$.
– JMoravitz
Aug 12 at 2:33
Thank you very much, I appreciate your effort in helping me a lot, I think it often gets confusing to me to see what problem is asking, if it written in a way like described, It also a little hard taking on-line course when you watch a video for 20 min which has clear example an explanation and then forced to solve something much more difficult, I might have some more question about other problem but, trying to solve it by myself. I am very glad to be able to find explanation and help on line. Thank You
– COLD TOLD
Aug 12 at 2:51
I wonder if you would have some time to help me with this problem, For $n in mathbbN$ let w(n) denote the number of 1s in the binary representation of n. For example, w(9)=2, since $9$ is 1001 in binary. Try to find a closed formula for g(n) in terms of n and w(n). I was trying to follow your explanation of above problem but everything I try seems to be wrong. If not it fine just don't want to be annoying.
– COLD TOLD
Aug 14 at 2:05
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
Hints:
$(2k+1)! = beginarraylcolorgrey1~~cdot 3~~cdot 5~~cdot 7~~cdots (2k-3)~~~~cdot (2k-1)~~~cdot(2k+1)\~~cdot 2~~cdot 4~~cdot 6~~cdot 8cdots~~~~cdot(2k-2)~~~~~cdot (2k)endarray$
Noting that the odd factors in grey contribute nothing to the largest power of $2$ which divides $(2k+1)!$ we see that $g(2n+1)=g(2n)$.
$(2k)! = beginarraylcolorgrey1~~cdot 3~~cdot 5~~cdot 7~~cdots (2k-3)~~~~cdot (2k-1)\~~cdot 2~~cdot 4~~cdot 6~~cdot 8cdots~~~~cdot(2k-2)~~~~cdot(2k)endarray$
$=colorgrey(1cdot 3cdot 5cdots (2k-3)cdot (2k-1))cdot (2cdot 4cdot 6cdots (2k-2)(2k))$
$=colorgrey(1cdot 3cdot 5cdots (2k-3)cdot (2k-1))cdot ((2cdot 1)cdot (2cdot 2)cdot (2cdot 3)cdots (2cdot(k-1))cdot (2cdot k))$
$=colorgrey(1cdot 3cdot 5cdots (2k-3)cdot (2k-1))cdot 2^kcdot k!$
Notice that the odd factors in grey contribute nothing to the largest power of $2$ which divides $(2k)!$
You should be able now to recognize the relationship between $g(2k)$ and $g(k)$. Armed with this knowledge, you should be able to find $g(8000000000000)-g(4000000000000)$ with almost no effort.
Additional hint:
Recognize that $g(2k)$ counts the number of factors of $2$ occurring in $(2k)!$ and $g(k)$ counts the number of factors of $2$ occurring in $k!$. Recognize that $(2k)!$ is equal to an odd number (which has no factors of $2$) times $2^k$ times $k!$. So, the only additional factors of $2$ which are present between $(2k)!$ and $k!$ are those that occur as a result of $2^k$.
Solution:
$g(2n)-g(n)=n$
The above helps us to come up with a recursive definition for $g$, but it is not particularly helpful for finding a closed form for $g$ (that I immediately see).
That being said, when calculating $g(n)$ notice that every multiple of $2$ less than or equal to $n$ will contribute one to the total of the largest exponent of $2$ that divides $n!$. Further, each multiple of four less than or equal to $n$ will contribute yet an additional one to the total, and further each multiple of eight will and so on.
You should be able to formalize these observations in order to express $g(n)$ in closed form using an infinite sum.
This should remind you a great deal of the problem of counting how many trailing zeroes are at the end of a factorial, see for example here.
answered Aug 12 at 0:57
JMoravitz
44.4k33481
Hints:
$(2k+1)! = beginarraylcolorgrey1~~cdot 3~~cdot 5~~cdot 7~~cdots (2k-3)~~~~cdot (2k-1)~~~cdot(2k+1)\~~cdot 2~~cdot 4~~cdot 6~~cdot 8cdots~~~~cdot(2k-2)~~~~~cdot (2k)endarray$
Noting that the odd factors in grey contribute nothing to the largest power of $2$ which divides $(2k+1)!$ we see that $g(2n+1)=g(2n)$.
$(2k)! = beginarraylcolorgrey1~~cdot 3~~cdot 5~~cdot 7~~cdots (2k-3)~~~~cdot (2k-1)\~~cdot 2~~cdot 4~~cdot 6~~cdot 8cdots~~~~cdot(2k-2)~~~~cdot(2k)endarray$
$=colorgrey(1cdot 3cdot 5cdots (2k-3)cdot (2k-1))cdot (2cdot 4cdot 6cdots (2k-2)(2k))$
$=colorgrey(1cdot 3cdot 5cdots (2k-3)cdot (2k-1))cdot ((2cdot 1)cdot (2cdot 2)cdot (2cdot 3)cdots (2cdot(k-1))cdot (2cdot k))$
$=colorgrey(1cdot 3cdot 5cdots (2k-3)cdot (2k-1))cdot 2^kcdot k!$
Notice that the odd factors in grey contribute nothing to the largest power of $2$ which divides $(2k)!$
You should be able now to recognize the relationship between $g(2k)$ and $g(k)$. Armed with this knowledge, you should be able to find $g(8000000000000)-g(4000000000000)$ with almost no effort.
Additional hint:
Recognize that $g(2k)$ counts the number of factors of $2$ occurring in $(2k)!$ and $g(k)$ counts the number of factors of $2$ occurring in $k!$. Recognize that $(2k)!$ is equal to an odd number (which has no factors of $2$) times $2^k$ times $k!$. So, the only additional factors of $2$ which are present between $(2k)!$ and $k!$ are those that occur as a result of $2^k$.
Solution:
$g(2n)-g(n)=n$
The above helps us to come up with a recursive definition for $g$, but it is not particularly helpful for finding a closed form for $g$ (that I immediately see).
That being said, when calculating $g(n)$ notice that every multiple of $2$ less than or equal to $n$ will contribute one to the total of the largest exponent of $2$ that divides $n!$. Further, each multiple of four less than or equal to $n$ will contribute yet an additional one to the total, and further each multiple of eight will and so on.
You should be able to formalize these observations in order to express $g(n)$ in closed form using an infinite sum.
This should remind you a great deal of the problem of counting how many trailing zeroes are at the end of a factorial, see for example here.
answered Aug 12 at 0:57
JMoravitz
44.4k33481
edited Aug 12 at 2:37
answered Aug 12 at 0:57
JMoravitz
44.4k33481
answered Aug 12 at 0:57
JMoravitz
44.4k33481
answered Aug 12 at 0:57
JMoravitz
44.4k33481
44.4k33481
As I was reading your comments I guess it makes me a little more confused lets me state the following that I do understand 1) $g(n)=textmaxkinBbb N~textsuch that~2^k~textdivides~ n!$ which i do get is the largest number in pover of 2 that divides n! which basically what you showed in the comment, does that mean that in order to solve $g(8000000000000)-g(4000000000000)$ I have to follow the same technique and find the larges power of 2 that divides 8000000000000?
– COLD TOLD
Aug 12 at 2:18
@COLDTOLD No. You don't actually need to know the value of $g(8000000000000)$ at all. Neither do you need to know the value of $g(4000000000000)$. Again, see if you can find the simplification of $g(2n)-g(n)$.
– JMoravitz
Aug 12 at 2:33
Thank you very much, I appreciate your effort in helping me a lot, I think it often gets confusing to me to see what problem is asking, if it written in a way like described, It also a little hard taking on-line course when you watch a video for 20 min which has clear example an explanation and then forced to solve something much more difficult, I might have some more question about other problem but, trying to solve it by myself. I am very glad to be able to find explanation and help on line. Thank You
– COLD TOLD
Aug 12 at 2:51
I wonder if you would have some time to help me with this problem, For $n in mathbbN$ let w(n) denote the number of 1s in the binary representation of n. For example, w(9)=2, since $9$ is 1001 in binary. Try to find a closed formula for g(n) in terms of n and w(n). I was trying to follow your explanation of above problem but everything I try seems to be wrong. If not it fine just don't want to be annoying.
– COLD TOLD
Aug 14 at 2:05
add a comment |Â
As I was reading your comments I guess it makes me a little more confused lets me state the following that I do understand 1) $g(n)=textmaxkinBbb N~textsuch that~2^k~textdivides~ n!$ which i do get is the largest number in pover of 2 that divides n! which basically what you showed in the comment, does that mean that in order to solve $g(8000000000000)-g(4000000000000)$ I have to follow the same technique and find the larges power of 2 that divides 8000000000000?
– COLD TOLD
Aug 12 at 2:18
@COLDTOLD No. You don't actually need to know the value of $g(8000000000000)$ at all. Neither do you need to know the value of $g(4000000000000)$. Again, see if you can find the simplification of $g(2n)-g(n)$.
– JMoravitz
Aug 12 at 2:33
Thank you very much, I appreciate your effort in helping me a lot, I think it often gets confusing to me to see what problem is asking, if it written in a way like described, It also a little hard taking on-line course when you watch a video for 20 min which has clear example an explanation and then forced to solve something much more difficult, I might have some more question about other problem but, trying to solve it by myself. I am very glad to be able to find explanation and help on line. Thank You
– COLD TOLD
Aug 12 at 2:51
I wonder if you would have some time to help me with this problem, For $n in mathbbN$ let w(n) denote the number of 1s in the binary representation of n. For example, w(9)=2, since $9$ is 1001 in binary. Try to find a closed formula for g(n) in terms of n and w(n). I was trying to follow your explanation of above problem but everything I try seems to be wrong. If not it fine just don't want to be annoying.
– COLD TOLD
Aug 14 at 2:05
As I was reading your comments I guess it makes me a little more confused lets me state the following that I do understand 1) $g(n)=textmaxkinBbb N~textsuch that~2^k~textdivides~ n!$ which i do get is the largest number in pover of 2 that divides n! which basically what you showed in the comment, does that mean that in order to solve $g(8000000000000)-g(4000000000000)$ I have to follow the same technique and find the larges power of 2 that divides 8000000000000?
– COLD TOLD
Aug 12 at 2:18
As I was reading your comments I guess it makes me a little more confused lets me state the following that I do understand 1) $g(n)=textmaxkinBbb N~textsuch that~2^k~textdivides~ n!$ which i do get is the largest number in pover of 2 that divides n! which basically what you showed in the comment, does that mean that in order to solve $g(8000000000000)-g(4000000000000)$ I have to follow the same technique and find the larges power of 2 that divides 8000000000000?
– COLD TOLD
Aug 12 at 2:18
@COLDTOLD No. You don't actually need to know the value of $g(8000000000000)$ at all. Neither do you need to know the value of $g(4000000000000)$. Again, see if you can find the simplification of $g(2n)-g(n)$.
– JMoravitz
Aug 12 at 2:33
@COLDTOLD No. You don't actually need to know the value of $g(8000000000000)$ at all. Neither do you need to know the value of $g(4000000000000)$. Again, see if you can find the simplification of $g(2n)-g(n)$.
– JMoravitz
Aug 12 at 2:33
Thank you very much, I appreciate your effort in helping me a lot, I think it often gets confusing to me to see what problem is asking, if it written in a way like described, It also a little hard taking on-line course when you watch a video for 20 min which has clear example an explanation and then forced to solve something much more difficult, I might have some more question about other problem but, trying to solve it by myself. I am very glad to be able to find explanation and help on line. Thank You
– COLD TOLD
Aug 12 at 2:51
Thank you very much, I appreciate your effort in helping me a lot, I think it often gets confusing to me to see what problem is asking, if it written in a way like described, It also a little hard taking on-line course when you watch a video for 20 min which has clear example an explanation and then forced to solve something much more difficult, I might have some more question about other problem but, trying to solve it by myself. I am very glad to be able to find explanation and help on line. Thank You
– COLD TOLD
Aug 12 at 2:51
I wonder if you would have some time to help me with this problem, For $n in mathbbN$ let w(n) denote the number of 1s in the binary representation of n. For example, w(9)=2, since $9$ is 1001 in binary. Try to find a closed formula for g(n) in terms of n and w(n). I was trying to follow your explanation of above problem but everything I try seems to be wrong. If not it fine just don't want to be annoying.
– COLD TOLD
Aug 14 at 2:05
I wonder if you would have some time to help me with this problem, For $n in mathbbN$ let w(n) denote the number of 1s in the binary representation of n. For example, w(9)=2, since $9$ is 1001 in binary. Try to find a closed formula for g(n) in terms of n and w(n). I was trying to follow your explanation of above problem but everything I try seems to be wrong. If not it fine just don't want to be annoying.
– COLD TOLD
Aug 14 at 2:05
add a comment |Â
5
To me this sounds like it could only make sense if you have a definition for $f$ first. Do you have a definition for the function $f$?
– alex.jordan
Aug 11 at 22:41
2
Surely there is more information given in the question or surrounding questions about the function $f$ and the function $g$. Until you provide us with more information the question is impossible to answer.
– JMoravitz
Aug 11 at 22:54
1
To emphasize the point, here are two extreme examples. Suppose that $f(n)=0$ for all $n$. Then we would have $g(n)=f(n!)=0$ for all $n$. For another example, suppose that $f(n)$ outputs the largest power of $2$ which divides $n$. In that case we would indeed have $g(n)=g(n-1)$ for every odd $n$ (something which isn't common), but in this example $g$ is much more complicated of a function than simply outputting zero for every result. These two functions are incredibly different, and until you tell us more about what $f$ is actually supposed to be, we can only use our imaginations.
– JMoravitz
Aug 11 at 23:02
1
You provided us with a screenshot of that one specific part of a question and $f$ is not defined there. What about the question before that? What about the beginning of the section of questions? If $f$ is not defined within the paragraph you screenshotted, then it must have been defined elsewhere.
– JMoravitz
Aug 11 at 23:04
2
Finally. Please provide such important definitions when you first post the question. Ironically, my second example in my second comment was almost the exact definition for $f$. Now, before working on solving the problem, we should work on making sure that you understand what is being asked. Do you understand what the function $f$ is and how to calculate for example, $f(4), f(6), f(9), f(24)$?
– JMoravitz
Aug 11 at 23:32