h(n) = (-1)^(parity of bit-sum of binary representation of n) f(x) S=SUM[ f(n) * h(n), for n=0..2^k-1 with k large] ln(x+1) S=-log(2)/2 ln(x+2) S = -0.1379330125 ln(x+3) -0.07070756527 x^j 0 for any fixed integer j>=0 1/(x+1) 0.398761088108 1/(x+2) 0.1049709156499 sqrt(x) -0.63407426 1/sqrt(x+1) 0.1983140804979 -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
On 7/6/14, Warren D Smith <warren.wds@gmail.com> wrote:
h(n) = (-1)^(parity of bit-sum of binary representation of n)
f(x) S=SUM[ f(n) * h(n), for n=0..2^k-1 with k large] ln(x+1) S=-log(2)/2 ln(x+2) S = -0.1379330125 ln(x+3) -0.07070756527 x^j 0 for any fixed integer j>=0 1/(x+1) 0.398761088108 1/(x+2) 0.1049709156499 sqrt(x) -0.63407426 1/sqrt(x+1) 0.1983140804979
--reminiscent of "Flanelle's theorem" Sum[ n^j * h(n), for n=0..2^k-1 ] = 0 if 0<=j<k with j=integer (and perhaps Adam P. Goucher will inform us... who the helle was Flanelle? I think it was actually Adam P. Goucher in disguise?) I find now a new closed form sum Sum[ C^n * h(n), for n=0..2^k-1 ] = (1-C)*(1-C^2)*(1-C^4)*...*(1-C^(2^(k-1))) To prove it, you work inductively layer by layer in the "Wilson binary tree" starting from leaves. At the leaf layer, we have C^n. At the next layer, fathers of leaves, we have by differencing (1-C) * C^(2*n). At the next layer, grandfathers of leaves, we have (1-C)*(1-C^2) * C^(4*n). And so on... at the the layer k+1 above the leaves we have (1-C) * (1-C^2) * (1-C^4) * ... * (1-C^(2^k)) * C^(2^(k+1) * n) ...and now evaluate this when n=0 at the layer k-1 above leaves, QED. You can also prove Flanelle by the same kind of layer-by-layer inductive approach, noting that differencing a polynomial of degree d, yields 0 after you do it more than d times. Note that our new sum also can be viewed as a "generating function(C)" for h(n). Well, isn't that nifty. Looking around for another nail to hit with my shiny new hammer, consider Sum[ h(n)*C^n/n!, for n=0..2^k-1 ] = ?? work inductively layer by layer in the "Wilson binary tree" starting from leaves. At the leaf layer, we have C^n / n!. At the next layer, fathers of leaves, we have by differencing (1-C/(2*n+1)) * C^(2*n) / (2*n)! Oh dear, this is getting yukky. To try to keep it simple, let's do C=1. Sum[ h(n)/n!, for n=0..2^k-1 ] = ?? At the leaf layer, we have 1 / n!. At the next layer, fathers of leaves, we have by differencing (1-1/(2*n+1)) / (2*n)! = 1/(2*n)! - 1/(2*n+1)! At the next layer, grandfathers of leaves, we have ...well... this one can be done. Actually the general C one can be done. You just have to stick it out, which I haven't. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
--reminiscent of "Flanelle's theorem" Sum[ n^j * h(n), for n=0..2^k-1 ] = 0 if 0<=j<k with j=integer
(and perhaps Adam P. Goucher will inform us... who the helle was Flanelle? I think it was actually Adam P. Goucher in disguise?)
That was the name suggested by `Maria' on the cp4space article: http://cp4space.wordpress.com/2013/08/14/polynomials-and-hamming-weights/#co...
I find now a new closed form sum Sum[ C^n * h(n), for n=0..2^k-1 ] = (1-C)*(1-C^2)*(1-C^4)*...*(1-C^(2^(k-1)))
Exciting.
To prove it, you work inductively layer by layer in the "Wilson binary tree" starting from leaves. At the leaf layer, we have C^n. At the next layer, fathers of leaves, we have by differencing (1-C) * C^(2*n). At the next layer, grandfathers of leaves, we have (1-C)*(1-C^2) * C^(4*n). And so on... at the the layer k+1 above the leaves we have (1-C) * (1-C^2) * (1-C^4) * ... * (1-C^(2^k)) * C^(2^(k+1) * n) ...and now evaluate this when n=0 at the layer k-1 above leaves, QED.
You can also prove Flanelle by the same kind of layer-by-layer inductive approach, noting that differencing a polynomial of degree d, yields 0 after you do it more than d times.
That's essentially the inductive approach I used for Flanelle(P).
Note that our new sum also can be viewed as a "generating function(C)" for h(n).
Indeed, that's mentioned here: http://en.wikipedia.org/wiki/Prouhet%E2%80%93Thue%E2%80%93Morse_constant Sincerely, Adam P. Goucher
On 7/6/14, Warren D Smith <warren.wds@gmail.com> wrote:
h(n) = (-1)^(parity of bit-sum of binary representation of n)
f(x) S=SUM[ f(n) * h(n), for n=0..2^k-1 with k large] ln(x+1) S=-log(2)/2 x^j 0 for any fixed integer j>=0
--Actually, it occurs to me that a slightly better way to prove "Flanelle's theorem" is to prove it using as your basis for polynomials, not the powers x^j, but rather the pseudo-powers x^^j = (x+j-1)! / (x-1)! which will be my ASCII notation for the "rising factorial" aka "Pochammer symbol" which if I had typesetting capability, I would write "x with superscript j, where the j has an overline" as opposed to the falling factorial x! / (x-j)! which I would write "x with superscript j, where the j has an underline" because those are far superior notations to the stupid ones you find in way too many putrid books written by people who like to confuse you with bad notations from hell. Also x^^1 = x, x^^0 = 1. The forward difference of x^^j is (x+1)^^j - x^^j = j * x^^(j-1) if j>0 which is the point -- powers are friendly with differentiation, but rising factorials are friendly with forward differencing. Indeed (Mx+1)^^j - (Mx)^^j = j * (Mx)^^(j-1). Right-o. So proceeding, we evaluate the Wilsonian sum Sum[ n^^j * h(n), for n=0..2^k-1 ] via the layer-by-layer inductive tree approach. At leaf layer we have n^^j. At the father-of leaves layer: -j * (2*n)^^(j-1). At grandfather of leaves layer: (-j) * (1-j) * (4*n)^^(j-2). And so on, at the layer k-1 above leaves we have (-j) * (1-j) * (2-j) * ... * (k-2-j) * (2^(k-1)*n)^^(j-k+1) which provides us with a closed form for the Wilsonian sum of a rising factorial (if power-of-two summands) which is a more powerful statement than Flanelle's theorem (which only told us the answer was 0 is you went too far, but did not tell us what happened if you went less far). -- Furthermore, in my previous evaluation of the Wilsonian sum of C^n, we can differentiate the resulting formula z times with respect to c, in this way evaluating in closed form, the Wilsonian sum of n^z*C^n. -- Now, returning to WIlson's original problem about log(2). Can we assault this problem with our new tools? Specifically, can the log function be written as a series involving rising factorials, or something? -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
On 7/6/14, Warren D Smith <warren.wds@gmail.com> wrote:
h(n) = (-1)^(parity of bit-sum of binary representation of n)
f(x) S=SUM[ f(n) * h(n), for n=0..2^k-1 with k large]
--incidentally, the hackers may enjoy the following problem: compute (-1)^h(n) for each n=0,1,2,...,2^k-1. I know of at least three ways to accomplish this in O(1) time per n (provided n is small enough to fit in a machine word) while consuming a number of words of memory O(1+k) or less...
And, by definition, for f(x) = 2^-x, S is the transcendental Prouhet-Thue-Morse constant: http://en.wikipedia.org/wiki/Prouhet%E2%80%93Thue%E2%80%93Morse_constant
Sent: Monday, July 07, 2014 at 12:29 AM From: "Warren D Smith" <warren.wds@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: [math-fun] Some Wilsonian sums
h(n) = (-1)^(parity of bit-sum of binary representation of n)
f(x) S=SUM[ f(n) * h(n), for n=0..2^k-1 with k large] ln(x+1) S=-log(2)/2 ln(x+2) S = -0.1379330125 ln(x+3) -0.07070756527 x^j 0 for any fixed integer j>=0 1/(x+1) 0.398761088108 1/(x+2) 0.1049709156499 sqrt(x) -0.63407426 1/sqrt(x+1) 0.1983140804979
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Adam P. Goucher -
Warren D Smith