OliForum Matematico

Scusate se posto nel luogo sbagliato ma sono nuovo.
il mio problema è questo:
Vorrei sapere se esiste un qualche approccio per questa "strana" cosa
$ \\ \sum_{i=0}^{k}\lceil \dfrac{n}{2^i}\rceil $

spero che possiate darmi una mano

Non e' che, per caso, k dipenda dal logaritmo binario di n? Comunque prova a pensare alla rappresentazione binaria di n...

se può esserti utile effettivamente k dipende dal logaritmo binario di n in questo modo:

$ k = \lceil \log_{2}{n}\rceil $

estite qualche relazione nota che sappiate?

MC

La somma considerata può essere ricondotta, con qualche attenzione, alla più nota $ v_2(n!)=\sum^{e}_{i=1}\left\lfloor \frac{n}{2^i}\right\rfloor $,
dove e è l'espoente massimo che rende la potenza di 2 minore o uguale a n e $ v_2(n!) $ è l'esponente di 2 nella fattorizzazione di $ n! $. Per questa trasformazione si usa: $ \left\lceil x\right\rceil=\left\lfloor x\right\rfloor+1 $ se x non è intero e $ \left\lceil x\right\rceil=\left\lfloor x\right\rfloor $ se x è intero. Inoltre $ \left\lceil \log_{2}n\right\rceil $ è uguale a e se n è una potenza di 2 oppure a e+1 se non lo è.

Kocour ha scritto:La somma considerata può essere ricondotta, con qualche attenzione, alla più nota $ v_2(n!)=\sum^{e}_{i=1}\left\lfloor \frac{n}{2^i}\right\rfloor $,
dove e è l'espoente massimo che rende la potenza di 2 minore o uguale a n e $ v_2(n!) $ è l'esponente di 2 nella fattorizzazione di $ n! $. Per questa trasformazione si usa: $ \left\lceil x\right\rceil=\left\lfloor x\right\rfloor+1 $ se x non è intero e $ \left\lceil x\right\rceil=\left\lfloor x\right\rfloor $ se x è intero. Inoltre $ \left\lceil \log_{2}n\right\rceil $ è uguale a e se n è una potenza di 2 oppure a e+1 se non lo è.

La conversione l'ho capita ma la mia ignoranza non mi permette di capire poi qual è il risultato della sommatoria. Potete aiutarmi ancora un pochino?

Grazie

Sia $ 2^e\leq n< 2^{e+1} $. Allora se $ k=e+1 $ la sommatoria vale $ k+1-h+n+v_2(n!) $ , se $ k=e $ il risultato è $ k-h+n+v_2(n!) $ dove $ n=2^hm $ con $ 0\leq h \leq e $ e m dispari.

Dipende per cosa ti serve la sommatoria... poi le si fa dire sotto tortura quello che ti serve...

Kocour ha scritto:Sia $ 2^e\leq n< 2^{e+1} $. Allora se $ k=e+1 $ la sommatoria vale $ k+1-h+n+v_2(n!) $ , se $ k=e $ il risultato è $ k-h+n+v_2(n!) $ dove $ n=2^hm $ con $ 0\leq h \leq e $ e m dispari.

ma questa sommatoria ha un nome? scusate ma le vostre spiegazioni mi risultano un po' nebulose...
Grazie lo stesso.

MC

Allora, quello che ha fatto Kocour non e' dare una risposta al tuo probema, ma semplicemente riformularlo, in termini di un'altra sommatoria.
Io ti ho chiesto a che cose ti servisse una forumla chiusa per quella sommatoria, solitamente sommatorie come quella compaiono in Compute Science in alcuni algoritmi, non si cerca una forumla chiusa, ma un upper/lower-bound...
Comunque in base ai libri ed agli articoli che ho consulato non esiste una forumla chiusa per quella sommatoria.

Effettivamente questa formula mi appare nel calcolo della complessità di un algoritmo. Ci lavoro da un po'. Inizialmente l'ho affrontato calcolando funzioni di Lower Bound ed Upper Bound. Poi mi sono chiesto se esistesse una forma chiusa (diciamo calcolabile in tempo costante) per il calcolo di tale termine. Non sapevo dove sbattere la testa, non è affatto facile trovare tali informazioni anche con l'aiuto di Internet.
Di questi problemi con parti intere superioni ed inferioni ne ho tre o quattro. Se siete interessati ve li posto, io ho perso la giovinezza appresso a queste cose. Spero di non aver sbagliato forum.

Grazie dell'aiuto. Il forum mi piace moltissimo. Credo che imparerò molto da voi e spero di esservi utile (tra le mie passioni c'è anche la teoria dei grafi e degli ipergrafi).
Ciau

MC

La formula e' calcolabile in tempo logaritmico (puoi usare operatori di shifting per effettuare la divisione per la potenza di 2 ).
Forse le tecniche richieste per l'analisi vanno un po' oltre questo forum, soprattutto se si incomincia a lavorare con le proprieta' delle funzioni convesse o le tecniche di perturbazione (non so se hai mai seguito un corso di matematica discreta...), se ne hai bisogno, puoi contattarmi via MP.

Ti ringrazio per la disponibilità. Effettivamente non ho mai seguito un corso di matematica discreta. Per adesso mi accontento di una maggiornazione di quella sommatoria. Ho maggiorato n alla potenza di 2 più vicina ma sono convinto che si possa fare molto meglio.
mi chiedo: ma dimostrare che quella sommatoria non si possa calcolare in tempo costante equivale a dire che il corrispondente problema è np-completo?


MC

Calma, calma, tra la possibilita' che il problema sia calcolabile in O(1) e che sia NP-completo ci sono migliaia di classi di complessita' intermedie, io ti ho fornito un algoritmo ce la calcola in O(ln n), quindi meno che polinomiale, il che' e' esattamente l'opposto di essere NP-completo....
Immagino che tu non abbia neanche mai seguito un corso di teoria della computabilita' o della complessita'...
Comunque questo esula molto dagli argomenti del forum... se vuoi la continuiamo viamessaggi privati...

Un ottimo upperbound, se non ho sbagliato i calcoli, e':
$ 2n\left(1-\frac{1}{2n}\right) = 2n-1 $