# Primitive sequence $a_i$ attaining Pillai's bound on $\sum_{i} 1/a_i$

A primitive sequence $1<a_1<\ldots<a_k\leq n$ is a sequence of integers no one of which divides any other, investigated by Erdos, Behrend and others, over the last 80 years. In fact, $\max k=\lfloor \frac{n+1}{2}\rfloor,$ which can be shown by taking exactly one member from each chain in the divisibility poset, namely $$C_x=\{x,2x,2^2x,\ldots\} \subset \{1,\ldots,n\}$$as $x$ ranges over the odd integers in $\{1,\ldots,n\}$. The easy examples of such sets, e.g., the numbers in $\{1,\ldots,n\}\cap [\lceil \frac{n}{2} \rceil,n]$ have the following property $$\sum_{i:a_i\leq n} \frac{1}{a_i} \leq c$$ for some absolute constant $c$ as $n$ increases.

However, Erdos states that S. Pillai observed that there is a constant $c'$ such that for every $n$ there is a finite primitive sequence all whose terms are upper bounded by $n$ such that $$\sum_{i:a_i\leq n} \frac{1}{a_i} > c' \frac{\log n}{\sqrt{\log \log n}}.$$

Are there any results on what such sequences may look like?

Edit: Is the value of the constant $c'$ or bounds on it known?

Fix $k$ and consider the set $E_k$ of all numbers with exactly $k$ prime factors (counted with multiplicity). They definitely form a primitive sequence. Already for $k=1$ sum of reciprocals is unbounded. I think, for $k=[\log \log n]$ we should obtain lower bound like $\log n/\sqrt{\log\log n}$. It is natural to expect: randomly chosen number in $[1,n]$ has exactly $k$ prime factors with probability about $1/\sqrt{\log\log n}$ by Erdős-Kac theorem
Denote $k=[\log \log n]$. Then by result of Selberg cited by alpoge in the comments, $|E(k)\cap [1,x]|\geq C x/\sqrt{k}$ for all $x\in [\sqrt{n},n]$. It follows that $$\sum_{m\in E(k)\cap [1,n]} m^{-1}\geq \sum_{m\in E(k),n\geq v\geq m} \frac1{v(v+1)}\geq \sum_{v=\sqrt{n}}^n \frac1{v(v+1)}|E(k)\cap [1,v]|\geq c\log(n)/\sqrt{k}$$ for some $c>0$.
• Indeed the number of integers $n\leq x$ with exactly $k\leq 1.99\log\log{x}$ prime factors is $\sim \frac{x}{\log{x}} \frac{(\log\log{x})^k}{k!}$. Taking $k = \log\log{x} + O(1)$ and using Stirling gives the lower bound you claim (upon splitting the sum into dyadic intervals and applying the asymptotic). – alpoge Dec 1 '15 at 15:33
• I always forget the constant! There should be a constant $f((k-1)/\log\log{x})$ in the asymptotic, too. This is proved in Selberg's "Note on a paper by L.G. Sathe". – alpoge Dec 1 '15 at 15:41
• We need not "many numbers", but "large sum of reciprocals", it is slightly different thing. But since this works for all $x$, Abel transform works. – Fedor Petrov Dec 1 '15 at 16:26
• @kodlu it is explained in the answer: expand $1/m=\sum_{v\geq m} 1/(v(v+1))$ and change order of summation – Fedor Petrov Dec 4 '15 at 8:21