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