23
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Berci Aug 5 '15 at 20:06
  • $\begingroup$ @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 :-) $\endgroup$ – Ant Aug 5 '15 at 20:18
  • 2
    $\begingroup$ @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$? $\endgroup$ – rabota Aug 5 '15 at 20:23
  • 5
    $\begingroup$ mathoverflow.net/questions/173047/… $\endgroup$ – simonzack Aug 5 '15 at 20:43
  • $\begingroup$ 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\}$.. $\endgroup$ – Paolo Leonetti Aug 6 '15 at 15:05
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – 6005 Aug 5 '15 at 22:04
  • $\begingroup$ @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. $\endgroup$ – Jack D'Aurizio Aug 5 '15 at 22:14
  • $\begingroup$ 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\}$. $\endgroup$ – Jack D'Aurizio Aug 5 '15 at 22:22
  • $\begingroup$ Jack, are you considering only geometric progressions of integers?.. $\endgroup$ – Paolo Leonetti Aug 5 '15 at 22:40
  • $\begingroup$ @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\}$. $\endgroup$ – Jack D'Aurizio Aug 5 '15 at 23:06
16
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – 6005 Aug 5 '15 at 21:57
  • $\begingroup$ You're not quite right about your number (1) ... Consider ${3,6,12,24,48,96}$ EDIT: 6005 beat me to it :) $\endgroup$ – Zubin Mukerjee Aug 5 '15 at 22:01
  • $\begingroup$ @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! $\endgroup$ – MartianInvader Aug 5 '15 at 22:06
  • $\begingroup$ 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$? $\endgroup$ – Paolo Leonetti Aug 5 '15 at 22:51
  • $\begingroup$ @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}$. $\endgroup$ – MartianInvader Aug 5 '15 at 23:50
13
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.