Sum of set bits in every element for a natural numbers
I was thinking of a mathematical puzzle with binary representation of numbers, but could not find a convincing answer myself.
Here is the puzzle: Say for some number N, I want to find the sum of the set bits of every number from 1 to N.
For example, for 5
The answer would be: 7 by the following procedure
1 - 1 set bit
2 - 1 set bit
3 - 2 set bits
4 - 1 set bit
5 - 2 set bits
So answer is 1 + 1 + 2 + 1 + 2 = 7
I found that it's easy to just go one by one and add, like I did. I also found that for a number having x bits, they form the pascal triangle with set ones, if number of occurances are counted with same number of set bits, irrespective of value. For example,
when x = 1, we have {1} - 1 set bit occurs once, hence 1.
when x = 2, we have {10, 11} - 1 set bit occurs once, 2 set bits occurs once, hence 1 1
when x = 3, we have {100, 101, 110, 111} - 1 set bit occurs once, 2 set bits occur twice, and 3 set bits occur once, hence 1 2 1
This series is continued. However, summing these up will give me a range, inside of which the answer lies. (Example ans is in [8, 15])
My first solution is the naive approach. Second one is a little mathematical, but not very fruitful.
I was wondering if we could derive a formula any N?
sequences-and-series binomial-coefficients puzzle binary
asked 2 days ago
metamemelordmetamemelord
134
New contributor
metamemelord is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
I was thinking of a mathematical puzzle with binary representation of numbers, but could not find a convincing answer myself.
Here is the puzzle: Say for some number N, I want to find the sum of the set bits of every number from 1 to N.
For example, for 5
The answer would be: 7 by the following procedure
1 - 1 set bit
2 - 1 set bit
3 - 2 set bits
4 - 1 set bit
5 - 2 set bits
So answer is 1 + 1 + 2 + 1 + 2 = 7
I found that it's easy to just go one by one and add, like I did. I also found that for a number having x bits, they form the pascal triangle with set ones, if number of occurances are counted with same number of set bits, irrespective of value. For example,
when x = 1, we have {1} - 1 set bit occurs once, hence 1.
when x = 2, we have {10, 11} - 1 set bit occurs once, 2 set bits occurs once, hence 1 1
when x = 3, we have {100, 101, 110, 111} - 1 set bit occurs once, 2 set bits occur twice, and 3 set bits occur once, hence 1 2 1
This series is continued. However, summing these up will give me a range, inside of which the answer lies. (Example ans is in [8, 15])
My first solution is the naive approach. Second one is a little mathematical, but not very fruitful.
I was wondering if we could derive a formula any N?
sequences-and-series binomial-coefficients puzzle binary
asked 2 days ago
metamemelordmetamemelord
134
New contributor
metamemelord is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
“5 - 1 set bit” ... ???
– Martin R
2 days ago
Have a look at math.stackexchange.com/q/2415630/42969.
– Martin R
2 days ago
One easily sees that F(2^k-1) = k 2^(k-1) . My guess is that a general formula, however, is almost certainly guaranteed to be either recursive, or messy.
– Ron Kaminsky
2 days ago
@MartinR thanks for pointing out the mistake with 5 and tagging this answer. Will definitely check, thanks a lot! :D
– metamemelord
2 days ago
@RonKaminsky amazing stuff, sir. I verified for a couple of values, it seems to fit. However, how exactly did you find pattern? :p
– metamemelord
2 days ago
add a comment |
I was thinking of a mathematical puzzle with binary representation of numbers, but could not find a convincing answer myself.
Here is the puzzle: Say for some number N, I want to find the sum of the set bits of every number from 1 to N.
For example, for 5
The answer would be: 7 by the following procedure
1 - 1 set bit
2 - 1 set bit
3 - 2 set bits
4 - 1 set bit
5 - 2 set bits
So answer is 1 + 1 + 2 + 1 + 2 = 7
I found that it's easy to just go one by one and add, like I did. I also found that for a number having x bits, they form the pascal triangle with set ones, if number of occurances are counted with same number of set bits, irrespective of value. For example,
when x = 1, we have {1} - 1 set bit occurs once, hence 1.
when x = 2, we have {10, 11} - 1 set bit occurs once, 2 set bits occurs once, hence 1 1
when x = 3, we have {100, 101, 110, 111} - 1 set bit occurs once, 2 set bits occur twice, and 3 set bits occur once, hence 1 2 1
This series is continued. However, summing these up will give me a range, inside of which the answer lies. (Example ans is in [8, 15])
My first solution is the naive approach. Second one is a little mathematical, but not very fruitful.
I was wondering if we could derive a formula any N?
sequences-and-series binomial-coefficients puzzle binary
asked 2 days ago
metamemelordmetamemelord
134
New contributor
metamemelord is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
I was thinking of a mathematical puzzle with binary representation of numbers, but could not find a convincing answer myself.
Here is the puzzle: Say for some number N, I want to find the sum of the set bits of every number from 1 to N.
For example, for 5
The answer would be: 7 by the following procedure
1 - 1 set bit
2 - 1 set bit
3 - 2 set bits
4 - 1 set bit
5 - 2 set bits
So answer is 1 + 1 + 2 + 1 + 2 = 7
I found that it's easy to just go one by one and add, like I did. I also found that for a number having x bits, they form the pascal triangle with set ones, if number of occurances are counted with same number of set bits, irrespective of value. For example,
when x = 1, we have {1} - 1 set bit occurs once, hence 1.
when x = 2, we have {10, 11} - 1 set bit occurs once, 2 set bits occurs once, hence 1 1
when x = 3, we have {100, 101, 110, 111} - 1 set bit occurs once, 2 set bits occur twice, and 3 set bits occur once, hence 1 2 1
This series is continued. However, summing these up will give me a range, inside of which the answer lies. (Example ans is in [8, 15])
My first solution is the naive approach. Second one is a little mathematical, but not very fruitful.
I was wondering if we could derive a formula any N?
sequences-and-series binomial-coefficients puzzle binary
sequences-and-series binomial-coefficients puzzle binary
asked 2 days ago
metamemelordmetamemelord
134
New contributor
metamemelord is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 2 days ago
metamemelordmetamemelord
134
New contributor
metamemelord is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 2 days ago
metamemelord
asked 2 days ago
metamemelordmetamemelord
134
New contributor
metamemelord is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 2 days ago
metamemelordmetamemelord
134
asked 2 days ago
metamemelordmetamemelord
134
134
New contributor
metamemelord is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
metamemelord is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
metamemelord is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
“5 - 1 set bit” ... ???
– Martin R
2 days ago
Have a look at math.stackexchange.com/q/2415630/42969.
– Martin R
2 days ago
One easily sees that F(2^k-1) = k 2^(k-1) . My guess is that a general formula, however, is almost certainly guaranteed to be either recursive, or messy.
– Ron Kaminsky
2 days ago
@MartinR thanks for pointing out the mistake with 5 and tagging this answer. Will definitely check, thanks a lot! :D
– metamemelord
2 days ago
@RonKaminsky amazing stuff, sir. I verified for a couple of values, it seems to fit. However, how exactly did you find pattern? :p
– metamemelord
2 days ago
add a comment |
“5 - 1 set bit” ... ???
– Martin R
2 days ago
Have a look at math.stackexchange.com/q/2415630/42969.
– Martin R
2 days ago
One easily sees that F(2^k-1) = k 2^(k-1) . My guess is that a general formula, however, is almost certainly guaranteed to be either recursive, or messy.
– Ron Kaminsky
2 days ago
@MartinR thanks for pointing out the mistake with 5 and tagging this answer. Will definitely check, thanks a lot! :D
– metamemelord
2 days ago
@RonKaminsky amazing stuff, sir. I verified for a couple of values, it seems to fit. However, how exactly did you find pattern? :p
– metamemelord
2 days ago
“5 - 1 set bit” ... ???
– Martin R
2 days ago
“5 - 1 set bit” ... ???
– Martin R
2 days ago
Have a look at math.stackexchange.com/q/2415630/42969.
– Martin R
2 days ago
Have a look at math.stackexchange.com/q/2415630/42969.
– Martin R
2 days ago
One easily sees that F(2^k-1) = k 2^(k-1) . My guess is that a general formula, however, is almost certainly guaranteed to be either recursive, or messy.
– Ron Kaminsky
2 days ago
One easily sees that F(2^k-1) = k 2^(k-1) . My guess is that a general formula, however, is almost certainly guaranteed to be either recursive, or messy.
– Ron Kaminsky
2 days ago
@MartinR thanks for pointing out the mistake with 5 and tagging this answer. Will definitely check, thanks a lot! :D
– metamemelord
2 days ago
@MartinR thanks for pointing out the mistake with 5 and tagging this answer. Will definitely check, thanks a lot! :D
– metamemelord
2 days ago
@RonKaminsky amazing stuff, sir. I verified for a couple of values, it seems to fit. However, how exactly did you find pattern? :p
– metamemelord
2 days ago
@RonKaminsky amazing stuff, sir. I verified for a couple of values, it seems to fit. However, how exactly did you find pattern? :p
– metamemelord
2 days ago
add a comment |
2 Answers
2
active
oldest
votes
$F(0) = 0.$
If $2^k le n lt 2^{k+1}$, then $F(n) = F(n - 2^k) + F(2^k - 1) + n - 2^k + 1$.
Since $F(2^k -1) = k,2^{k-1}$, we have $F(n) = F(n-2^k) + k,2^{k-1} + n - 2^k + 1$.
The recursion works because the numbers between $2^k$ and $n$ all have their highest bit set (those bits give the $n - 2^k + 1$ part of the sum), and the sum of the other bits of those numbers is $F(n - 2^k)$, and the remaining numbers are taken care of by the $F(2^k-1)$ term.
The formula for $F(2^k-1)$ works because each of the $k$ bits of the numbers in ${0, 1,dots, 2^k - 1}$ is $1$ exactly half of the time.
answered 2 days ago
Ron KaminskyRon Kaminsky
1428
Now let the next highest set bit in $n$ be in the $2^m$ position. We can use your recurrence to get $F(n)=F(n-2^k-2^m)+k2^{k-1}+m2^{m-1}+(n-2^k+1)+(n-2^k-2^m+1)$. A bit in the $2^b$ position contributes $b2^{b-1}$ from the first part and $2^b$ times the number of higher bits in the number from the second part. Finally the $+1$s give the total number of bits in the number. For the example of $5=101_2$ we get $2cdot2^{2-1}+1cdot 2^0+2=7$
– Ross Millikan
2 days ago
@RossMillikan For a little while I thought that there would be an elegant summation form over the bits which are set in $n$, but as you point out in your comment, the $(n-2^k-2^m+1)$ does depend on both $k$ and $m$ and not just $m$.
– Ron Kaminsky
2 days ago
add a comment |
Not a clean formula, but using Legendre's formula (see Alternate form) and this it can be shown that:
$$F(n) = frac{(n+1)n}{2}+sum_{k=1}^{lfloor{n/2}rfloor}{(2k-1)[(lfloorlog_2{(n/(2k-1))}rfloor-1)2^{lfloorlog_2{(n/(2k-1))}rfloor+1}+2]-(n+1)frac{(lfloorlog_2{(n/(2k-1))}rfloor+1)lfloorlog_2{(n/(2k-1))}rfloor}{2}}$$
where the following identity is used:
$$nu_2(n) =nu_2left({n choose 1}right) = nu_2left({n choose n-1}right) = nu_2left(frac{n!}{(n-1)!}right) = nu_2(n!)-nu_2((n-1)!) = n-s_2(n)-n+1+s_2(n-1) = s_2(n-1)+1-s_2(n)$$
where $nu_2(n)$ is the 2-adic valuation of $n$ and $s_2(n)$ is the sum of ones in the binary representation of $n$.
answered yesterday
mbjoembjoe
164119
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
metamemelord is a new contributor. Be nice, and check out our Code of Conduct.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3063186%2fsum-of-set-bits-in-every-element-for-a-natural-numbers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$F(0) = 0.$
If $2^k le n lt 2^{k+1}$, then $F(n) = F(n - 2^k) + F(2^k - 1) + n - 2^k + 1$.
Since $F(2^k -1) = k,2^{k-1}$, we have $F(n) = F(n-2^k) + k,2^{k-1} + n - 2^k + 1$.
The recursion works because the numbers between $2^k$ and $n$ all have their highest bit set (those bits give the $n - 2^k + 1$ part of the sum), and the sum of the other bits of those numbers is $F(n - 2^k)$, and the remaining numbers are taken care of by the $F(2^k-1)$ term.
The formula for $F(2^k-1)$ works because each of the $k$ bits of the numbers in ${0, 1,dots, 2^k - 1}$ is $1$ exactly half of the time.
answered 2 days ago
Ron KaminskyRon Kaminsky
1428
Now let the next highest set bit in $n$ be in the $2^m$ position. We can use your recurrence to get $F(n)=F(n-2^k-2^m)+k2^{k-1}+m2^{m-1}+(n-2^k+1)+(n-2^k-2^m+1)$. A bit in the $2^b$ position contributes $b2^{b-1}$ from the first part and $2^b$ times the number of higher bits in the number from the second part. Finally the $+1$s give the total number of bits in the number. For the example of $5=101_2$ we get $2cdot2^{2-1}+1cdot 2^0+2=7$
– Ross Millikan
2 days ago
@RossMillikan For a little while I thought that there would be an elegant summation form over the bits which are set in $n$, but as you point out in your comment, the $(n-2^k-2^m+1)$ does depend on both $k$ and $m$ and not just $m$.
– Ron Kaminsky
2 days ago
add a comment |
$F(0) = 0.$
If $2^k le n lt 2^{k+1}$, then $F(n) = F(n - 2^k) + F(2^k - 1) + n - 2^k + 1$.
Since $F(2^k -1) = k,2^{k-1}$, we have $F(n) = F(n-2^k) + k,2^{k-1} + n - 2^k + 1$.
The recursion works because the numbers between $2^k$ and $n$ all have their highest bit set (those bits give the $n - 2^k + 1$ part of the sum), and the sum of the other bits of those numbers is $F(n - 2^k)$, and the remaining numbers are taken care of by the $F(2^k-1)$ term.
The formula for $F(2^k-1)$ works because each of the $k$ bits of the numbers in ${0, 1,dots, 2^k - 1}$ is $1$ exactly half of the time.
answered 2 days ago
Ron KaminskyRon Kaminsky
1428
Now let the next highest set bit in $n$ be in the $2^m$ position. We can use your recurrence to get $F(n)=F(n-2^k-2^m)+k2^{k-1}+m2^{m-1}+(n-2^k+1)+(n-2^k-2^m+1)$. A bit in the $2^b$ position contributes $b2^{b-1}$ from the first part and $2^b$ times the number of higher bits in the number from the second part. Finally the $+1$s give the total number of bits in the number. For the example of $5=101_2$ we get $2cdot2^{2-1}+1cdot 2^0+2=7$
– Ross Millikan
2 days ago
@RossMillikan For a little while I thought that there would be an elegant summation form over the bits which are set in $n$, but as you point out in your comment, the $(n-2^k-2^m+1)$ does depend on both $k$ and $m$ and not just $m$.
– Ron Kaminsky
2 days ago
add a comment |
$F(0) = 0.$
If $2^k le n lt 2^{k+1}$, then $F(n) = F(n - 2^k) + F(2^k - 1) + n - 2^k + 1$.
Since $F(2^k -1) = k,2^{k-1}$, we have $F(n) = F(n-2^k) + k,2^{k-1} + n - 2^k + 1$.
The recursion works because the numbers between $2^k$ and $n$ all have their highest bit set (those bits give the $n - 2^k + 1$ part of the sum), and the sum of the other bits of those numbers is $F(n - 2^k)$, and the remaining numbers are taken care of by the $F(2^k-1)$ term.
The formula for $F(2^k-1)$ works because each of the $k$ bits of the numbers in ${0, 1,dots, 2^k - 1}$ is $1$ exactly half of the time.
answered 2 days ago
Ron KaminskyRon Kaminsky
1428
$F(0) = 0.$
If $2^k le n lt 2^{k+1}$, then $F(n) = F(n - 2^k) + F(2^k - 1) + n - 2^k + 1$.
Since $F(2^k -1) = k,2^{k-1}$, we have $F(n) = F(n-2^k) + k,2^{k-1} + n - 2^k + 1$.
The recursion works because the numbers between $2^k$ and $n$ all have their highest bit set (those bits give the $n - 2^k + 1$ part of the sum), and the sum of the other bits of those numbers is $F(n - 2^k)$, and the remaining numbers are taken care of by the $F(2^k-1)$ term.
The formula for $F(2^k-1)$ works because each of the $k$ bits of the numbers in ${0, 1,dots, 2^k - 1}$ is $1$ exactly half of the time.
answered 2 days ago
Ron KaminskyRon Kaminsky
1428
edited 2 days ago
answered 2 days ago
Ron KaminskyRon Kaminsky
1428
answered 2 days ago
Ron KaminskyRon Kaminsky
1428
answered 2 days ago
Ron KaminskyRon Kaminsky
1428
1428
Now let the next highest set bit in $n$ be in the $2^m$ position. We can use your recurrence to get $F(n)=F(n-2^k-2^m)+k2^{k-1}+m2^{m-1}+(n-2^k+1)+(n-2^k-2^m+1)$. A bit in the $2^b$ position contributes $b2^{b-1}$ from the first part and $2^b$ times the number of higher bits in the number from the second part. Finally the $+1$s give the total number of bits in the number. For the example of $5=101_2$ we get $2cdot2^{2-1}+1cdot 2^0+2=7$
– Ross Millikan
2 days ago
@RossMillikan For a little while I thought that there would be an elegant summation form over the bits which are set in $n$, but as you point out in your comment, the $(n-2^k-2^m+1)$ does depend on both $k$ and $m$ and not just $m$.
– Ron Kaminsky
2 days ago
add a comment |
Now let the next highest set bit in $n$ be in the $2^m$ position. We can use your recurrence to get $F(n)=F(n-2^k-2^m)+k2^{k-1}+m2^{m-1}+(n-2^k+1)+(n-2^k-2^m+1)$. A bit in the $2^b$ position contributes $b2^{b-1}$ from the first part and $2^b$ times the number of higher bits in the number from the second part. Finally the $+1$s give the total number of bits in the number. For the example of $5=101_2$ we get $2cdot2^{2-1}+1cdot 2^0+2=7$
– Ross Millikan
2 days ago
@RossMillikan For a little while I thought that there would be an elegant summation form over the bits which are set in $n$, but as you point out in your comment, the $(n-2^k-2^m+1)$ does depend on both $k$ and $m$ and not just $m$.
– Ron Kaminsky
2 days ago
Now let the next highest set bit in $n$ be in the $2^m$ position. We can use your recurrence to get $F(n)=F(n-2^k-2^m)+k2^{k-1}+m2^{m-1}+(n-2^k+1)+(n-2^k-2^m+1)$. A bit in the $2^b$ position contributes $b2^{b-1}$ from the first part and $2^b$ times the number of higher bits in the number from the second part. Finally the $+1$s give the total number of bits in the number. For the example of $5=101_2$ we get $2cdot2^{2-1}+1cdot 2^0+2=7$
– Ross Millikan
2 days ago
Now let the next highest set bit in $n$ be in the $2^m$ position. We can use your recurrence to get $F(n)=F(n-2^k-2^m)+k2^{k-1}+m2^{m-1}+(n-2^k+1)+(n-2^k-2^m+1)$. A bit in the $2^b$ position contributes $b2^{b-1}$ from the first part and $2^b$ times the number of higher bits in the number from the second part. Finally the $+1$s give the total number of bits in the number. For the example of $5=101_2$ we get $2cdot2^{2-1}+1cdot 2^0+2=7$
– Ross Millikan
2 days ago
@RossMillikan For a little while I thought that there would be an elegant summation form over the bits which are set in $n$, but as you point out in your comment, the $(n-2^k-2^m+1)$ does depend on both $k$ and $m$ and not just $m$.
– Ron Kaminsky
2 days ago
@RossMillikan For a little while I thought that there would be an elegant summation form over the bits which are set in $n$, but as you point out in your comment, the $(n-2^k-2^m+1)$ does depend on both $k$ and $m$ and not just $m$.
– Ron Kaminsky
2 days ago
add a comment |
Not a clean formula, but using Legendre's formula (see Alternate form) and this it can be shown that:
$$F(n) = frac{(n+1)n}{2}+sum_{k=1}^{lfloor{n/2}rfloor}{(2k-1)[(lfloorlog_2{(n/(2k-1))}rfloor-1)2^{lfloorlog_2{(n/(2k-1))}rfloor+1}+2]-(n+1)frac{(lfloorlog_2{(n/(2k-1))}rfloor+1)lfloorlog_2{(n/(2k-1))}rfloor}{2}}$$
where the following identity is used:
$$nu_2(n) =nu_2left({n choose 1}right) = nu_2left({n choose n-1}right) = nu_2left(frac{n!}{(n-1)!}right) = nu_2(n!)-nu_2((n-1)!) = n-s_2(n)-n+1+s_2(n-1) = s_2(n-1)+1-s_2(n)$$
where $nu_2(n)$ is the 2-adic valuation of $n$ and $s_2(n)$ is the sum of ones in the binary representation of $n$.
answered yesterday
mbjoembjoe
164119
add a comment |
Not a clean formula, but using Legendre's formula (see Alternate form) and this it can be shown that:
$$F(n) = frac{(n+1)n}{2}+sum_{k=1}^{lfloor{n/2}rfloor}{(2k-1)[(lfloorlog_2{(n/(2k-1))}rfloor-1)2^{lfloorlog_2{(n/(2k-1))}rfloor+1}+2]-(n+1)frac{(lfloorlog_2{(n/(2k-1))}rfloor+1)lfloorlog_2{(n/(2k-1))}rfloor}{2}}$$
where the following identity is used:
$$nu_2(n) =nu_2left({n choose 1}right) = nu_2left({n choose n-1}right) = nu_2left(frac{n!}{(n-1)!}right) = nu_2(n!)-nu_2((n-1)!) = n-s_2(n)-n+1+s_2(n-1) = s_2(n-1)+1-s_2(n)$$
where $nu_2(n)$ is the 2-adic valuation of $n$ and $s_2(n)$ is the sum of ones in the binary representation of $n$.
answered yesterday
mbjoembjoe
164119
add a comment |
Not a clean formula, but using Legendre's formula (see Alternate form) and this it can be shown that:
$$F(n) = frac{(n+1)n}{2}+sum_{k=1}^{lfloor{n/2}rfloor}{(2k-1)[(lfloorlog_2{(n/(2k-1))}rfloor-1)2^{lfloorlog_2{(n/(2k-1))}rfloor+1}+2]-(n+1)frac{(lfloorlog_2{(n/(2k-1))}rfloor+1)lfloorlog_2{(n/(2k-1))}rfloor}{2}}$$
where the following identity is used:
$$nu_2(n) =nu_2left({n choose 1}right) = nu_2left({n choose n-1}right) = nu_2left(frac{n!}{(n-1)!}right) = nu_2(n!)-nu_2((n-1)!) = n-s_2(n)-n+1+s_2(n-1) = s_2(n-1)+1-s_2(n)$$
where $nu_2(n)$ is the 2-adic valuation of $n$ and $s_2(n)$ is the sum of ones in the binary representation of $n$.
answered yesterday
mbjoembjoe
164119
Not a clean formula, but using Legendre's formula (see Alternate form) and this it can be shown that:
$$F(n) = frac{(n+1)n}{2}+sum_{k=1}^{lfloor{n/2}rfloor}{(2k-1)[(lfloorlog_2{(n/(2k-1))}rfloor-1)2^{lfloorlog_2{(n/(2k-1))}rfloor+1}+2]-(n+1)frac{(lfloorlog_2{(n/(2k-1))}rfloor+1)lfloorlog_2{(n/(2k-1))}rfloor}{2}}$$
where the following identity is used:
$$nu_2(n) =nu_2left({n choose 1}right) = nu_2left({n choose n-1}right) = nu_2left(frac{n!}{(n-1)!}right) = nu_2(n!)-nu_2((n-1)!) = n-s_2(n)-n+1+s_2(n-1) = s_2(n-1)+1-s_2(n)$$
where $nu_2(n)$ is the 2-adic valuation of $n$ and $s_2(n)$ is the sum of ones in the binary representation of $n$.
answered yesterday
mbjoembjoe
164119
edited 23 hours ago
answered yesterday
mbjoembjoe
164119
answered yesterday
mbjoembjoe
164119
answered yesterday
mbjoembjoe
164119
164119
add a comment |
add a comment |
metamemelord is a new contributor. Be nice, and check out our Code of Conduct.
metamemelord is a new contributor. Be nice, and check out our Code of Conduct.
metamemelord is a new contributor. Be nice, and check out our Code of Conduct.
metamemelord is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3063186%2fsum-of-set-bits-in-every-element-for-a-natural-numbers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
“5 - 1 set bit” ... ???
– Martin R
2 days ago
Have a look at math.stackexchange.com/q/2415630/42969.
– Martin R
2 days ago
One easily sees that F(2^k-1) = k 2^(k-1) . My guess is that a general formula, however, is almost certainly guaranteed to be either recursive, or messy.
– Ron Kaminsky
2 days ago
@MartinR thanks for pointing out the mistake with 5 and tagging this answer. Will definitely check, thanks a lot! :D
– metamemelord
2 days ago
@RonKaminsky amazing stuff, sir. I verified for a couple of values, it seems to fit. However, how exactly did you find pattern? :p
– metamemelord
2 days ago