# 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$$?

• This is answered at Math Overflow Commented Aug 5, 2015 at 22:32
• @Winther Thanks for this, I'll update the question asking for an explicit non-trivial upper bound on $f(n)$, since it is obvious from your link that $f(n) = \Theta(n)$, and the lower bound is the more interesting but still an upper-bound $f(n) \leq cn$ for some $c < 1$ would be good. Commented Aug 5, 2015 at 22:40
• For any two integers (e.g. $i$ and $n-i$) there exist a geometrical progression containing both of them (e.g. $i\left(\frac{n-i}{i}\right)^k$) so $f(n) \leq \frac{n}{2}$. Combinding this with the MO bound we have $0.3n\leq f(n) \leq 0.5n$ Commented Aug 5, 2015 at 22:59
• @Winther Thanks a second time, this shows the upper bound constant is less than or equal to $1/2$. The argument is basically straightforward, so hopefully better constants can be proved. Commented Aug 5, 2015 at 23:05

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$.

• I am wondering if your ideas can be used to improve the concrete bound for the case of $n = 100$? Perhaps it will give $n = 37$? Unfortunately, I do not fully follow your arguments as I am inexperienced in analytic number theory, but I trust you will have some intuitions? Here is a link to the specific case: math.stackexchange.com/questions/1386381/… Commented Aug 7, 2015 at 12:44
• @ColmBhandal: the interesting fact is that $\mathbb{E}[V]$ is around $1.65$ for $n=100$, so if my conjecture holds, $37$ progressions are both needed and sufficient to cover $[1,100]$. Commented Aug 7, 2015 at 15:21
• Interesting consequence. Though I still would need a few hours study to get my head around the arguments made in favour of the conjecture. Commented Aug 8, 2015 at 0:50
• perhaps you should have a look at the other thread. $37$ is out of the bound found so far. Does this throw doubt on the conjecture? Commented Aug 9, 2015 at 17:40
• What is $\mathbb E[V]$?
– san
Commented Oct 2, 2015 at 22:27

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

• Dmitry do you have a link to your code, or a link to a deeper explanation of what you've done? Commented Jul 15, 2019 at 15:44
• I have added a link to my Java code. Enjoy! Commented Jul 17, 2019 at 2:49
• "Solve near optimally" means that the solution is achieved in optimal time or that it is nearly the optimal solution (probabilistic(?))? Or is it always the optimal solution?
– san
Commented Jul 20, 2019 at 4:46
• I used integer linear programming to confirm $f(1000)=362$ and $f(10000)=3621$. Commented Jul 21, 2019 at 0:22
• OK, yes. Optimal is 3620. I used the following formulation. Let $P$ denote the set of geometric progressions of length $\ge 3$. Let binary variable $x_p$ indicate whether progression $p\in P$ is selected, and let $s_i$ denote a slack variable for not covering element $i \in \{1,\dots,n\}$. (Pairs of uncovered elements can be covered with trivial 2-term progressions.) Then the problem is to minimize $\sum_p x_p + 0.5 \cdot \sum_i s_i$ subject to $\sum_{p: i \in p} x_p + s_i \ge 1$ for all $i$. Commented Jul 22, 2019 at 21:57