Is it possible to cover $\{1,2,...,100\}$ with $20$ geometric progressions?

Solution 1:

No.

A geometric progression can contain zero, one, or two primes. Since there are $25$ primes between 1 and 100, that means at least $5$ of your geometric sequences must contain $2$ primes. But such a sequence contains no other integers, since $p\left(\frac{q}{p}\right)^n$ is only an integer when $n$ is $1$ or $0$ for primes $p$ and $q$.

So the remaining $15$ progressions must now cover $90$ of the integers from $1$ to $100$. We show this is impossible with a counting argument, by considering how many values can be covered by progressions of various types:

1) Progressions where $\frac{a_{n+1}}{a_n}$ is an integer: If the ratio is $2$, then we can hit $7$ integers with the sequence $\{1,2,4,8,16,32,64\}$, or $6$ with the progression $\{2,4,8,16,32,64\}$ or $\{3,6,12,24,48,96\}$; otherwise the progression has at most $5$ elements. Note also that the second progression mentioned here is a subset of the first, so we don't need to count both.

If the ratio is more than $2$ the progression can cover at most $5$ integers (indeed, only the sequence $\{1, 3, 9, 27, 81\}$ can even cover this many; any others grow too quickly).

2) Progressions where $\frac{a_{n+1}}{a_n}$ is non-integer rational: Let the ratio be expressed as $\frac{m}{n}$ in lowest terms. Then suppose $a_0$ is the lowest integer in the progression and $a_k$ is the highest (that is $\leq 100$). We then have that $a_0\left(\frac{m}{n}\right)^k$ is an integer, which means that $a_0$ is a multiple of $n^k$. This means the progression cannot contain more than $5$ integers, because a progression with $6$ integers would need to start with a multiple of a $5^{th}$ power. As the only multiples of $5^{th}$ powers (below $100$) are $32$, $64$, and $96$, $n$ being $2$ in all these cases, the best we can do with a $5^{th}$ power starting point is $\{32, 48, 72\}$ which only contains $3$ numbers below $100$.

It's worth noting that there is at least one progression with $5$ integers, namely $\{16, 24, 36, 54, 81\}$.

3) Progressions where $\frac{a_{n+1}}{a_n}$ is irrational: If such a progression hits more than one integer, it must do so in rational ratios (ie $\left(\frac{a_{n+1}}{a_n}\right)^k$ is rational for some $k$), and so we can replace it with a rational-valued progression.

This means the most integers below $100$ that we could hope to cover with the remaining $15$ progressions is $7 + 6 + (13)(5) = 78$, well short of the necessary $90$.

Solution 2:

Any geometric progression of reals contains at most two squarefree integers. Since there are $61$ squarefree integers in $\{1, 2, 3, \ldots, 100\}$ (see OEIS A005117 and A013928) (note $1$ is considered squarefree), at least $\left\lceil{\frac{61}{2}}\right\rceil = 31$ geometric progressions are required. In particular you cannot do it with only $20$.

Slightly longer answer:

If $\mathcal{G}$ is a geometric progression of positive real numbers, then $\mathcal{G} \cap \mathbb{Q}$ is a geometric progression of positive rational numbers, and $\mathcal{G} \cap \mathbb{Z}$ is a geometric progression of positive integers (though the ratio may be a non-integer rational). So we only need to consider positive integer geometric progressions. Suppose the common ratio is $\frac{r}{s}$, where $r,s$ are relatively prime integers and $r > s \ge 1$. The geometric progression may be finite or infinite, but it has a minimum element. If $a$ is that minimum element, then the terms can be listed out: $$ a, \frac{ar}{s}, \frac{ar^2}{s^2}, \frac{ar^3}{s^3}, \cdots. $$ We see that of the terms $\frac{ar^k}{s^k}$ for $k \ge 2$ are divisible by $r^2$ (since $r$ and $s$ are relatively prime), and since $r \ge 2$, they are not squarefree. So only $a$ and $\frac{ar}{s}$, the first two terms, can potentially be squarefree. Therefore, there are at most $2$ squarefree integers in the geometric progression.

Solution 3:

Let $$\nu_p(n) = \max\{m\in\mathbb{N}: p^m\mid n\}$$ and $$ V(n) = \max_p \nu_p(n).$$ If $n$ belongs to some geometric progression, it may have at most $V(n)$ elements less than $n$. So, 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}.$$ Moreover, there is just one number in $\{1,\ldots,100\}$ such that $V(n)=6$, just two numbers such that $V(n)=5$ and just four numbers such that $V(n)=4$. So we may cover at most $7+6+5+5=23$ numbers in $\{1,\ldots,100\}$ with long sequences, and we are left with $77$ numbers that have to be covered by $13$ sequences of length at most five. Since $5\cdot 13<77$, there is no way.