# Convergent sub-sequences of reciprocals of large sets using greedy algorithm.

Let $$A\subset\mathbb{N}$$ be large, that is $$\displaystyle\sum_{n\in A} \frac{1}{n}\$$ diverges. Write $$\ A = \{ a_1, a_2, a_3, \ldots \};\ a_1 < a_2 < a_3 < \ldots.$$

Let $$x\in\mathbb{R}_{>0},$$ and define:

• $$a_1(x)$$ to be the least positive member of $$A$$ such that $$\displaystyle \frac{1}{a_1(x)} < x.$$
• For each $$n\geq 1,$$ let $$a_n(x)$$ be the least positive member of $$A$$ greater than $$a_{n-1}(x)$$ such that $$\displaystyle\sum_{k=1}^{n} \frac{1}{a_k(x)} < x.$$ (greedy algorithm).

Prove or disprove: $$\exists\ N\in\mathbb{N}$$ such that $$a_N(x) \geq a_{N-1}(x)(a_{N-1}(x)-1) + 1.$$

Or does there exist an $$x>0$$ such that this is not true?

I think that for $$A=\mathbb{N}$$ this is true. In fact for this case, I think $$\exists\ N$$ such that $$\ a_n(x) \geq a_{n-1}(x)(a_{n-1}(x)-1) + 1\ \forall\ n\geq N.$$ This comes from the fact that, for example, $$\frac{1}{11} + \frac{1}{(11)(10)} = \frac{1}{10}.$$

But if $$A \neq \mathbb{N},$$ for example $$A=\mathbb{P},$$ then we cannot say that $$\frac{1}{11} + \frac{1}{(11)(7)} = \frac{1}{7}:$$ indeed, the left-hand side is less than the right-hand side. So how to proceed?

• For $A=\Bbb N$ I agree this is probably true; here's one entry point to the relevant topic in Egyptian fractions: en.wikipedia.org/wiki/… Commented Jun 16 at 22:21

The conjecture is false. For a counterexample, let $$A_m = [5^m, 2\cdot 5^m) \cap \Bbb Z$$ and set $$A=\bigcup_{m=1}^\infty A_n$$. Note that $$\sum_{k\in A_m} \frac1k \sim \log 2$$ for each $$m$$, and so $$A$$ is large. Now choose $$x=\sum_{m=1}^\infty \biggl( \frac1{5^m}+\frac1{5^m+1} \biggr) \approx 0.465062.$$ Then the greedy algorithm produces the "obvious" sequence $$(a_n(x)) = (5^1,5^1+1,5^2,5^2+1,5^3,5^3+1,\ldots)$$. Confirming this assertion uses the upper bound $$\sum_{m=\ell}^\infty \biggl( \frac1{5^m}+\frac1{5^m+1} \biggr) < \sum_{m=\ell}^\infty \biggl( \frac1{5^m}+\frac1{5^m} \biggr) = \frac1{2\cdot 5^\ell},$$ so that the element chosen after $$a_{2m-1}(x) = 5^m$$ and $$a_{2m}(x)=5^m+1$$ cannot come from $$A_m$$.