% Created April 16, 2009, for submission to JIS
% This is the version submitted to JIS, June 19, 2009

\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

% \usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Example}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\def\I#1{{[\![#1]\!]}}                % Iversonian
\def\G#1{{G(\langle #1 ,1 \rangle)}}  % G( < ... , 1 > )
% new commands

\newcommand{\coord}[3]{{\left(#1,#2\right)}^{#3}}
\newcommand{\subone}[1]{#1^\prime}
\newcommand{\A}[1]{\left<#1\right>}
% \newcommand{\G}[1]{G \left(#1\right)}
\newcommand{\GA}[1]{\G{\A{#1}}}
\newcommand{\p}[1]{(#1)}

\newcommand{\T}[3]{{\mathcal{T}}_{#1,#2}({#3})} % \newcommand{\T}[3]{{\mathcal{T}}_{#1}^{#2}({#3})}
\newcommand{\Aofn}[3]{a_{#1,#2}({#3})}  % \newcommand{\aofn}[3]{a_{#1}^{#2}({#3})}
\newcommand{\aofn}[3]{a({#3})}  % \newcommand{\aofn}[3]{a_{#1}^{#2}({#3})}
\newcommand{\an}[1]{a({#1})}
\newcommand{\dofn}[3]{d_{#1,#2}({#3})} % \newcommand{\dofn}[3]{d_{#1}^{#2}({#3})}
\newcommand{\dn}[1]{d({#1})}
\newcommand{\pofn}[3]{p_{#1,#2}({#3})} % \newcommand{\pofn}[3]{p_{#1}^{#2}({#3})}
\newcommand{\pn}[1]{p({#1})}
\newcommand{\kh}[2]{\mathbf{[}{#2}\mathbf{]}} % \newcommand{\kh}[2]{[{#2}]_{#1}}

\begin{document}
% \maketitle

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf
Generating Functions for the Digital Sum \\
\vskip .1in
and Other Digit Counting Sequences
}
\vskip 1cm
\large
Franklin T. Adams-Watters \\
% Affiliation? \\
\href{mailto:FrankTAW@Netscape.net}{\tt FrankTAW@Netscape.net}\\
\ \\
Frank Ruskey \\
University of Victoria \\
Victoria, BC V8W 3P6 \\
CANADA \\
\href{mailto:ruskey@cs.uvic.ca}{\tt ruskey@cs.uvic.ca}\\
\end{center}

\vskip .2in

\begin{abstract}
A numeration system associates a unique string, $\Xi(n)$, with each
positive integer $n$, where each string is over the same finite
alphabet.  Various digit counting statistics of $\Xi(n)$ are of
interest with respect to a numeration system.  An example is the
digital sum, which is the sum of the digits in the number.  We present
a unifying framework for deriving identities for the generating
functions of such statistics in many of the more popular numeration
systems.  
\end{abstract}

\section{Introduction}

Numeration systems provide a rich source of integer sequences.
There are many interesting digit counting statistics that arise from the
  various numeration systems.
A typical example, the digital sum, is explained below.

Given a number $n$ represented in binary, $n = (b_d b_{d-1} \cdots b_1 b_0)_2$, the
  (binary) \emph{digital sum} of $n$, denoted $s_2(n)$ is $b_0+b_1+\cdots+b_{d}$.
The digital sum goes under several other names including sideways sum, sideways
  addition, population count, and Hamming weight.
It is denoted $\nu n$ in Knuth \cite{KnuthFasc1}, but we use the notation 
used by
  Allouche and Shallit \cite{AlloucheShallit} (but due to earlier researchers; e.g.,
  B\'esineau \cite{Besineau} and Coquet and Toffin \cite{CoquetToffin}).
There are two natural ways in which we might extend the idea to $k$-ary numbers,
  either by summing digits, or by counting non-zeros.
We use the notation $s_k(n)$ (again following \cite{AlloucheShallit}) for the
  sum-of-digits function and $c_k(n)$ for the counting non-zeros function.

According to OEIS \seqnum{A053735},
  the ordinary generating function of $s_k(n)$ has the beautiful expression given
  in Theorem \ref{thm:intro} below.
For $k = 2$ this generating function may be found in Knuth \cite{KnuthFasc1};
  see exercise 7.1.3.41.
The purpose of this short paper is to provide a proof of this and some other
  related generating functions that are in the OEIS --- as part of a more
  generalized setting.
Table \ref{table:OEIS} contains some of the sequences to which our results apply.

\begin{theorem}
For all $k \ge 2$,
\begin{eqnarray*}
\sum_{n \ge 0} s_k(n) z^n
& = &
\frac{1}{1-z} \sum_{m \ge 0} \frac{ z^{k^m} + 2z^{2k^m} + \cdots + (k-1)z^{(k-1)k^m}}{1+z^{k^m}+z^{2k^m}+
  \cdots + z^{(k-1)k^m}} \\
& = &
\frac{1}{1-z} \sum_{m \ge 0} \frac{
z^{k^m} - kz^{k^{m+1}} + (k-1)z^{(k+1)k^m}}{(1 - z^{k^m}) (1 - z^{k^{m+1}})}.
\end{eqnarray*}
\label{thm:intro}
\end{theorem}

\section{Numeration as a sequence of columns}

Imagine a table comprised of infinite columns of numbers, $C_0, C_1, C_2, \ldots$.
The numbers in each column are indexed starting at 0 and the numbers found in all
  of the columns all come from the same finite set.
In a numeration system each row of the table is distinct.
For example, in the binary number system, $C_j$ consists of the
  periodic repetition of $2^j$ 0s followed by $2^j$ 1s.

What is the generating function function for the row sums of those columns?
Suppose that the generating function for the $m$-th column is $C_m(z)$.
Then
\begin{equation}
A(z) = \sum_{m \ge 0} C_m(z)
\label{eq:general}
\end{equation}
is the generating function for the row sums.
That is, $\langle z^n \rangle A(z)$ is the sum of the numbers in
  the $n$-th row, where $\langle z^n \rangle$ means
  ``coefficient of $z^n$".
The generating function (\ref{eq:general}) will exist so long as there
  are constants $c_n$ such that $\langle z^n \rangle C_m(z) = 0$
  for all $m \ge c_n$.
In many numeration systems the $m$-th column can be described as a
  infinite string of the form $\mathbf{s}_m \mathbf{t}_m^\infty$,
  where $\mathbf{s}_m$ and $\mathbf{t}_m$ are strings with
  $\mathbf{t}_m \neq \varepsilon$ and $\mathbf{t}_m^\infty$ denotes
  the infinite string $\mathbf{t}_m^\infty = \mathbf{t}_m \mathbf{t}_m \mathbf{t}_m \cdots$.
Let $|\mathbf{s}|$ be the length of the string $\mathbf{s}$.
If $S_m(z)$ and $T_m(z)$ are the generating functions (which are actually
  polynomials) of $\mathbf{s}$ and $\mathbf{t}$, respectively.
Then
\begin{equation}
C_m(z) = S_m(z) + \frac{z^{|\mathbf{s}_m|} T_m(z)}{1-z^{|\mathbf{t}_m|} }
\label{eq:infstring}
\end{equation}
Often $\mathbf{s}_m$ and $\mathbf{t}_m$ will have a special form that
  allows for further simplification of $C_m(z)$

In this paper the most general from that we use is shown below.
Here the $m$-th column depends on integers $b_m$, $a_m$ and $u_m$,
  and the sequence of numbers $\alpha_0, \alpha_1, \alpha_2, \ldots$.
The following string is called the \emph{column pattern}:
\begin{equation}
\mathbf{s}_m \mathbf{t}_m^\infty = 0^{b_m}(\alpha_0^{a_m} \alpha_1^{a_m} \cdots \alpha_{(u_m-1)}^{a_m})^\infty
\label{eq:regexpr}
\end{equation}

For example, the column pattern for the binary digital sum
  is $(0^{2^m} 1^{2^m})^\infty$; here $b_m = 0$, $a_m = 2^m$, $\alpha_0 = 1$, $\alpha_1 = 1$,
  and $u_m = 2$.
The generating function of $\alpha_0^{a_m} \alpha_1^{a_m} \cdots \alpha_{(u_m-1)}^{a_m}$ is
\[
A_m(z) = (\alpha_0 + \alpha_1 z^{a_m} + \alpha_1 z^{2a_m} + \cdots + \alpha_{u_m-1} z^{(u_m-1) a_m})
   \frac{1-z^{a_m}}{1-z}
\]
Thus, by (\ref{eq:infstring}), the generating function for (\ref{eq:regexpr}) is
\[
\frac{z^{b_m} A_m(z)}{1-z^{u_m a_m}} =
\frac{z^{b_m}}{1-z} \cdot \frac{
\alpha_0 + \alpha_1 z^{a_m} + \alpha_2 z^{2a_m} + \cdots + \alpha_{u_m-1} z^{(u_m-1) a_m}
}{
1+z^{a_m} + z^{2a_m} + \cdots + z^{(u_m-1) a_m}
}.
\]
Summing over $m \ge 0$ we obtain
\begin{eqnarray}
A(z) & = &
\frac{1}{1-z} \sum_{m \ge 0} \frac{z^{b_m}(1-z^{a_m})}{1-z^{u_m a_m}}
(\alpha_0 + \alpha_1 z^{a_m} + \alpha_2 z^{2a_m} + \cdots + \alpha_{u_m-1} z^{(u_m-1) a_m})
 \label{eq:patterngf2} \\
 & = &
 \frac{1}{1-z} \sum_{m \ge 0} z^{b_m}
\frac{
\alpha_0 + \alpha_1 z^{a_m} + \alpha_2 z^{2a_m} + \cdots + \alpha_{u_m-1} z^{(u_m-1) a_m}
}{
1+z^{a_m} + z^{2a_m} + \cdots + z^{(u_m-1) a_m}
}.
\label{eq:patterngf}
\end{eqnarray}
In the sections to follow we apply this generating function to various numeration systems,
  starting with a new addition to the OEIS.

\section{The Balanced Ternary System}

In the \emph{balanced ternary system} each natural number $n$ is expressed as a
  sum of distinct signed powers of 3.
For example $5 = 9 - 3 - 1 = 3^3 - 3^1 - 3^0$.
The digital sum is OEIS A065363.
Following Knuth \cite{KnuthII} we use $\bar{1}$ to denote $-1$.
It is outside the scope of this paper, but it is not difficult to show
  that the pattern of the $m$-th column is
\[
0^{3^m - 3^{m-1} - \cdots - 3^0} (1^{3^m} \bar{1}^{3^m} 0^{3^m})^\infty.
\]
Since $3^m - 3^{m-1} - \cdots - 3^0 = (3^m+1)/2$, the generating function
  for the sum of the digits of the balanced ternary representation of $n$ is
\[
A(z) = \frac{1}{1-z} \sum_{m \ge 0} z^{(3^m+1)/2}
\frac{1- z^{3^m}}
{1+z^{3^m} + z^{2 \cdot 3^m}}
=
\frac{1}{1-z} \sum_{m \ge 0} z^{(3^m+1)/2}
\frac{(1- z^{3^m})^2}
{1-z^{3^{m+1}}}.
\]

\section{The $k$-ary Numeration System and Morphisms}

The column pattern for $k$-ary numbers is
\begin{equation}
(\alpha_0^{k^m} \alpha_1^{k^m} \ldots \alpha_{k-1}^{k^m})^\infty.
\label{eq:kary}
\end{equation}
Here the row sum of the $n$-th row, where
\[
n = \sum_{k \ge 0} b_k k^m,
\ \ \text{ is } \ \
\sum_{k \ge 0} \alpha_{b_k} k^m.
\]
That is, each digit $b$ is ``weighted" by $\alpha_b$.
For the digital sum, $\alpha_b = b$.

The special form of (\ref{eq:kary}) implies that
  there is a ``morphism" that underlies the construction; for the
  digital sum it is $j \rightarrow j,j+1,j+2,\ldots,j+k-1$.
For example, when $k = 3$ we get the sequence $s_3(0),s_3(1),s_3(2),\ldots$ as the
  limit (i.e., fixed-point) of a morphism noted by Robert G. Wilson in \seqnum{A053735},
  which gives us successively
\[
0 \rightarrow 012 \rightarrow 012\ 123\ 234 \rightarrow
012123234\ 123234345\ 234345456 \rightarrow \cdots
\]
This limit will exist for any morphism of the form
\begin{equation}
j \rightarrow j+\alpha_0, j+\alpha_1, \ldots, j+\alpha_{k-1},
\label{eq:morphism}
\end{equation}
so long as $\alpha_0 = 0$.

\begin{theorem}
The row sums of the column pattern (\ref{eq:kary}) are generated
  by the morphism (\ref{eq:morphism}) so long as $\alpha_0 = 0$.
\end{theorem}
\begin{proof}
The column pattern (\ref{eq:kary}) is invariant under the
  following two-step operation:
(a) Take column $m$ and replace each entry in the column by
  $k$ identical entries, calling the new column $C'_{m+1}$.
(b) Form a new column $C'_0$ with the pattern $(01 \cdots (k-1))^\infty$.
The invariance is that $C'_m = C_m$ for $m = 0,1,2,\ldots$.

A row sum $j$ under operations (a) and (b) becomes the $k$ row sums
  $j+\alpha_0, j+\alpha_1, \ldots, j+\alpha_{k-1}$.
This is the morphism (\ref{eq:morphism}).
\end{proof}

With the pattern (\ref{eq:kary}) equation (\ref{eq:patterngf}) gives us the theorem below.
\begin{theorem}
If $k$ is an integer with $k \ge 2$ and $\alpha_0 = 0$, then the generating function of the limit of the
   morphism (\ref{eq:morphism}) is
\begin{equation}
A(z) \  = \
\frac{1}{1-z} \sum_{m \ge 0} \frac{ \alpha_1 z^{k^m} + \alpha_2 z^{2k^m} + \cdots + \alpha_{k-1} z^{(k-1)z^m}}{1+z^{k^m}+z^{2k^m}+ \cdots + z^{(k-1)k^m}}.
\label{eq:Az}
\end{equation}
\label{thm:gf}
\end{theorem}

Note that Theorem \ref{thm:intro} is the special case where $\alpha_i = i$ for $i = 0,1,\ldots,k-1$.
The second equality in Theorem \ref{thm:intro} follows from the fact that
  $z+2z+\cdots+(k-1)z^{k-1} = (z - kz^k + (k-1)z^{k+1}) / (1 - z)^2$.
We now return to the non-zero count function, $c_k(n)$, which can be expressed without the inner sums
  used in (\ref{eq:Az}).

\begin{corollary}
The generating function of $c_k(n)$ is
\begin{equation}
C_k(z) = \frac{1}{1-z} \sum_{m \ge 1}
  \frac{ z^{k^{m-1}} - z^{k^{m}}}{1-z^{k^{m}}}.
\label{eq:Ck}
\end{equation}
\end{corollary}
\begin{proof}
Here the morphism is $j \rightarrow j,j+1,\ldots,j+1$ and so Theorem
  \ref{thm:gf} gives us the first equality below.
\begin{eqnarray}
C_k(z) & = &
\frac{1}{1-z} \sum_{m \ge 0} \frac{ z^{k^m} + z^{2k^m} + \cdots + z^{(k-1)k^m}}{1+z^{k^m}+z^{2k^m}+ \cdots + z^{(k-1)k^m}}
\label{eq:CkzX} \\
& = &
\frac{1}{1-z} \sum_{m \ge 0} \frac{ (1-z^{k^{m+1}})/(1-z^{k^m})-(1-z^{k^{m}})/(1-z^{k^m}) }{ (1-z^{k^{m+1}})/(1-z^{k^m}) }
  \nonumber
\end{eqnarray}
Cancelling common denominators and simplifying gives (\ref{eq:Ck}).
\end{proof}

Other morphisms would give counts of the number of times individual digits occur in the obvious way.
For example, $j \rightarrow j,j,j+1,j$ is the morphism for the number of 2's that occur in the 4-ary expansion of $n$
  (here the pattern is $(0^{4^m}0^{4^m}1^{4^m}0^{4^m})^\infty$).

\begin{theorem}
Let $d$ be an integer with $0 < d < k$.
The generating function for the number of digits equal to $d$ in the $k$-ary expansion of $n$ is
\begin{equation}
\frac{1}{1-z} \sum_{m \ge 0} \frac{  z^{dk^m} }{1+z^{k^m}+z^{2k^m}+ \cdots + z^{(k-1)k^m}} =
\frac{1}{1-z} \sum_{m \ge 0} \frac{  z^{dk^m}(1-z^{k^m}) }{1-z^{k^{m+1}}}.
\label{eq:digits}
\end{equation}
The generating function for the number of $0$ digits in the $k$-ary expansion of $n$ is
\begin{equation}
\frac{1}{1-z} \sum_{m \ge 0} \frac{ z^{k^{m+1}} }{1+z^{k^m}+z^{2k^m}+ \cdots + z^{(k-1)k^m}} =
\frac{1}{1-z} \sum_{m \ge 0} \frac{  z^{k^{m+1}}(1-z^{k^m}) }{1-z^{k^{m+1}}}.
\label{eq:zero}
\end{equation}
\end{theorem}
\begin{proof}
Equation (\ref{eq:digits}) follows from Theorem \ref{thm:gf} with the morphism
  $j \rightarrow j,\ldots,j,j+1,j,\ldots,j$ where the $j+1$ occurs in position $d$, counting
  from $0$.
To prove (\ref{eq:zero}) we use the generating function
\[
T(z) \ = \ \frac{1}{1-z} \sum_{m \ge 0} z^{k^m}
\]
for $1 + \lfloor \log_k n \rfloor$, which is the number of $k$-ary digits in $n$.
Adding (\ref{eq:CkzX}) and (\ref{eq:zero}) we clearly obtain $T(z)$.

A second way of finishing the proof is to note that the column pattern
\[
0^{k^m} ( 1^{k^m} 2^{k^m} \cdots (k-1)^{k^m} 0^{k^m})^\infty
\]
also describes the $k$-ary listing of numbers.
The useful aspect of expressing it this way is that the leading 0s are
  correspond to the initial $0^{k^m}$ above.
Thus the pattern for counting (non-leading) 0s is
\[
0^{k^m} ( 0^{k^m} 0^{k^m} \cdots 0^{k^m} 1^{k^m})^\infty.
\]
According to (\ref{eq:patterngf}) the numerator inside the sum
  of the generating function is $z^{b_m} z^{(u_m-1)a_m} = z^{k^m} z^{(k-1)k^m} = z^{k^{m+1}}$,
  as desired.
\end{proof}


\begin{table}
\begin{center}
\begin{tabular}{c|c|c|c}
\textbf{OEIS} & \textbf{description} & \textbf{comment} & \textbf{pattern} \\ \hline
\seqnum{A023416} & 0s in binary & same as \seqnum{A080791} & $0^{2^m}(0^{2^m}1^{2^m})^\infty$ \\
\seqnum{A000120} & 1s in binary & digital sum, base 2 & $(0^{2^m}1^{2^m})^\infty$ \\
\seqnum{A077267} & 0s in base 3 & same as \seqnum{A081602} & $0^{3^m}(0^{3^m}0^{3^m}1^{3^m})^\infty$ \\
\seqnum{A062756} & 1s in base 3 & & $(0^{3^m}1^{3^m}0^{3^m})^\infty$ \\
\seqnum{A081603} & 2s in base 3 & & $(0^{3^m}0^{3^m}1^{3^m})^\infty$ \\
\seqnum{A160380} & 0s in base 4 & & $0^{4^m}(0^{4^m}0^{4^m}0^{4^m}1^{4^m})^\infty$\\
\seqnum{A160381} & 1s in base 4 & & $(0^{4^m}1^{4^m}0^{4^m}0^{4^m})^\infty$ \\
\seqnum{A160382} & 2s in base 4 & & $(0^{4^m}0^{4^m}1^{4^m}0^{4^m})^\infty$ \\
\seqnum{A160383} & 3s in base 4 & & $(0^{4^m}0^{4^m}0^{4^m}1^{4^m})^\infty$ \\
\seqnum{A160384} & non-0 base 3 & & $(0^{3^m}1^{3^m}1^{3^m})^\infty$ \\
\seqnum{A160385} & non-0 base 4 & & $(0^{4^m}1^{4^m}1^{4^m}1^{4^m})^\infty$ \\
\seqnum{A053735} & digital, base 3 & & $(0^{3^m}1^{3^m}2^{3^m})^\infty$ \\
\seqnum{A053737} & digital, base 4 & & $(0^{4^m}1^{4^m}2^{4^m}3^{4^m})^\infty$ \\
\seqnum{A034968} & digital, factorial base  & see also \seqnum{A139365} \\
\seqnum{A065363} & digital, balanced base 3 & & $0^{(3^m+1)/2} (1^{3^m} \bar{1}^{3^m} 0^{3^m})^\infty$ \\
\seqnum{A139351} & 1s or 3s in base 4 & 1s in even positions in binary & $(0^{4^m}1^{4^m}0^{4^m}1^{4^m})^\infty$ \\
\seqnum{A139352} & 2s or 3s in base 4 & 1s in odd positions in binary  & $(0^{4^m}0^{4^m}1^{4^m}1^{4^m})^\infty$ \\
\end{tabular}
\end{center}
\caption{Relevant sequences in OEIS.}
\label{table:OEIS}
\end{table}

\subsection{Digit counts in specific positions}

Let $C(n,r,d)$ be the number of 1 bits in the binary representation of $n$ that are
  in positions that are congruent to $r$ mod $d$.
As usual, the ``positions" are indexed starting at 0 on the right.
For example, $888 = (1101111000)_2$, so $C(888,0,3) = 3$, $C(888,1,3) = 1$ and $C(888,2,3) = 2$.

\begin{theorem}
For all integers $d \ge 0$ and integers $r$ with $0 \le r < d$,
\begin{equation}
\sum_{n \ge 0} C(n,r,d) z^n \ = \
\sum_{m \ge 0} \frac{ z^{2^{r+dm}} }{ 1 + z^{2^{r+dm}} }.
\label{eq:mod}
\end{equation}
\end{theorem}
\begin{proof}
Let $B(r,d) = \{ s \in \mathbb{Z} \! :\! 1 \le s < 2^d  \text{ and } \lfloor s/2^r \rfloor \text{ is odd} \}$;
  in other words, the $d$ bit binary numbers with the $r$-th bit equal to 1.
Let $\bar{B}(r,d) = \{0,1,\ldots,2^d-1\} \setminus B(r,d)$.
For example, $B(1,3) = \{2,3,6,7\}$ and $B(1,3) = \{0,1,4,5\}$.

Now consider the number $n$ written both in binary and in base $2^d$.
Note that, in the binary representation of $n$, the number of 1 bits in positions that are
  congruent to $r$ mod $d$ is the same as the number of digits from the
  set $B(r,d)$ in the $2^d$-ary representation of $n$.
Thus we may apply Theorem \ref{thm:gf} to get the generating function
\[
\sum_{n \ge 0} C(n,r,d) z^n \ = \
\sum_{m \ge 0} \frac{
\sum_{s \in B(r,d)} z^{s 2^{dm}}
}{
\sum_{0 \le s < 2^d} z^{s 2^{dm}}
}
\]
Note that the numerator above can be written
\[
\sum_{s \in B(r,d)} z^{s 2^{dm}} \ = \ z^{2^r 2^{dm}} \sum_{s \in \bar{B}(r,d)} z^{s 2^{dm}}
\]
and the denominator as
\[
\sum_{0 \le s < d} z^{s 2^{dm}} = \sum_{s \in B(r,d)} z^{s 2^{dm}} + \sum_{s \in \bar{B}(r,d)} z^{s 2^{dm}}
= (1+z^{2^r 2^{dm}}) \sum_{s \in \bar{B}(r,d)} z^{s 2^{dm}}.
\]
Canceling the common sum gives the right hand side of (\ref{eq:mod}).
\end{proof}

The following corollary allows us to give a generating function for A139351
  and A139352.

\begin{corollary}
The generating function for the number of $1$'s in even positions in the
  binary expansion of $n$,
and the corresponding generating function for the number of $1$'s in odd positions,
  are given below.
\[
\frac{1}{1-z} \sum_{m \ge 0} \frac{  z^{4^m} }{1+z^{4^m}}, \ \ \ \ \ \ \ \
\frac{1}{1-z} \sum_{m \ge 0} \frac{  z^{2 \cdot 4^m} }{1+z^{2 \cdot 4^m}}.
\]
\end{corollary}

\section{Multi-Radix Numeration Systems}

In this section we consider numbers written in the multi-radix base
  $k_0 \times k_1 \times k_2 \times \cdots$.
If each $k_i = k$ then we get the $k$-ary numeration system considered
  in the previous section.
It will prove useful to adopt the following notation:
  (a) $k'_j = k_j-1$,
  (b) $\bar{k}_j = k_0 k_1 \cdots k_{j-1}$,
  with the usual convention for the empty product, $\bar{k}_0 = 1$.
Then the column pattern is
\[
(\alpha_0^{\bar{k}_m} \alpha_1^{\bar{k}_m} \cdots \alpha_{k'_m}^{\bar{k}_m} )^\infty.
\]

\begin{theorem}
The generating function for the digital sum of the number $n$ written in
  the multi-radix base $k_0 \times k_1 \times k_2 \times \cdots $ is
\[
\frac{1}{1-z} \sum_{m \ge 0} \frac{
z^{\bar{k}_m}+2z^{2\bar{k}_m}+\cdots+k'_m z^{k'_m \cdot \bar{k}_m} }{
1 + z^{\bar{k}_m}+z^{2\bar{k}_m}+\cdots+z^{k'_m \cdot \bar{k}_m} }.
\]
\end{theorem}
\begin{proof}
The generating function is (\ref{eq:patterngf}) with
  $b_m = 0$, $\alpha_i = i$, $u_m = k'_m$, and $a_m = \bar{k}_m$.
\end{proof}

In the factorial base, $k_j = j+1$, so that $\bar{k}_j = j!$.
For example, $99 = 3 \cdot 4! + 0 \cdot 3! + 2 \cdot 2! + 1 \cdot 1!$.
We now obtain a generating function for \seqnum{A034968} in the following
  corollary.

\begin{corollary}
The generating function for the digital sum of the number $n$ written in
  the factorial base is
\[
\frac{1}{1-z} \sum_{m \ge 1} \frac{
z^{m!}+2z^{2m!}+\cdots+mz^{m \cdot m!} }{
1 + z^{m!}+z^{2m!}+\cdots+z^{m \cdot m!} }.
\]
\end{corollary}
\begin{proof}
This follows directly from the previous theorem.
Note that the numerator is zero when $m = 0$, so that the summation
  starts at 1.
\end{proof}

\section{Final Remarks}

It is also possible to approach the derivation of the generating functions
  used here using ``divide-and-conquer" recurrence relations.
See Stephan \cite{Stephan} for examples of this approach in the $k=2$ case.
For example the recurrence relation corresponding to the morphism
  (\ref{eq:morphism}) is $a(0) = 0$ and $a(km+i) = \alpha_i + a(m)$
  for integer indices $i$ with $0 \le i < k$.
These recurrence relations are very useful for actually computing the
  sequences.

As we have shown here, finding a generating function for the sum of the
  digits is straightforward when dealing with a simple radix, or a mixed
  radix system where each positional multiplier is a multiple of the
  previous one.
When this does not hold, the problem is much more difficult.

The simplest example of such a system is the Zeckendorf \cite{Zeckendorf}
  or ``base Fibonacci" representation (\seqnum{A014417}, digital sum in \seqnum{A007895}).
Attempting the same sort of one digit at a time approach, the low order
  digit is the infinite Fibonacci word, \seqnum{A003849}.
Since this sequence includes arbitrarily long repeated segments,
  but is not periodic, it does not have a rational
  generating function.

\nocite{*}
\bibliographystyle{abbrvnat}
\begin{thebibliography}{99}

\bibitem{AlloucheShallit}
  J.-P. Allouche and J. O. Shallit,
  \emph{Automatic Sequences},  Cambridge University Press, 2003.

% \bibitem{ABS} J.-P. Allouche, J. Betrema, and J. O. Shallit,
%   \emph{Sur des points fixes de morphismes d'un mono\"ide libre},
%   Informatique th\'eorique et Applications, \textbf{23} (1989) 235--249.

\bibitem{Besineau}
  J. B\'esineau, Ind\'ependance statistique d'ensembles li\'es \`a la
  fonctions ``somme des chiffres'', \emph{Acta Arith.} \textbf{20} (1972), 401--416.

\bibitem{CoquetToffin}
  J. Coquet and P. Toffin, Repr\'esentations des entiers naturels
  et ind\'ependance statistique, \emph{Bull. Sci. Math.}, \textbf{105} (1981), 289--298.

\bibitem{KnuthII}
  D. E. Knuth, \emph{The Art of Computer Programming, Volume 2,
  Seminumerical Algorithms}, 3rd edition, Addison-Wesley, 1998.

\bibitem{KnuthFasc1}
  D. E. Knuth, \emph{The Art of Computer Programming, Volume 4,
  Fascicle 1: Bitwise Tricks \& Techniques and Binary Decision
  Diagrams}, Addison-Wesley, 2009.

\bibitem{GKP}
  R. L. Graham, D. E. Knuth, and O. Patashnik,
  \emph{Concrete Mathematics},
  Addison-Wesley, second edition, 1994.

\bibitem{OEIS} N. J. A. Sloane,
  \emph{The On-Line Encyclopedia of Integer Sequences},
  \url{www.research.att.com/~njas/sequences/}, accessed April 2009.

\bibitem{Stephan} R. Stephan,
  {Divide-and-conquer generating functions, part I:
 elementary sequences}, \href{http://arxiv.org/abs/math/0307027}{\tt http://arxiv.org/abs/math/0307027}, 2003.

\bibitem{Zeckendorf}
  E. Zeckendorf,
  {Repr\'{e}sentation des nombres naturels par une somme de nombres
  de Fibonacci ou de nombres de Lucas}, \emph{Bull. Soc. Roy. Sci. Li\`{e}ge}, \textbf{41} (1972), 179--182.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A15; Secondary 05A10.

\noindent \emph{Keywords:}  Generating function, numeration system, digital sum, sideways addition,
  digit counting, morphism, factorial base, balanced ternary numbers.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000120},
\seqnum{A003849},
\seqnum{A007895},
\seqnum{A014417},
\seqnum{A023416},
\seqnum{A034968},
\seqnum{A053735},
\seqnum{A053737},
\seqnum{A062756},
\seqnum{A065363},
\seqnum{A077267},
\seqnum{A080791},
\seqnum{A081602},
\seqnum{A081603},
\seqnum{A139351},
\seqnum{A139352},
\seqnum{A139365},
\seqnum{A160380},
\seqnum{A160381},
\seqnum{A160382},
\seqnum{A160383},
\seqnum{A160384}, and
\seqnum{A160385}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received June 19 2009;
revised version received July 11 2009.
Published in {\it Journal of Integer Sequences}, July 12 2009.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}