0

I have following expression: $\left\lfloor\frac{n}{10}\right\rfloor+\left\lfloor\frac{n}{10^2}\right\rfloor+\left\lfloor\frac{n}{10^3}\right\rfloor+\ldots+\left\lfloor\frac{n}{10^{\lfloor\log_{10} n\rfloor}}\right\rfloor$ where $n$ is a positive integer, greater than $0$

Can this expressoin be somehow simplified? If yes - how?

Thank you

Alastor
  • 145
blindProgrammer
  • 163

1 Answers1

1

Consider the decimal expansion of $n$. The first term is obtained from $n$ by deleting the rightmost digit, the second by deleting the rightmost $2$ etc., while the last term is just the leftmost digit. For example, with $n=123$ your sum is $12+1=13$.

Write $n=\sum_{i=0}^k a_i 10^i$, with integer coefficients $0\le a_i\le 9,\,a_k\ne 0$. The desired sum is $$\sum_{j=1}^k\sum_{i=j}^k a_i 10^{i-j}=\sum_{i=0}^k a_i(\sum_{j=1}^i 10^{i-j})=\sum_{i=0}^k a_i\tfrac{10^i - 1}{9}=\tfrac{n-\sum_i a_i}{9}.$$Note that $\sum_i a_i$ is the sum of digits of $n$.

J.G.
  • 115,835
  • Thank you very much for your informative response. To compute the expression I have mentioned in my question, it is required approximately logarithmic number of mathematical operations. While your formula looks small, we need to calculate each individual digits from number n, which will also take logarithmic number of mathematical operations and in this sense the complexity of above two expressions are the same. I should have mentioned this in my question but i forgot: Could there be a way of simplification, that will also reduce the number of required mathematical oparations? – blindProgrammer Jun 18 '18 at 05:47
  • 1
    @blindProgrammer I sincerely doubt it. It's rare for problems to have $o(\log n)$ solutions. In this case, any such solution could be used to sum the digits of $n$ faster than the usual way, which makes the idea less likely. – J.G. Jun 18 '18 at 06:25