13
$\begingroup$

Given two natural numbers $n\geq 1$ and $b\geq 2$, denote by $S_b(n)$ the sum of the digit of $n$ in its representation in base $b$. Clearly $S_b(n)$ varies from 1 (when $n$ is a power of $b$) to $(b-1)\lfloor\ln{n}/\ln{b}\rfloor$ (when $n=b^k-1$ for some integer $k$). However, for a fixed $n$, the value of $S_b(n)$ for a generic base $b$ should be of order $(b-1)/2\cdot\ln{n}/\ln{b}$.

This lead to consider the average of $S_b(n)$ for $b\leq n$

$$S(n):=\sum_{b\leq n}S_b(n)$$ or (maybe better) the wieghted average $$S_w(n):=\sum_{b\leq n}\frac{S_b(n)}{b}$$

There exists some asymptotics or non trivial bounds for $S(n)$ and $S_w(n)$?

$\endgroup$

3 Answers 3

14
$\begingroup$

Numerics suggest that $S(n) \sim Cn^2$ for some constant $C$ between $0.175$ and $0.18$.

Note that the bases $\frac n2<b\le n$ are easy to calculate: we get a sequence of two-digit numbers of the form $1x$, where $x$ runs from $\frac n2$ or so to $0$ (covering all integers in between). The sum of all these digits is asymptotic to $\frac12(\frac n2)^2$.

In the next range $\frac n3<b\le \frac n2$, we get a sequence of two-digit numbers of the form $2x$, where $x$ hits every other integer between about $\frac n3$ and $0$. The sum of all these digits is asymptotic to $\frac22(\frac n6)^2$.

Continuing to look at these ranges, we get a sequence of contributions of the form $\frac k2(\frac n{k(k+1)})^2$ from the bases $\frac n{k+1}<b\le\frac nk$ (at least until $k$ is about $\sqrt n$ or so). And one can calculate that $$ \sum_{k=1}^\infty \frac k2\bigg(\frac 1{k(k+1)}\bigg)^2 = 1-\frac{\pi^2}{12} = 0.17753... $$

So I'm guessing that one can prove in this way that $S(n) \sim (1-\frac{\pi^2}{12})n^2$.

(Numerically $S_w(n)$ seems to have size $n$, perhaps asymptotic to $Dn$ with some constant $D$ between $0.43$ and $0.44$. The similar heuristic doesn't give such a formula, however, because the large bases don't dominate the sum to the same extent as for $S(n)$.)

$\endgroup$
3
  • $\begingroup$ Thank you for your response. The asymptotic for $S(n)$ seems indeed true. Can we say something about the error term? Anyway the weighted version $S_w(n)$ looks more interesenting, because (as you pointed out) the major contribution is given only by small bases. Supposing $S_w(n)$ asymptotic to $Dn$, what can we say about the error term? $\endgroup$
    – Capublanca
    Oct 8, 2015 at 10:30
  • $\begingroup$ I wouldn't say that the major contribution is from the small bases - only that the large bases don't completely dominate. In a random heuristic, the contribution from the base $b$ is roughly $(\log n)/(2\log b)$; so there's not too much difference between the contributions of the small and large $b$, compared to the scale of the answer. Anyway, to answer your question: I doubt there's anything (outside generic guesses) one could say about the error term until one identifies the constnat $D$. $\endgroup$ Oct 8, 2015 at 17:35
  • $\begingroup$ The question if $S_w(n)$ actually admits an asymptotic of the form $Dn$ seems very interesting. Do you have some suggestion for such result to be true? $\endgroup$
    – Capublanca
    Oct 9, 2015 at 3:47
13
$\begingroup$

The observation by Greg Martin is indeed correct. I have worked with these expressions in my bachelor thesis, which can be accessed for free here:

Fissum, Robin. Digit sums and the number of prime factors of the factorial $n!=1\cdot 2\cdots n$, NTNU (2020).

