The number of distinct subsums of ∑₁^{𝑁}1/𝑖
Authors: Bleicher M. N. , Erdős P. 
Published: June 2010

In this paper we improve the lower bounds for the number,

S
(
N
)

S(N)

, of distinct values obtained as subsums of the first N terms of the harmonic series. We obtain a bound of the form
\[
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S left-parenthesis upper N right-parenthesis greater-than-or-slanted-equals e left-parenthesis StartFraction upper N log 2 Over log upper N EndFraction product Underscript 3 Overscript k plus 1 Endscripts log Subscript j Baseline upper N right-parenthesis">

S
(
N
)
⩾
e

(

N
log
⁡
2

log
⁡
N

∏
3

k
+
1

log

j

N

)

S(N) \geqslant e\left ( {\frac {{N\log 2}}{{\log N}}\prod \limits _3^{k + 1} {{{\log }_j}N} } \right )

\]
whenever

log

k
+
1

N
⩾
k
+
1

{\log _{k + 1}}N \geqslant k + 1

, for

k
⩾
3

k \geqslant 3

. Slight modifications are needed for

k
=
1
,
2

k = 1,2

. We begin by discussing the number

Q
k

(
N
)

{Q_k}(N)

of integers

n
⩽
N
,
n
=

p
1

p
2

⋯

p
k

n \leqslant N,n = {p_1}{p_2} \cdots {p_k}

, where

p
i

>

e

α

p

i
−
1

,
i
=
2
,
⋯
,
k

{p_i} > {e^{\alpha {p_{i - 1}}}},i = 2, \cdots ,k

. We prove that
\[
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartFraction upper N Over log upper N EndFraction product Underscript i equals 1 Overscript k plus 1 Endscripts log Subscript i Baseline upper N less-than-or-slanted-equals upper Q Subscript k Baseline left-parenthesis upper N right-parenthesis less-than-or-slanted-equals left-parenthesis 1 plus StartFraction k Over log Subscript k plus 1 Baseline upper N EndFraction right-parenthesis StartFraction upper N Over log upper N EndFraction product Underscript i equals 3 Overscript k plus 1 Endscripts log Subscript i Baseline upper N period">

N

log
⁡
N

∏

i
=
1

k
+
1

log

i

N
⩽

Q
k

(
N
)
⩽

(

1
+

k

log

k
+
1

N

)

N

log
⁡
N

∏

i
=
3

k
+
1

log

i

N

.

\frac {N}{{\log N}}\prod \limits _{i = 1}^{k + 1} {{{\log }_i}N \leqslant {Q_k}(N) \leqslant \left ( {1 + \frac {k}{{{{\log }_{k + 1}}N}}} \right )} \frac {N}{{\log N}}\prod \limits _{i = 3}^{k + 1} {{{\log }_i}N} .

\]
This bound is valid for

log

k
+
1

N
⩾
k
+
1

{\log _{k + 1}}N \geqslant k + 1

and for

1
⩽
α
⩽
2
(
1
−

e
2

(
4
)

/

e
3

(
4
)
)

1 \leqslant \alpha \leqslant 2(1 - {e_2}(4)/{e_3}(4))

. The symbols

log
i

x

{\log _i}x

and

e
i

(
x
)

{e_i}(x)

are defined by
\[
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartLayout 1st Row 1st Column e 0 left-parenthesis x right-parenthesis equals x comma 2nd Column a m p semicolon e Subscript i plus 1 Baseline left-parenthesis x right-parenthesis equals e Superscript e Super Subscript i Superscript left-parenthesis x right-parenthesis Baseline comma 2nd Row 1st Column log Subscript 0 Baseline x equals x comma 2nd Column a m p semicolon log Subscript i plus 1 Baseline x equals log left-parenthesis log Subscript i Baseline x right-parenthesis comma EndLayout">

e
0

(
x
)
=
x
,

a
m
p
;

e

i
+
1

(
x
)
=

e

e
i

(
x
)

,

log

0

x
=
x
,

a
m
p
;

log

i
+
1

x
=
log
⁡
(

log

i

x
)
,

\begin {array}{*{20}{c}} {{e_0}(x) = x,} \hfill & {{e_{i + 1}}(x) = {e^{{e_i}(x)}},} \hfill \\ {{{\log }_0}x = x,} \hfill & {{{\log }_{i + 1}}x = \log ({{\log }_i}x),} \hfill \\ \end {array}

\]
where

log
⁡
x

\log x

denotes the logarithm to the base e.