8
$\begingroup$

The binary weight of the non negative integer k is defined by 

w[k_] := Total[IntegerDigits[k, 2]]

The first values are (cf. http://oeis.org/ A000120) 

Table[w[k], {k, 0, 10}]

(*
  {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2}
*)

Now define formally the generating function

g[z_] = Sum[w[k] z^k, {k, 0, ∞}]

(*
  (2 - z)/(-1 + z)^2 
*)

Most surprisingly, Mathematica returns an explicit result.

But this can't be correct, as the expansions about z = 0 differ

Sum[w[k] z^k, {k, 0, 5}]

(*
  z + z^2 + 2 z^3 + z^4 + 2 z^5
*)

Series[(2 - z)/(-1 + z)^2, {z, 0, 5}] // Normal

(*
  2 + 3 z + 4 z^2 + 5 z^3 + 6 z^4 + 7 z^5
*)

It looks as if in the infinite sum the function w[k] is replaced by (k + 2).

Any explanation? Seems to be a bug.

EDIT #1

24.02.15 19:08

To avoid the head replacement effect pointed out by belisarius we can consider the function

w1[n_] := n - Sum[IntegerExponent[k, 2], {k, 1, n}]

which is identical to w[k] for any k.

Now the infinite sum 

g1[z_] = Sum[w1[n] z^n, {n, 0, \[Infinity]}]

is returned unevaluated, as it "should" (because it is too complicated)

$\sum _{n=0}^{\infty } z^n \left(n-\sum _{k=1}^n \text{IntegerExponent}[k,2]\right)$

So my discovery is not a bug, but I have learned the lesson that one should be very careful with infinite sums and their interpretation of the terms to be added.

Improve this question
$\endgroup$
  • 1
    $\begingroup$ Interestingly, Mathematica requires several seconds to compute Sum[w[k] .1^k, {k, 0, 999999}], returning 0.112122. But Sum[w[k] .1^k, {k, 0, 1000000}] returns almost instantly with 2.34568. Yes, I would say that this is a bug. $\endgroup$ – bbgodfrey Feb 24 '15 at 12:14
  • 1
    $\begingroup$ Finite sums are computed by addition up to 10^6-1 terms. Above that symbolic methods are used by default. Per @belisarius explanation of Total behavior, and the procedural summation cutoff of a million, no bug here. On a related note, I think some information about this may be found in the documentation. Also mentioned in a prior MSE post, though offhand I do not recall which one that was. $\endgroup$ – Daniel Lichtblau Feb 24 '15 at 16:28
  • $\begingroup$ @DanielLichtblau I only remember this one $\endgroup$ – Dr. belisarius Feb 24 '15 at 17:11
  • 1
    $\begingroup$ This, I believe $\endgroup$ – Daniel Lichtblau Feb 25 '15 at 0:59
  • $\begingroup$ @DanielLichtblau Thanks for the link. $\endgroup$ – Dr. Wolfgang Hintze Feb 25 '15 at 14:22
9
$\begingroup$

The problem is that Total[] works with any head. So:

Total[Derivative[1, 2, 1]]
(* 4 *)

Total[IntegerDigits[k, 2]]
(* 2 + k *)

And so you can expect

Sum[(2 + k) z^k, {k, 0, ∞}] == Sum[Total[IntegerDigits[k, 2]] z^k, {k, 0, ∞}]
Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.