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