[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[obm-l] Teoria dos Numeros



Olá a todos,

estou meio sumido, mas acho q ainda sim posso mandar uma questaozinha q nao consegui resolver..
alias, nem sei c tem solucao...

Determine Sum{i=1 ... n} ( k mod i )

apenas para relatar a origem.. eh um problema de programacao, onde 1 <= k, n <= 10^9...
como nao encontrei uma solucao fechada, procurei algumas alternativas, e acabei encontrando algumas propriedades...
por exemplo:
Seja f(n) = Sum{i=1...n} {k mod i}.
Entao, se n > k, temos que: f(n) = f(k) + k*(n-k)
é possível mostrar que f(k) = f([k/2]) + g(k), onde [k/2] é o piso de k/2, e g(k) é conhecido e possui uma forma fechada..

minha duvida é: existe uma forma fechada para este somatorio??

obrigado,
Salhab