[math-fun] sum of binary digits
Let n be a positive integer. Let g(n) be the sum of the binary digits of n. I am looking for interesting facts involving g(n). Here are 3 that i have so far, in increasing difficulty to prove: Theorem 1: The minimum number of integral powers of 2 to sum to n is g(n). Theorem 2: The highest power of 2 to divide n! is 2^[ n - g(n) ]. Theorem 3: The number of odd entries in the nth row of Pascal's Triangle is 2^[ g(n) ]. Anyone know any others? Erich Friedman
You will find a few things here: http://oeis.org/A000120 On Wed, Jun 1, 2016 at 8:10 PM, Erich Friedman <erichfriedman68@gmail.com> wrote:
Let n be a positive integer. Let g(n) be the sum of the binary digits of n. I am looking for interesting facts involving g(n). Here are 3 that i have so far, in increasing difficulty to prove:
Theorem 1: The minimum number of integral powers of 2 to sum to n is g(n).
Theorem 2: The highest power of 2 to divide n! is 2^[ n - g(n) ].
Theorem 3: The number of odd entries in the nth row of Pascal's Triangle is 2^[ g(n) ].
Anyone know any others?
Erich Friedman _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
An interesting result in topology is that for n > 1 every compact smooth n-manifold can be immersed* in the Euclidean space of dimension 2n - g(n). —Dan ________________________________________________ * An immersion is a smooth map between manifolds f: M —> W such that the derivative matrix Df(x) has rank = dim(M) at every x in M. This was a conjecture since before 1960 and was finally proved in 1985 by Ralph Cohen.
On Jun 1, 2016, at 5:10 PM, Erich Friedman <erichfriedman68@gmail.com> wrote:
Let n be a positive integer. Let g(n) be the sum of the binary digits of n. I am looking for interesting facts involving g(n). Here are 3 that i have so far, in increasing difficulty to prove:
Theorem 1: The minimum number of integral powers of 2 to sum to n is g(n).
Theorem 2: The highest power of 2 to divide n! is 2^[ n - g(n) ].
Theorem 3: The number of odd entries in the nth row of Pascal's Triangle is 2^[ g(n) ].
Anyone know any others?
P.S. I should've mentioned that this result is best possible: The real projective spaces P^n for n > 1 cannot be immersed in R^k for k < 2n - g(n). —Dan
On Jun 1, 2016, at 7:48 PM, Dan Asimov <asimov@msri.org> wrote:
An interesting result in topology is that for n > 1 every compact smooth n-manifold can be immersed* in the Euclidean space of dimension 2n - g(n).
—Dan ________________________________________________ * An immersion is a smooth map between manifolds
f: M —> W
such that the derivative matrix Df(x) has rank = dim(M) at every x in M.
This was a conjecture since before 1960 and was finally proved in 1985 by Ralph Cohen.
On Jun 1, 2016, at 5:10 PM, Erich Friedman <erichfriedman68@gmail.com> wrote:
Let n be a positive integer. Let g(n) be the sum of the binary digits of n. I am looking for interesting facts involving g(n). Here are 3 that i have so far, in increasing difficulty to prove:
Theorem 1: The minimum number of integral powers of 2 to sum to n is g(n).
Theorem 2: The highest power of 2 to divide n! is 2^[ n - g(n) ].
Theorem 3: The number of odd entries in the nth row of Pascal's Triangle is 2^[ g(n) ].
Anyone know any others?
ad Theorem 1: g(n) is *exactly* the number of integral powers of two that sum to n: Any integer n has a unique representation in any (positive integer) base b>=2 as n=sum_i a_i b^i (i>=0, 0<= a_i <= b-1) So we have n=sum_i a_i 2^i (i>=0, 0<=a_i<=1), and g(n)=sum_i a_i both with unique a_i. Christoph ________________________________________ From: math-fun [math-fun-bounces@mailman.xmission.com] on behalf of Erich Friedman [erichfriedman68@gmail.com] Sent: Thursday, June 02, 2016 2:11 AM To: math-fun Subject: [math-fun] sum of binary digits Let n be a positive integer. Let g(n) be the sum of the binary digits of n. I am looking for interesting facts involving g(n). Here are 3 that i have so far, in increasing difficulty to prove: Theorem 1: The minimum number of integral powers of 2 to sum to n is g(n). Theorem 2: The highest power of 2 to divide n! is 2^[ n - g(n) ]. Theorem 3: The number of odd entries in the nth row of Pascal's Triangle is 2^[ g(n) ]. Anyone know any others? Erich Friedman _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I think Knuth uses nu(n) for Hamming weight. I like v(n). It's as good as nu. OEIS mentions that v() satisfies a triangle inequality, v(a+b) <= v(a)+v(b). It neglects to mention multiplication: v(a*b) <= v(a)*v(b). Of course, v(a) <= a, and v(a&b) <= min(v(a),v(b)) <= v(a) and v(a) <= max(v(a),v(b)) <= v(a|b). [Using & for bitwise And, and vbar for bitwise Or. Also, using ^ (hat) for Xor ...] v(a^b) + v(a&b) = v(a|b). Probably we can do something with (a&b) + (a|b) = a+b, and a+b = (a^b) + 2(a&b). Maybe v(a+b) <= v(a^b) + v(a&b). Rich ------- Quoting Pacher Christoph <Christoph.Pacher@ait.ac.at>:
ad Theorem 1: g(n) is *exactly* the number of integral powers of two that sum to n:
Any integer n has a unique representation in any (positive integer) base b>=2 as n=sum_i a_i b^i (i>=0, 0<= a_i <= b-1)
So we have n=sum_i a_i 2^i (i>=0, 0<=a_i<=1), and g(n)=sum_i a_i both with unique a_i.
Christoph ________________________________________ From: math-fun [math-fun-bounces@mailman.xmission.com] on behalf of Erich Friedman [erichfriedman68@gmail.com] Sent: Thursday, June 02, 2016 2:11 AM To: math-fun Subject: [math-fun] sum of binary digits
Let n be a positive integer. Let g(n) be the sum of the binary digits of n. I am looking for interesting facts involving g(n). Here are 3 that i have so far, in increasing difficulty to prove:
Theorem 1: The minimum number of integral powers of 2 to sum to n is g(n).
Theorem 2: The highest power of 2 to divide n! is 2^[ n - g(n) ].
Theorem 3: The number of odd entries in the nth row of Pascal's Triangle is 2^[ g(n) ].
Anyone know any others?
Erich Friedman _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
A lot of these theorems are consequences of the fact that v(a) is, intuitively, really small compared with a; it has a sublogarithmic growth rate. So if x~y is any operation that is expected to be considerably bigger than x and y, then we can expect v(x~y) to be smaller than v(x)~v(y). I don't know how to rigorize this, though. On Thu, Jun 2, 2016 at 4:23 PM, <rcs@xmission.com> wrote:
I think Knuth uses nu(n) for Hamming weight. I like v(n). It's as good as nu. OEIS mentions that v() satisfies a triangle inequality, v(a+b) <= v(a)+v(b). It neglects to mention multiplication: v(a*b) <= v(a)*v(b). Of course, v(a) <= a, and v(a&b) <= min(v(a),v(b)) <= v(a) and v(a) <= max(v(a),v(b)) <= v(a|b). [Using & for bitwise And, and vbar for bitwise Or. Also, using ^ (hat) for Xor ...] v(a^b) + v(a&b) = v(a|b). Probably we can do something with (a&b) + (a|b) = a+b, and a+b = (a^b) + 2(a&b). Maybe v(a+b) <= v(a^b) + v(a&b).
Rich
-------
Quoting Pacher Christoph <Christoph.Pacher@ait.ac.at>:
ad Theorem 1:
g(n) is *exactly* the number of integral powers of two that sum to n:
Any integer n has a unique representation in any (positive integer) base b>=2 as n=sum_i a_i b^i (i>=0, 0<= a_i <= b-1)
So we have n=sum_i a_i 2^i (i>=0, 0<=a_i<=1), and g(n)=sum_i a_i both with unique a_i.
Christoph ________________________________________ From: math-fun [math-fun-bounces@mailman.xmission.com] on behalf of Erich Friedman [erichfriedman68@gmail.com] Sent: Thursday, June 02, 2016 2:11 AM To: math-fun Subject: [math-fun] sum of binary digits
Let n be a positive integer. Let g(n) be the sum of the binary digits of n. I am looking for interesting facts involving g(n). Here are 3 that i have so far, in increasing difficulty to prove:
Theorem 1: The minimum number of integral powers of 2 to sum to n is g(n).
Theorem 2: The highest power of 2 to divide n! is 2^[ n - g(n) ].
Theorem 3: The number of odd entries in the nth row of Pascal's Triangle is 2^[ g(n) ].
Anyone know any others?
Erich Friedman _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
A postscript: With v(a+b) <= v(a^b) + v(a&b) and v(a^b) + v(a&b) = v(a|b) we get v(a+b) <= v(a|b), which is a little bit interesting, since a+b >= a|b. Rich --- Quoting Allan Wechsler <acwacw@gmail.com>:
A lot of these theorems are consequences of the fact that v(a) is, intuitively, really small compared with a; it has a sublogarithmic growth rate. So if x~y is any operation that is expected to be considerably bigger than x and y, then we can expect v(x~y) to be smaller than v(x)~v(y). I don't know how to rigorize this, though.
On Thu, Jun 2, 2016 at 4:23 PM, <rcs@xmission.com> wrote:
I think Knuth uses nu(n) for Hamming weight. I like v(n). It's as good as nu. OEIS mentions that v() satisfies a triangle inequality, v(a+b) <= v(a)+v(b). It neglects to mention multiplication: v(a*b) <= v(a)*v(b). Of course, v(a) <= a, and v(a&b) <= min(v(a),v(b)) <= v(a) and v(a) <= max(v(a),v(b)) <= v(a|b). [Using & for bitwise And, and vbar for bitwise Or. Also, using ^ (hat) for Xor ...] v(a^b) + v(a&b) = v(a|b). Probably we can do something with (a&b) + (a|b) = a+b, and a+b = (a^b) + 2(a&b). Maybe v(a+b) <= v(a^b) + v(a&b).
Rich
-------
Quoting Pacher Christoph <Christoph.Pacher@ait.ac.at>:
ad Theorem 1:
g(n) is *exactly* the number of integral powers of two that sum to n:
Any integer n has a unique representation in any (positive integer) base b>=2 as n=sum_i a_i b^i (i>=0, 0<= a_i <= b-1)
So we have n=sum_i a_i 2^i (i>=0, 0<=a_i<=1), and g(n)=sum_i a_i both with unique a_i.
Christoph ________________________________________ From: math-fun [math-fun-bounces@mailman.xmission.com] on behalf of Erich Friedman [erichfriedman68@gmail.com] Sent: Thursday, June 02, 2016 2:11 AM To: math-fun Subject: [math-fun] sum of binary digits
Let n be a positive integer. Let g(n) be the sum of the binary digits of n. I am looking for interesting facts involving g(n). Here are 3 that i have so far, in increasing difficulty to prove:
Theorem 1: The minimum number of integral powers of 2 to sum to n is g(n).
Theorem 2: The highest power of 2 to divide n! is 2^[ n - g(n) ].
Theorem 3: The number of odd entries in the nth row of Pascal's Triangle is 2^[ g(n) ].
Anyone know any others?
Erich Friedman _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
* rcs@xmission.com <rcs@xmission.com> [Jun 03. 2016 08:44]:
[...] Probably we can do something with (a&b) + (a|b) = a+b, and a+b = (a^b) + 2(a&b). Maybe v(a+b) <= v(a^b) + v(a&b).
From a+b = (a^b) + 2(a&b) we get (a+b)/2 = (a^b)/2 + (a&b) so
static inline ulong average(ulong x, ulong y) // Return floor( (x+y)/2 ) // Result is correct even if (x+y) wouldn't fit into a ulong // Use: x+y == ((x&y)<<1) + (x^y) // that is: sum == carries + sum_without_carries { return (x & y) + ((x ^ y) >> 1); // return y + ((x-y)>>1); // works if x>=y } Similarly ulong ceil_average(ulong x, ulong y) // Return ceil( (x+y)/2 ) // Result is correct even if (x+y) wouldn't fit into a ulong // Use: x+y == ((x|y)<<1) - (x^y) // ceil_average(x,y) == average(x,y) + ((x^y)&1)) { return (x | y) - ((x ^ y) >> 1); } Best regards, jj
Rich
[...]
participants (7)
-
Allan Wechsler -
Dan Asimov -
Erich Friedman -
Joerg Arndt -
Pacher Christoph -
rcs＠xmission.com -
W. Edwin Clark