THESIS
2009
xiv, 86 p. : ill. (some col.) ; 30 cm
Abstract
In this thesis, we analyze two types of weighted digital sums (WDS) which arise in algorithm analysis. Start by expressing integer n in binary as n = (b
_{i}b
_{i -1} b
_{1}b
_{0})
_{2}, i.e., n = ∑
^{i}_{t=0}b
_{t}2
^{t}.The first type of WDS is defined as
_{M} ^{i}_{t=0} _{t} ^{t} _{0} _{M} _{M} _{M} _{M} _{M} ^{M} ^{M-1}_{d=0} ^{d} _{M,d} _{M} _{M} _{M} _{M,d} ^{i1} ^{i2} ^{ik} _{1} _{2} _{k} _{M} ^{k}_{t =1} ^{M} ^{it} _{0}...[
Read more ]
In this thesis, we analyze two types of weighted digital sums (WDS) which arise in algorithm analysis. Start by expressing integer n in binary as n = (b_{i}b_{i -1}... b_{1}b_{0})_{2}, i.e., n = ∑^{i}_{t=0}b_{t}2^{t}.The first type of WDS is defined as
S_{M}(n) = ∑^{i}_{t=0}t(t +1)(t +2) ... (t + M - 1)b_{t}2^{t}
for M ≥ 1 and S_{0}(n) = n. Also, define
TS_{M}(n) = 1/n∑_{jSM(j).By employing the Mellin-Perron formula, we derive exact closed-form formulae for TSM(n), which are in the form ofTSM(n) =λMn lgM n + ∑M-1d=0(n lgd n)FM,d(lg n) + cM,where λM, cM are constants and FM,d(u)’s are periodic functions with period one, which are given by absolutely convergent Fourier series.By expressing integer n as n = 2i1 + 2i2 + ... + 2ik with i1 > i2 > ... > ik ≥ 0, the second type of WDS is defined asWM(n)=∑kt =1tM2itfor M ≥ 1 and W0(n) = n. Also, defineTWM(n) = 1/n ∑jWM(j).Using higher order case of the Mellin-Perron formula, we derive an exact closed-form formula, which is in terms of Riemann-Zeta function values, for TW1(n). This method cannot be generalized to the cases with larger M’s, so we use another method for analyzing the cases with M ≥ 2. For M ≥ 1, we show thatTWM(n) = nGM(lg n)+ dM lgM n + ∑M-1d=0(lgd n) GM,d(lg n),where dM is a constant, GM(u) and GM,d(u)’s are periodic functions with period one, which are given by absolutely convergent Fourier series.[ Hide abstract ]}
Post a Comment