What is known about the minimal number $f(n)$ of geometric progressions needed to cover $\{1,2,\ldots,n\}$, as a function of $n$?

What is known about the minimal number $f(n)$ of geometric progressions needed to cover $\{1,2,\ldots,n\}$, as a function of $n$?

So a geometric progression can contain at most two primes. This automatically gives a lower bound on the minimal number $f(n)$ of geometric progressions needed to cover the integers $\{1,2,\ldots,n\}$, at least asymptotically, because of the prime number theorem. But this seems like a very crude bounding technique. I don't expect a closed-form formula for $f(n)$ is known. But what about its asymptotics? Can we say that $f(n) = \Theta (g(n))$ for some easy to understand function $g(n)$? Or give some fairly tight asymptotic upper and lower bounds for $f(n)$, even if there is an asymptotic growth rate gap between the two bounds?

UPDATE: From the link given in the comment, we have $f(n) \geq cn$ always for some constant $0 < c < 1$. And clearly $f(n) \leq n$. So then the interesting question seems to become, what is the best constant $d \leq 1$ we can find so that we can say $f(n) \leq dn$ holds for large enough $n$?

Solution 1:

Just some thoughts.

By quoting the other question, I would say that the asymptotic depends on the distribution of $$ V(n) = \max_p \max\left\{m\in\mathbb{N}:p^m\mid n\right\} $$ that is concentrated around small values - the crude bound the OP mentions is equivalent to say that $V$ is concentrated around $1$, so we need many sequences (i.e. intersections between a geometric progression and $\{1,\ldots,n\}$) with small length ($1+1$).

I think this is useful: if the sequence $A=\{a_1,a_2,\ldots,a_l\}$ is the intersection between a geometric progression and $\{1,\ldots,100\}$, we have: $$\sum_{a\in A}V(a)\geq\binom{l}{2},$$ hence if $A_1,\ldots,A_k$ cover $\{1,\ldots, n\}$, we have $l_1+\ldots+l_k\geq n$ and: $$ \sum_{k}\sum_{a\in A_k} V(a) \geq \sum_k\binom{l_k}{2}, $$ so both the $L^1$ and $L^2$-norm of $(l_1,\ldots,l_k)$ are constrained.

My conjecture is that $k$ behaves like $\displaystyle\frac{n}{\mathbb{E}[V]+1}$, and it is quite trivial that $\mathbb{E}[V]=\Theta(1)$.

Stealing 6005's argument in the other question, no geometric progression can take more than two squarefree values, and since there are about $\frac{6}{\pi^2}n$ squarefree integers in $\{1,\ldots,n\}$, $k\geq\frac{3}{\pi^2}n$.

Solution 2:

I wrote a program that computes $f(n)$ for larger $n$. It generates feasible geometric progressions (sets) and then uses simulated annealing to solve (near optimally) the resulting set covering problem. From other answers (like http://math.stackexchange.com/questions/1386381/cover-1-2-100-with-minimum-number-of-geometric-progressions) we already know that $f(100)=36$. For larger $n$, I was able to compute some good upper bounds on $f(n)$. I found that $f(1000) \leq 362$ and $f(10000) \leq 3620$. After seeing these numbers I suddenly realised that $f(n) \approx n/e$, which was rather surprising! I also submitted a sequence to OEIS: https://oeis.org/A309095

Here is my Java code to compute $f(n)$: https://pastebin.com/b23ugGZN