Question

Considere uma função

f: N* → N

onde para cada n ∈ N*, f(n) fornece quantos dígitos são necessários para se escrever todos os naturais em sequência de 1 até n.

Escreva uma lei de formação para f na forma fechada.

f(n) = __________

=====

Favor encontrar a expressão fechada para todos os somatórios envolvidos.

Answer 1

Olá Lukyo



Primeiro vamos pensar através de valores pré-definidos, uma forma de saber quantos dígitos existirão de 1 até esse número. Vamos supor que eu queira saber quantos dígitos existem de 1 a 20.

De 1 a 9 são os números de 1 dígito, portando existirão 9 dígitos. De 10 a 20 serão números de 2 dígitos, para saber quantos números existem de 10 a 20, basta tirar a diferença entre eles e somar 1. 

20 - 10 + 1 = 11

Então existem 11 números de 2 dígitos de 10 a 20. Para saber quantos dígitos existem de 10 a 20, basta multiplicar por 2 por 11

2 * 11 = 22

Então basta somar a quantidade de dígitos que existem com números de 1 digito com a quantidade de dígitos de 10 a 20.

9 + 22 = 31

Supondo agora que queremos saber a quantidade de dígitos que existem de 1 a 310.

Primeiro teríamos que saber a quantidade e dígitos que tem de 1 a 9, que já sabemos que é 9. Depois precisaremos saber a quantidade de dígitos que existem com os números de dois dígitos, ou seja, de 10 a 99.

99 - 10 + 1 = 90

E por fim, precisaríamos saber a quantidade de algarismos que existem com os números de 3 dígitos que vai até 310.

310 - 100 + 1 = 211

Então a partir de alguns números conseguimos tirar algumas conclusões. A primeira é que, para saber a quantidade de dígitos que existem de 1 a n, é necessário saber antes a quantidade total de dígitos que existem com números com dígitos menores que n. 

Como já vimos, a quantidade de dígitos de 1 a 9 (números de 1 dígito) é 9. A quantidade de dígitos que existem de 10 a 20 (números de 2 dígitos) é 2 * (99 - 10 + 1). Já a quantidade de dígitos que existem de 100 a 999 (números de 3 dígitos) é 3 * (999 - 100 + 1).

Ou seja, é o produto da quantidade de dígitos pela quantidade de números que existem com aquela quantidade de dígitos. Então generalizando, temos

1 * 9 + 2 * (99 - 10 + 1) + 3 * (999 - 100 + 1) + 4 * (9 999 - 1 000 + 1) + ...
1 * 9 + 2 * (90) + 3 * (900) + 4 * (9 000) + ...

Então a quantidade total de dígitos que existem, de números de 1 dígitos até x dígitos, pode ser representada da seguinte forma

$\mathsf{\displaystyle\sum_{k=1}^x k\cdot9\cdot10^{k-1}=}$ 1 * 9 + 2 * 90 + 3 * 900 + ... + x * 9 * 10ˣ⁻¹

Mas o que queremos, é saber a quantidade de dígitos que existem de 1 até um número n. Para isso poderíamos pensar da seguinte forma. Poderíamos somar a quantidade de dígitos que existem de números de 1 dígito até números com 1 dígito a menos que n, ou seja.

1 * 9 + 2 * 90 + 3 * 900 + .. + (x - 1) * 9 * 10ˣ⁻²

E agora precisamos saber a quantidade de dígitos que existem do menor número de x dígitos até n. O menor número com uma quantidade qualquer de dígito, é sempre dado por uma potência de 10. O menor número de 3 dígitos por exemplo é o 100. Portanto teríamos

1 * 9 + 2 * 90 + 3 * 900 + ... + (x - 1) * 9 * 10ˣ⁻² + x * (n - 10ˣ⁻¹ + 1) 

Portanto temos,

$\mathsf{\displaystyle\sum_{k=1}^{x-1} k\cdot9\cdot10^{k-1}+}$ x * (n - 10ˣ⁻¹ + 1)

Mas seria necessário saber a quantidade de dígitos x que esse número n tem. Para isso faremos o uso da função piso e do logaritmo. 

Quando tiramos o logaritmo de um número maior que 1 na base 10, a parte inteira é sempre uma unidade menor que esse número. Vejamos alguns exemplos

$\mathsf{\ell og~5\approx0,69}\\\\\mathsf{\ell og~20\approx 1,30}\\\\\mathsf{\ell og~320\approx2,50}$

Note que a parte inteira é sempre uma unidade menor que a quantidade de algarismos, então basta somar uma unidade e a parte inteira será exatamente a quantidade de algarismos. No entanto, a parte decimal se tornaria um problema, então faremos o uso da função piso, que nos retorna somente a parte inteira de um número. 

Notação da função piso, é $\mathsf{\left\lfloor x\right\rfloor}$

Portanto, utilizando logaritmo e a função piso, conseguimos obter a quantidade x de dígitos que um número n tem

$\mathsf{x=\left\lfloor 1+\ell og~n~\right\rfloor}$

Agora basta achar a fórmula fechada do somatório $\mathsf{\displaystyle\sum_{k=1}^{x-1}k\cdot9\cdot10^{k-1}}$.


$\mathsf{\bullet}$ Siga os anexos 2, 3, 4 e 5 abaixo e veja como foi feito o desenvolvimento para achar a formula fechada desse somatório


Achando f(n) 

$\mathsf{f(n)=\dfrac{x\cdot9\cdot10^{x-1}-10^x+1}{9}+x\cdot(n-10^{x-1}+1)}$

Lembrando que $\mathsf{x=\left\lfloor 1+\ell og~n\right\rfloor}$


$\boxed{\mathsf{\!f(n)\!=\!\dfrac{(\left\lfloor\ell og~n\right\rfloor\cdot9-1)\cdot \!10^{\left\lfloor\ell og~n\right\rfloor\!}+1}{9}+\!\left\lfloor 1+\ell og~n\right\rfloor\cdot(n-10^{\left\lfloor\ell og~\!n\right\rfloor}+1)}}}$


Dúvidas? comente.