Re: [obm-l] Problemas em aberto

["Domingos Jr." <dopikas@xxxxxxxxxx>]

>
>
>
>20) Seja f: S = {2, 3, 4, 5, 6, ...} -> S a função que leva um número n no
>seu número de fatores primos. Por exemplo, f(6) = 2 e f(12) = f(8) = 3.
>Quanto vale lim[n->inf] (f(2) + f(3) + ... + f(n))/(n-1)?
>


A resposta é bonitinha quando f não conta os primos repetidamente...
Vamos usar aquele princípio básico da combinatória que nos ensina a 
contar a mesma coisa de duas maneiras distintas :-)
Note que f(2) + ... + f(n) é equivalente a Soma_{p primo} Piso{n/p}.

Para verificar isso, disponha caixas indexadas por todos os primos <= n. 
Olhe para cada elemento i <= n, colocando um marcador na caixa p em cada 
primo p que é divisor de i. É evidente que o número de marcadores de 
todas as caixas é f(2) + ... + f(n). Por outro lado, quantos marcadores 
teremos numa caixa p? Cada inteiro i <= n que é múltiplo de p colocou 
exatamente um marcador em tal caixa, logo temos Piso{n/p} marcadores em 
tal caixa.

Sempre que o termo "p" aparecer, fica implícito que p é primo, ok?
Como Piso{n/p} > n/p - 1, temos:
f(2) + ... + f(n) > Soma_{p  <= n} [n/p - 1] = -pi(n) + n Soma_{p <=n} 
[1/p],
onde pi(n) é a função que conta o número de primos <= n.

Resultados clássicos nos grantem que:
i) pi(n) ~ n/(log n)
ii) Soma_{p <=n} [1/p] ~ log log n, logo

Soma_{p  <= n} [n/p - 1] ~ n[log log n - 1/(log n)].

Isso prova que lim_{n -> oo} [f(2) + ... + f(n)]/n = oo. Como a nossa f 
tem valores sempre menores ou iguais aos valores da f do problema 
original, o resultado vale também para o problema original.

Se f conta os primos de forma repetida então a nossa contagem passa a ser
f(2) + ... + f(n) = Soma_{k = 0..oo} Soma_{p primo} Piso{n/p^k}.
Talvez alguém da lista tenha paciência de analisar assintoticamente o 
mostrinho...

[ ]'s
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================