Proposition 2.10, page 12 states that $$\sum_{2\leq b\leq n}S_b(n)\sim (1-\frac{\pi^2}{12})n^2$$ as $n \to \infty$.

Relationship between the two sums

We have
$$\sum_{2\leq b\leq n}\frac{S_b(n)}{b}=\frac{1}{n}\sum_{2\leq b\leq n}S_b(n)+\int_{1}^{n}\frac{\sum \limits_{2 \leq b \leq x}S_b(n)}{x^2}dx$$

Proof:

Set $n_0$ equal to a fixed positive integer, and consider the sum $\sum \limits_{2\leq b\leq n}\frac{S_b(n_0)}{b}$. If we let $(a_k)_{k=1,2,\ldots}$ be the sequence defined by $a_1=0$ and $a_t=S_t(n_0)$ for $t\geq 2$, and $\phi:t\mapsto\frac{1}{t}$. Then the sum becomes $\sum \limits_{k=1}^{n}a_k\phi(k)$, which by Abel's summation formula equals $$\phi(n)\sum_{k=1}^na_k -\int_{1}^{n}\phi'(x)\sum_{k\leq x}a_k \;\;dx$$ or equivalently $$\frac{1}{n}\sum_{2\leq b\leq n}S_b(n_0)+\int_{1}^{n}\frac{\sum \limits_{2 \leq b \leq x}S_b(n_0)}{x^2}dx$$ Setting $n_0$ equal to $n$ completes the proof.

Asymptotic formula for the second sum

Proposition 4.4, page 27 states that $$\int_{1}^{n}\frac{\sum \limits_{p \leq n}S_p(n)}{x^2}dx \sim (\frac{\pi^2}{12}-\gamma)\frac{n}{\log(n)},$$ as $n \to \infty$, where $\gamma$ is the Euler- Mascheroni constant. Here, the summation is taken over the primes $p$. If you modify the deduction of this formula, you could conclude that $$\int_{1}^{n}\frac{\sum \limits_{2 \leq b \leq x}S_b(n)}{x^2}dx \sim (\frac{\pi^2}{12}-\gamma)n$$ Using the relationship we obtained for the two summands, along with these two asymptotic formulae, we get: \begin{align} \sum_{2\leq b\leq n}\frac{S_b(n)}{b}\;=&\;\frac{1}{n}\sum_{2\leq b\leq n}S_b(n)+\int_{1}^{n}\frac{\sum \limits_{2 \leq b \leq x}S_b(n)}{x^2}dx \\ \sim \; &(1-\frac{\pi^2}{12})n+(\frac{\pi^2}{12}-\gamma)n \\[2mm] \sim \; &(1-\gamma)n & \\[2mm] =&\; n \cdot 0.42278433\ldots \end{align} Which perfectly matches the the numerical heuristics as pointed out by Greg Martin.

What if we sum over only primes p?

Proposition 2.12(p.14), Propostion 4.4(p.27) and the forumlae on page 25 show that

\begin{align}\sum_{p \leq n}S_p(n)\; =\; &(1-\frac{\pi^2}{12})\frac{n^2}{\log(n)}+C\frac{n^2}{\log^2(n)}+o(\frac{n^2}{\log^2(n)}) \\ \sum_{p\leq n}\frac{S_p(n)}{p}\sim& \;(1-\gamma)\frac{n}{\log(n)}, \end{align}

where $C=0.119\ldots$

$\endgroup$
2
  • $\begingroup$ Well done, very nice job! $\endgroup$
    – Capublanca
    Sep 27, 2020 at 14:16
  • $\begingroup$ Happy to be of help : ) $\endgroup$
    – AfterMath
    Sep 27, 2020 at 15:14
4
$\begingroup$

Check out the closely related article by L. E. Bush from the 1940 American Math Monthly. Bush shows that for $r$ fixed, and $n < N,$ the average value of digit sums is asymptotic to: $$ \frac{(r-1) \log N}{2 \log r}. $$

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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