OliForum Matematico

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

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

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

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 trasforma...

Volevo presentarmi....sapete come funziona con quella buona educazione insegnataci da bambini. In ogni modo eccomi qui alle prese con quotidiani problemi di carattere combinatorico e su grafi. Non ho studiato mai la matematica in maniera troppo profonda, sono sempre andato avanti per intuizione. Pri...

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

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