Página 1 de 1

(Rufino) Função máximo inteiro

Enviado: Seg 07 Set, 2020 16:50
por Deleted User 23699
Prove que

[tex3]d(1)+d(2)+d(3)+...+d(n)=\lfloor{\frac{n}{1}}\rfloor+\lfloor{\frac{n}{2}}\rfloor+\lfloor{\frac{n}{3}}\rfloor+...+\lfloor{\frac{n}{n}}\rfloor[/tex3]

onde d(i) é o número de divisores positivos do número natural i.

Re: (Rufino) Função máximo inteiro

Enviado: Sex 20 Out, 2023 16:48
por παθμ
Note que o número [tex3]\left \lfloor \frac{n}{k} \right \rfloor[/tex3] é a quantidade de múltiplos de [tex3]k[/tex3] que existem no intervalo [tex3][1, \;n].[/tex3]

Imagine cada parcela da soma [tex3]\sum_{i=1}^{n}d(i)[/tex3] como uma caixa inicialmente vazia, as quais vamos preenchendo com bolas que representam unidades. Para preenchê-las, vamos passar por cada um dos inteiros de 1 a n. Para cada [tex3]1 \leq k \leq n,[/tex3] vemos quais são os [tex3]1 \leq i \leq n[/tex3] que têm [tex3]k[/tex3] como um de seus divisores, e adicionamos uma bola a cada uma dessas caixas [tex3]i.[/tex3] Fazemos isso até passearmos por todos os [tex3]1 \leq k \leq n.[/tex3] Para cada inteiro [tex3]k,[/tex3] nós adicionamos então [tex3]\left \lfloor \frac{n}{k} \right \rfloor[/tex3] bolas no total, porque essa é a quantidade de múltiplos de [tex3]k[/tex3] no intervalo de 1 a n. Por isso, ao final, teremos adicionado [tex3]\sum_{k=1}^{n} \left \lfloor \frac{n}{k} \right \rfloor[/tex3] bolas nas caixas, e portanto:

[tex3]\boxed{\sum_{k=1}^{n}d(k)=\sum_{k=1}^{n} \left \lfloor \frac{n}{k} \right \rfloor}[/tex3]