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
ib
i -1 b
1b
0)
2, i.e., n = ∑
it=0b
t2
t.The first type of WDS is defined as
M it=0 t t 0 M M M M M M M-1d=0 d M,d M M M M,d i1 i2 ik 1 2 k M kt =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
ib
i -1... b
1b
0)
2, i.e., n = ∑
it=0b
t2
t.The first type of WDS is defined as
S
M(n) = ∑
it=0t(t +1)(t +2) ... (t + M - 1)b
t2
tfor 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 of
TSM(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 as
WM(n)=∑kt =1tM2it
for M ≥ 1 and W0(n) = n. Also, define
TWM(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 that
TWM(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.
Post a Comment