Generating functions for sum of digits

franktaw at franktaw at
Fri Nov 4 04:40:02 CET 2005

 For A053735 Sum of digits of (n written in base 3), the given generating function,
(Sum_{k>=0} x^(3^k)/(1+x^(3^k)))/(1-x),
is wrong.  The correct generating function is
(Sum_{k>=0} (x^(3^k)+2*x^(2*3^k))/(1+x^(3^k)+x^(2*3^k)))/(1-x).
In general, the sum of digits of (n written in base b) has generating function
(Sum_{k>=0} (Sum_{0<=i<b} i*x^(i*b^k))/(Sum_{0<=i<b} x^(i*b^k)))/(1-x);
in particular, for b=4, A053737 the generating function is
(Sum_{k>=0} (x^(4^k)+2*x^(2*4^k)+3*x^(3*4^k))/(1+x^(4^k)+x^(2*4^k)+x^(3*4^k))/(1-x).
(There is a typo in the example line of this sequence: it should end with 4, not 3.)
Also, the generating function for the number of digits equal to d in the base b representation of n (0<d<b) is
(Sum_{k>=0}  x^(d*b^k)/(Sum_{0<=i<b} x^(i*b^k)))/(1-x);
in particular, for d=1, b=3, A062756 has generating function
(Sum_{k>=0} x^(3^k)/(1+x^(3^k)+x^(2*3^k)))/(1-x).
For d=0, use the above formula with d=b:
(Sum_{k>=0} x^(b^(k+1))/(Sum_{0<=i<b} x^(i*b^k)))/(1-x),
adding 1 if you consider the representation of 0 to have one zero digit.  Thus for A077267, the G.F. is
(Sum_{k>=0} x^(3^(k+1))/(1+x^(3^k)+x^(2*3^k)))/(1-x),
and for A081602 it is
1+(Sum_{k>=0} x^(3^(k+1))/(1+x^(3^k)+x^(2*3^k)))/(1-x).
(And these two sequences should have cross-references indicating that they are essentially the same.)
Finally, the sequence that got me into this: A033095 (total number of 1's in all bases) has G.F.
x+(Sum_{b>=2} (Sum_{k>=0} x^(b^k)/(Sum_{0<=i<b} x^(i*b^k)))/(1-x) - x).
If the initial term of A033095 was 0, the initial "x+" would not be needed.  This value is rather arbitrary; changing the "n+1" in the definition to "n" would make it 0.
Look What The New Can Do!
Now you can preview dozens of stories and have the ones you select delivered to you without ever leaving the Top Home Page. And the new Tool Box gives you one click access to local Movie times, Maps, White Pages and more.  See for yourself at
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the SeqFan mailing list