Thoughts about the Lucas Theorem
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
We define $f(n) = max k in mathbbN text, such that $2^k$ divides n $. As an example, $f(99) = 0$, $f(5) = 0$, $f(12) = 2$, $f(14) = 1$.
Now further let's define $g(n) := f(n!)$. Finding a recurrence, if $n$ is odd then $g(n) = g(n-1)$. How can we write $g(n)$ in terms of a closed formula?
How can we describe the even variant in terms of $g(n/2)$?
And if we can describe it, what would be the closed formula for two evens $a,b$ for the equation $g(a) - g(b)$? As an example $g(8.000.000.000.000) - g(4.000.000.000.000) = ?$
combinatorics discrete-mathematics
asked Aug 15 at 9:47
John Smith
327
add a comment |Â
up vote
2
down vote
favorite
We define $f(n) = max k in mathbbN text, such that $2^k$ divides n $. As an example, $f(99) = 0$, $f(5) = 0$, $f(12) = 2$, $f(14) = 1$.
Now further let's define $g(n) := f(n!)$. Finding a recurrence, if $n$ is odd then $g(n) = g(n-1)$. How can we write $g(n)$ in terms of a closed formula?
How can we describe the even variant in terms of $g(n/2)$?
And if we can describe it, what would be the closed formula for two evens $a,b$ for the equation $g(a) - g(b)$? As an example $g(8.000.000.000.000) - g(4.000.000.000.000) = ?$
combinatorics discrete-mathematics
asked Aug 15 at 9:47
John Smith
327
This is an useful (in terms of calculating) formula $g(n) = sum_i=1^infty lfloor fracn2^i rfloor $ (note that the sum is finite)
– Rumpelstiltskin
Aug 15 at 10:16
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
We define $f(n) = max k in mathbbN text, such that $2^k$ divides n $. As an example, $f(99) = 0$, $f(5) = 0$, $f(12) = 2$, $f(14) = 1$.
Now further let's define $g(n) := f(n!)$. Finding a recurrence, if $n$ is odd then $g(n) = g(n-1)$. How can we write $g(n)$ in terms of a closed formula?
How can we describe the even variant in terms of $g(n/2)$?
And if we can describe it, what would be the closed formula for two evens $a,b$ for the equation $g(a) - g(b)$? As an example $g(8.000.000.000.000) - g(4.000.000.000.000) = ?$
combinatorics discrete-mathematics
asked Aug 15 at 9:47
John Smith
327
We define $f(n) = max k in mathbbN text, such that $2^k$ divides n $. As an example, $f(99) = 0$, $f(5) = 0$, $f(12) = 2$, $f(14) = 1$.
Now further let's define $g(n) := f(n!)$. Finding a recurrence, if $n$ is odd then $g(n) = g(n-1)$. How can we write $g(n)$ in terms of a closed formula?
How can we describe the even variant in terms of $g(n/2)$?
And if we can describe it, what would be the closed formula for two evens $a,b$ for the equation $g(a) - g(b)$? As an example $g(8.000.000.000.000) - g(4.000.000.000.000) = ?$
combinatorics discrete-mathematics
asked Aug 15 at 9:47
John Smith
327
asked Aug 15 at 9:47
John Smith
327
asked Aug 15 at 9:47
John Smith
327
asked Aug 15 at 9:47
John Smith
327
327
This is an useful (in terms of calculating) formula $g(n) = sum_i=1^infty lfloor fracn2^i rfloor $ (note that the sum is finite)
– Rumpelstiltskin
Aug 15 at 10:16
add a comment |Â
This is an useful (in terms of calculating) formula $g(n) = sum_i=1^infty lfloor fracn2^i rfloor $ (note that the sum is finite)
– Rumpelstiltskin
Aug 15 at 10:16
This is an useful (in terms of calculating) formula $g(n) = sum_i=1^infty lfloor fracn2^i rfloor $ (note that the sum is finite)
– Rumpelstiltskin
Aug 15 at 10:16
This is an useful (in terms of calculating) formula $g(n) = sum_i=1^infty lfloor fracn2^i rfloor $ (note that the sum is finite)
– Rumpelstiltskin
Aug 15 at 10:16
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
The highest power of $2$ that divides $x!$ is
$$sum_n=1^infty[fracx2^n]$$
Which can be shown by counting techniques. Thus we get
$$g(x)=sum_n=1^infty[fracx2^n]$$
From this, we get
$$g(2x)= sum_n=1^infty[frac2x2^n]=sum_n=1^infty[fracx2^n-1]$$
$$=sum_n=0^infty[fracx2^n]$$
$$=x+sum_n=1^infty[fracx2^n]$$
$$=x+g(x)$$
From this we get $g(2n)=n+g(n)$
If we take $n=2^km$, where $m$ is odd, we have
$$g(n) = g(2^km)= 2^k-1m+2^k-2m+....+2m+m+g(m)= 2^km-m+g(m)$$
$$=n-m + g(m-1)$$
w=We can repeat this again with $g(m-1)$ to get
$$g(n)=n-m +(m-1)-.... -(2^l+1)+(2^l-1)= n-sum 1 $$
Where $l$ is aninteger
The number of times we add $1$ in the above summation of $1$ is the number of times we have to apply the recursive algorithm. But the number of times we apply the algorithm is the same as the number of ones in the binary expansion of $n$. From this we get
$$g(n)=n-ktext k=number of 1s in binary expansion of n$$
This is the closed form of $g(n)$ for all $n$
answered Aug 15 at 10:20
Prathyush Poduval
2,165922
Should be $x!$ in the first line
– Rumpelstiltskin
Aug 15 at 10:22
@Rumpelstiltskin edited it
– Prathyush Poduval
Aug 15 at 10:29
Brilliant. Could you elaborate for me a little the expansion step $g(n) = g(2^k m)$? I try to derive it, calculating the equation with respect to $2^k$. I came so far: given $g(2^kx) = sum_n=1^infty frac2^kx2^n=sum_n=1^inftyfracx2^n-k = 2^k-1x + 2^k-2 x+ ... + 2x + x + sum_n=0^infty fracx2^n$. Is this the correct analogous to your formula?
– John Smith
Aug 15 at 11:34
1
Yes, it is the same as my formula since the last sum is the same as $g(x)$
– Prathyush Poduval
Aug 15 at 11:36
Brilliant, than I got it! Thank you.
– John Smith
Aug 15 at 15:37
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
The highest power of $2$ that divides $x!$ is
$$sum_n=1^infty[fracx2^n]$$
Which can be shown by counting techniques. Thus we get
$$g(x)=sum_n=1^infty[fracx2^n]$$
From this, we get
$$g(2x)= sum_n=1^infty[frac2x2^n]=sum_n=1^infty[fracx2^n-1]$$
$$=sum_n=0^infty[fracx2^n]$$
$$=x+sum_n=1^infty[fracx2^n]$$
$$=x+g(x)$$
From this we get $g(2n)=n+g(n)$
If we take $n=2^km$, where $m$ is odd, we have
$$g(n) = g(2^km)= 2^k-1m+2^k-2m+....+2m+m+g(m)= 2^km-m+g(m)$$
$$=n-m + g(m-1)$$
w=We can repeat this again with $g(m-1)$ to get
$$g(n)=n-m +(m-1)-.... -(2^l+1)+(2^l-1)= n-sum 1 $$
Where $l$ is aninteger
The number of times we add $1$ in the above summation of $1$ is the number of times we have to apply the recursive algorithm. But the number of times we apply the algorithm is the same as the number of ones in the binary expansion of $n$. From this we get
$$g(n)=n-ktext k=number of 1s in binary expansion of n$$
This is the closed form of $g(n)$ for all $n$
answered Aug 15 at 10:20
Prathyush Poduval
2,165922
Should be $x!$ in the first line
– Rumpelstiltskin
Aug 15 at 10:22
@Rumpelstiltskin edited it
– Prathyush Poduval
Aug 15 at 10:29
Brilliant. Could you elaborate for me a little the expansion step $g(n) = g(2^k m)$? I try to derive it, calculating the equation with respect to $2^k$. I came so far: given $g(2^kx) = sum_n=1^infty frac2^kx2^n=sum_n=1^inftyfracx2^n-k = 2^k-1x + 2^k-2 x+ ... + 2x + x + sum_n=0^infty fracx2^n$. Is this the correct analogous to your formula?
– John Smith
Aug 15 at 11:34
1
Yes, it is the same as my formula since the last sum is the same as $g(x)$
– Prathyush Poduval
Aug 15 at 11:36
Brilliant, than I got it! Thank you.
– John Smith
Aug 15 at 15:37
add a comment |Â
up vote
2
down vote
accepted
The highest power of $2$ that divides $x!$ is
$$sum_n=1^infty[fracx2^n]$$
Which can be shown by counting techniques. Thus we get
$$g(x)=sum_n=1^infty[fracx2^n]$$
From this, we get
$$g(2x)= sum_n=1^infty[frac2x2^n]=sum_n=1^infty[fracx2^n-1]$$
$$=sum_n=0^infty[fracx2^n]$$
$$=x+sum_n=1^infty[fracx2^n]$$
$$=x+g(x)$$
From this we get $g(2n)=n+g(n)$
If we take $n=2^km$, where $m$ is odd, we have
$$g(n) = g(2^km)= 2^k-1m+2^k-2m+....+2m+m+g(m)= 2^km-m+g(m)$$
$$=n-m + g(m-1)$$
w=We can repeat this again with $g(m-1)$ to get
$$g(n)=n-m +(m-1)-.... -(2^l+1)+(2^l-1)= n-sum 1 $$
Where $l$ is aninteger
The number of times we add $1$ in the above summation of $1$ is the number of times we have to apply the recursive algorithm. But the number of times we apply the algorithm is the same as the number of ones in the binary expansion of $n$. From this we get
$$g(n)=n-ktext k=number of 1s in binary expansion of n$$
This is the closed form of $g(n)$ for all $n$
answered Aug 15 at 10:20
Prathyush Poduval
2,165922
Should be $x!$ in the first line
– Rumpelstiltskin
Aug 15 at 10:22
@Rumpelstiltskin edited it
– Prathyush Poduval
Aug 15 at 10:29
Brilliant. Could you elaborate for me a little the expansion step $g(n) = g(2^k m)$? I try to derive it, calculating the equation with respect to $2^k$. I came so far: given $g(2^kx) = sum_n=1^infty frac2^kx2^n=sum_n=1^inftyfracx2^n-k = 2^k-1x + 2^k-2 x+ ... + 2x + x + sum_n=0^infty fracx2^n$. Is this the correct analogous to your formula?
– John Smith
Aug 15 at 11:34
1
Yes, it is the same as my formula since the last sum is the same as $g(x)$
– Prathyush Poduval
Aug 15 at 11:36
Brilliant, than I got it! Thank you.
– John Smith
Aug 15 at 15:37
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
The highest power of $2$ that divides $x!$ is
$$sum_n=1^infty[fracx2^n]$$
Which can be shown by counting techniques. Thus we get
$$g(x)=sum_n=1^infty[fracx2^n]$$
From this, we get
$$g(2x)= sum_n=1^infty[frac2x2^n]=sum_n=1^infty[fracx2^n-1]$$
$$=sum_n=0^infty[fracx2^n]$$
$$=x+sum_n=1^infty[fracx2^n]$$
$$=x+g(x)$$
From this we get $g(2n)=n+g(n)$
If we take $n=2^km$, where $m$ is odd, we have
$$g(n) = g(2^km)= 2^k-1m+2^k-2m+....+2m+m+g(m)= 2^km-m+g(m)$$
$$=n-m + g(m-1)$$
w=We can repeat this again with $g(m-1)$ to get
$$g(n)=n-m +(m-1)-.... -(2^l+1)+(2^l-1)= n-sum 1 $$
Where $l$ is aninteger
The number of times we add $1$ in the above summation of $1$ is the number of times we have to apply the recursive algorithm. But the number of times we apply the algorithm is the same as the number of ones in the binary expansion of $n$. From this we get
$$g(n)=n-ktext k=number of 1s in binary expansion of n$$
This is the closed form of $g(n)$ for all $n$
answered Aug 15 at 10:20
Prathyush Poduval
2,165922
The highest power of $2$ that divides $x!$ is
$$sum_n=1^infty[fracx2^n]$$
Which can be shown by counting techniques. Thus we get
$$g(x)=sum_n=1^infty[fracx2^n]$$
From this, we get
$$g(2x)= sum_n=1^infty[frac2x2^n]=sum_n=1^infty[fracx2^n-1]$$
$$=sum_n=0^infty[fracx2^n]$$
$$=x+sum_n=1^infty[fracx2^n]$$
$$=x+g(x)$$
From this we get $g(2n)=n+g(n)$
If we take $n=2^km$, where $m$ is odd, we have
$$g(n) = g(2^km)= 2^k-1m+2^k-2m+....+2m+m+g(m)= 2^km-m+g(m)$$
$$=n-m + g(m-1)$$
w=We can repeat this again with $g(m-1)$ to get
$$g(n)=n-m +(m-1)-.... -(2^l+1)+(2^l-1)= n-sum 1 $$
Where $l$ is aninteger
The number of times we add $1$ in the above summation of $1$ is the number of times we have to apply the recursive algorithm. But the number of times we apply the algorithm is the same as the number of ones in the binary expansion of $n$. From this we get
$$g(n)=n-ktext k=number of 1s in binary expansion of n$$
This is the closed form of $g(n)$ for all $n$
answered Aug 15 at 10:20
Prathyush Poduval
2,165922
edited Aug 15 at 10:27
answered Aug 15 at 10:20
Prathyush Poduval
2,165922
answered Aug 15 at 10:20
Prathyush Poduval
2,165922
answered Aug 15 at 10:20
Prathyush Poduval
2,165922
2,165922
Should be $x!$ in the first line
– Rumpelstiltskin
Aug 15 at 10:22
@Rumpelstiltskin edited it
– Prathyush Poduval
Aug 15 at 10:29
Brilliant. Could you elaborate for me a little the expansion step $g(n) = g(2^k m)$? I try to derive it, calculating the equation with respect to $2^k$. I came so far: given $g(2^kx) = sum_n=1^infty frac2^kx2^n=sum_n=1^inftyfracx2^n-k = 2^k-1x + 2^k-2 x+ ... + 2x + x + sum_n=0^infty fracx2^n$. Is this the correct analogous to your formula?
– John Smith
Aug 15 at 11:34
1
Yes, it is the same as my formula since the last sum is the same as $g(x)$
– Prathyush Poduval
Aug 15 at 11:36
Brilliant, than I got it! Thank you.
– John Smith
Aug 15 at 15:37
add a comment |Â
Should be $x!$ in the first line
– Rumpelstiltskin
Aug 15 at 10:22
@Rumpelstiltskin edited it
– Prathyush Poduval
Aug 15 at 10:29
Brilliant. Could you elaborate for me a little the expansion step $g(n) = g(2^k m)$? I try to derive it, calculating the equation with respect to $2^k$. I came so far: given $g(2^kx) = sum_n=1^infty frac2^kx2^n=sum_n=1^inftyfracx2^n-k = 2^k-1x + 2^k-2 x+ ... + 2x + x + sum_n=0^infty fracx2^n$. Is this the correct analogous to your formula?
– John Smith
Aug 15 at 11:34
1
Yes, it is the same as my formula since the last sum is the same as $g(x)$
– Prathyush Poduval
Aug 15 at 11:36
Brilliant, than I got it! Thank you.
– John Smith
Aug 15 at 15:37
Should be $x!$ in the first line
– Rumpelstiltskin
Aug 15 at 10:22
Should be $x!$ in the first line
– Rumpelstiltskin
Aug 15 at 10:22
@Rumpelstiltskin edited it
– Prathyush Poduval
Aug 15 at 10:29
@Rumpelstiltskin edited it
– Prathyush Poduval
Aug 15 at 10:29
Brilliant. Could you elaborate for me a little the expansion step $g(n) = g(2^k m)$? I try to derive it, calculating the equation with respect to $2^k$. I came so far: given $g(2^kx) = sum_n=1^infty frac2^kx2^n=sum_n=1^inftyfracx2^n-k = 2^k-1x + 2^k-2 x+ ... + 2x + x + sum_n=0^infty fracx2^n$. Is this the correct analogous to your formula?
– John Smith
Aug 15 at 11:34
Brilliant. Could you elaborate for me a little the expansion step $g(n) = g(2^k m)$? I try to derive it, calculating the equation with respect to $2^k$. I came so far: given $g(2^kx) = sum_n=1^infty frac2^kx2^n=sum_n=1^inftyfracx2^n-k = 2^k-1x + 2^k-2 x+ ... + 2x + x + sum_n=0^infty fracx2^n$. Is this the correct analogous to your formula?
– John Smith
Aug 15 at 11:34
1
1
Yes, it is the same as my formula since the last sum is the same as $g(x)$
– Prathyush Poduval
Aug 15 at 11:36
Yes, it is the same as my formula since the last sum is the same as $g(x)$
– Prathyush Poduval
Aug 15 at 11:36
Brilliant, than I got it! Thank you.
– John Smith
Aug 15 at 15:37
Brilliant, than I got it! Thank you.
– John Smith
Aug 15 at 15:37
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2883413%2fthoughts-about-the-lucas-theorem%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
This is an useful (in terms of calculating) formula $g(n) = sum_i=1^infty lfloor fracn2^i rfloor $ (note that the sum is finite)
– Rumpelstiltskin
Aug 15 at 10:16