Consider the set $S_n=\{1,2,\cdots ,n\}$. What is the minimum number of distinct geometric progressions that cover $S_n$? Let us call this number $a_n$. I was wondering about this number after doing a problem from the Allrussian MO, 1995.

Can the set $\{1,2,\cdots,100\}$ be covered with $12$ geometric progressions?

It becomes straightforward after observing the fact no three primes can be in a geometric progression. Hence the problem is restated to the obvious contradiction $$\pi(100)\le 24$$ Now I had searched a bit and here it is proven that $a_{100}\ge 24$. Now I would like some asymptotics, or references, or better bounds on $a_n$ .

I have also found the fact that $$a_n\ge \left\lfloor{\frac{3n}{\pi^2}}\right\rfloor$$

Which is obvious since any geometric progression contains at most $2$ squarefree numbers and there are about $\dfrac{6n}{\pi^2}$ squarefree numbers less than $n$. Note it surpasses the bound given. But is something better possible? Thanks in advance.

9more comments