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

Recall that a sequence $A=(a_n)_{n\ge 1}$ of reals is said to be a geometric progression whenever $a_{n+1}/a_n$ is constant for each $n\ge 1$. Then, replacing $20$ with $12$, the following question comes from an old Russian competition:

Problem: Can you find $20$ geometric progressions $A_1,\ldots,A_{20}$ of reals such that $$\{1,2,\ldots,100\} \subseteq A_1 \cup \ldots A_{20}?$$

• Well, the direction along primes might help, as if a geometric progression contains more primes, it can contain at most $2$ primes and no more integers. – Berci Aug 5 '15 at 20:06
• @Berci That would explain why there was a $12$ in the original question, as we have $25$ primes between $1$ and $100$ :) I'll think more about this tomorrow :-) – Ant Aug 5 '15 at 20:18
• @jordan have you managed to cover $\{1,\ldots,100\}$ by $21$ arithmetic progressions? Or what is it that makes you ask this question with $20$ instead of $12$? – rabota Aug 5 '15 at 20:23
• mathoverflow.net/questions/173047/… – simonzack Aug 5 '15 at 20:43
• You can find two linked questions: math.stackexchange.com/questions/1386381/… and math.stackexchange.com/questions/1385991/… about the minimum number of GP required to cover $\{1,...,100\}$.. – Paolo Leonetti Aug 6 '15 at 15:05

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.

• Can you explain where $7 + 6 + 5 + 5 = 23$ comes from, what a "long sequence" is, and where you use the fact $\sum_{a \in A} V(a) \le {l \choose 2}$? having some trouble following. – 6005 Aug 5 '15 at 22:04
• @6005: essentially, the intersection between $\{1,\ldots,100\}$ and a geometric sequence may be moderately big only if the ratio of the geometric series is $2$ or $3$. Otherwise, we have to cover many numbers with short sequences. The inequality about $\sum V$ is not really used, but I originally thought that a proof through Cauchy-Schwarz inequality was possible. – Jack D'Aurizio Aug 5 '15 at 22:14
• The numbers that are easy to cover are $\{1,2,4,8,16,32,64\}\cup\{3,6,12,24,48,96\}\cup\{5,10,20,40,80\}$. I wonder, me may also tackle the problem in the following way: proving that if the ratio of a geometric series is $\frac{a}{b}$ with $\gcd(a,b)=1$ and $a,b$ both odd (irrational ratios are irrelevant) we may cover at most $5$ integers in $\{1,\ldots,100\}$. – Jack D'Aurizio Aug 5 '15 at 22:22
• Jack, are you considering only geometric progressions of integers?.. – Paolo Leonetti Aug 5 '15 at 22:40
• @jordan: no, I am considering general geometric progressions, but I am evaluating a specific arithmetic function on the intersection between them and $\{1,\ldots,100\}$. – Jack D'Aurizio Aug 5 '15 at 23:06

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

• What about $3, 6, 12, 24, 48, 96$? In case (1), this is not the powers of two but covers more than 4 integers, contrary to what you claimed. – 6005 Aug 5 '15 at 21:57
• You're not quite right about your number (1) ... Consider ${3,6,12,24,48,96}$ EDIT: 6005 beat me to it :) – Zubin Mukerjee Aug 5 '15 at 22:01
• @6005 and Zubin Thanks! You are correct of course. I've modified the argument to be a little more meticulous so it doesn't miss this case. Fortunately there was enough headroom on my upper bound to accommodate! – MartianInvader Aug 5 '15 at 22:06
• I just read the first part of your proof: a sequence which contains (at least) 2 primes, contains no more integers. Why do you consider only progressions of typo $p(q/p)^n$? – Paolo Leonetti Aug 5 '15 at 22:51
• @jordan You need the progression to end up multiplying by $\frac{q}{p}$, so the only option for the ratio is of the form $(\frac{q}{p})^{\frac{1}{n}}$, but if $n > 1$ all the non-integral powers of $\frac{q}{p}$ will yield irrational solutions, so you can assume you're just taking powers of $\frac{q}{p}$. – MartianInvader Aug 5 '15 at 23:50

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

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.