6
$\begingroup$

Let $b \geq 2$ be an integer and let $s_b(n)$ be the sum of the digits of the base-$b$ representation of the nonnegative integer $n$ (e.g., $s_{10}(726)=7+2+6$). From the weak law of large numbers, it follows that $$s_b(n) > \left(\tfrac{0+1+\cdots + (b-1)}{b}-\varepsilon\right) \log_b n$$ for almost all the positive integers $n \leq x$, with at most $o(x)$ exceptions, as $x \to +\infty$. Therefore, if $\{a_k\}_{k=1}^\infty$ is a "generic" monotone increasing sequence of positive integer, it is quite reasonable to expect that $s_b(a_k) > C \log(a_k)$ for almost all $k$, i.e., with the exception of a set of asymptotic density 0, where $C$ is a positive constant (depending on the sequence $\{a_k\}_{k=1}^\infty$). By "generic" I means, informally speaking, that $\{a_k\}_{k=1}^\infty$ has not some trivial properties that makes the statement false (e.g., $a_k := b^k$). So for example, we can conjecture that $$s_b(n!) > C_1 n \log n$$ $$s_b(a^n) > C_2 n$$ $$s_b(F_n) > C_3 n$$ for almost all $n$, where $a$ is a positive integer coprime to $b$ and $F_n$ is the $n$-th Fibonacci number. In [1] and [3] they have been shown the weaker lower bounds $s_b(n!) > C_1 \log n \log \log \log n$ (see also [2]) and $s_b(F_n) > C_2 \log n / \log \log n$, for all integers $n$, respectively. Moreover, in [4] the bound $s_b(a_n) > C \log n$ for almost all $n$, has been proved for any sequence of integers $$a_n = e^{f(n)} (1 + O(n^{-\alpha}))$$ where $\alpha > 0$ and $f(x)$ is a two times differentiable function satisfying $f(x) \asymp 1/x$ for large x.

My question is: Are there some non(too)trivial example of $\{a_k\}_{k=1}^\infty$ such that the optimal lower bound $s_b(a_k) > C \log(a_k)$, for almost all $k$, has been proved?

Thank you very much for any suggestion/reference.

[1] C. Sanna, On the sum of digits of the factorial, J. Number Theory 147, 2015, 836--841.

[2] F. Luca, The number of nonzero digits of n!, Canad. Math. Bull., 45, 2002, 115--11.

[3] F. Luca, Distinct digits in base b expansions of linear recurrence sequences, Quaest. Math., 23, 2000, 389--404.

[4] J. Cilleruelo, F. Luca, J. Rué and A. Zumalacárregui, On the sums of digits of the some sequences of integers, Cent. Eur. J. Math., 11, 2013, 188--195.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ You write $s_b(n) > (1+2+\cdots+(b-1)) \log_b n$, but I think you need to divide the right-hand side by $b$ just to get the mean of the distribution, and to make it a little smaller still to have the inequality hold for almost all $n$. $\endgroup$
    – Greg Martin
    Commented Aug 31, 2014 at 17:25
  • $\begingroup$ @Greg Martin Right, I edited, thanks. $\endgroup$
    – user40023
    Commented Aug 31, 2014 at 17:36
  • 1
    $\begingroup$ $n!$ is sure to end with a certain number of zeros (roughly $\frac{n}{b-1}$ in case $b$ is prime) That would have some effect. $\endgroup$
    – Aaron Meyerowitz
    Commented Aug 31, 2014 at 22:44
  • $\begingroup$ In your three examples, you should certainly expect to have $s_b(n!) \asymp n \log{n}$ and $s_b(a^n) \asymp s_b(F_n) \asymp n$ for most $n$ (i.e., of full density in the positive integers). Why would you expect this to hold for all $n$ without exception? Also, is $a_k = k$ "generic"? How about $k^2+1$? For either of them the expected sum of digits is true for most $k$, but there are exceptions. What about $a_k = k^3+2$? $\endgroup$
    – Vesselin Dimitrov
    Commented Sep 1, 2014 at 14:13
  • $\begingroup$ I do not think you may draw such a strong conclusion just by the law of large numbers heuristic. An analogy: the primes have density zero in the positive integers (just like your exceptional values of $n$ in the law of large numbers), and yet, unless there is an obvious divisibility obstruction, many typical functions (such as $k^2+1$, $k!+1$...) are definitely expected to take infinitely many prime number values. $\endgroup$
    – Vesselin Dimitrov
    Commented Sep 1, 2014 at 14:19

1 Answer 1

Reset to default
2
$\begingroup$

The first paper you reference concerns simply the number of non-zero digits of $n!$ and not their sum. Of course that just changes the constant in front. That paper does note that the bound is quite weak compared to what one might expect. For example in the case $b=2$ his bound assures us that $n!$ has at least $7$ non-zero digits provided that $n$ is at least $767$ (by which point $n!$ has many thousand binary digits.) That is enough to allow one to establish that $n=9$ is actually the last case with as few as $6$ bits equal to $1.$ Then $9!=1011000100110000000_2$ So what can be proved is certainly far weaker than what one might expect.

However the case of $n!$ is certainly not generic. It is entirely predictable that there are $\lfloor 9/2 \rfloor+\lfloor 9/4 \rfloor+\lfloor 9/8 \rfloor=4+2+1$ $0$'s on the right. The other $12$ leading digits might be expected to split roughly equally and in fact split exactly equally.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I have read [1], you remark that Luca noted that his lower bound is probably weaker, but this is actually the point of my question! It is true that many of the less significant digits of $n!$ are zeros, but not too many: by Legendre-De Polignac formula the number $Z_n$ of trailing zeros of $n!$ is less than $n/(p-1)$, where $p$ is the greatest prime factor of $n$, so assuming that $n! / b^{Z_n}$ is "generic" my conjecture gives again $s_b(n!) = s_b(n! / b^{Z_n}) > C n \log n$. Thus I downvote you answer. $\endgroup$
    – user40023
    Commented Sep 1, 2014 at 9:35

You must log in to answer this question.