Re: [obm-l] Problemas em aberto

[Carlos Gustavo Tamm de Araujo Moreira <gugu@xxxxxxx>]

   Caro Domingos,
   Note que a diferenca entre as duas somas e' soma(p<=n,k>=2)[n/p^k]<=
soma(p<=n)(n/p(p-1))=O(n) (aqui p percorre os primos), donde, como voce
mostrou que uma das somas e' assintoticamente n.loglog(n), a outra
automaticamente tambem e'. Note que voce so' usou ii), que e' mais facil de
provar que i) (veja o Hardy e Wright). Alem disso, para ver que os limites
sao infinitos, basta usar que a serie dos inversos dos primos da' infinito,
o que provavelmente ja' foi provado nesta lista (senao me avisem que eu
provo).
   Abracos,
             Gugu
 
>
>>
>>
>>
>>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
>=========================================================================
>

=========================================================================
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
=========================================================================