20
$\begingroup$

In another question, posted here by jordan, we are asked whether it is possible to cover the numbers $\{1,2,\ldots,100\}$ with $20$ geometric sequences of real numbers. Naturally, we would like to extend the question:

Problem: What is the minimum number $n$ of geometric progressions $A_1, A_2,\ldots,A_{n}$ of rational* numbers such that $$ \{1,2,\ldots,100\} \subseteq A_1 \cup A_2\cup \ldots\cup A_{n}? $$

In the other question, 6005 obtained a lower bound of $31 \leq n$ with an argument about square free integers. We can also obtain an upper bound of $43$ as follows. Consider these $5$ sequences: $[1, 2, 4, 8, 16, 32, 64]$ and $[6, 12, 24, 48, 96]$ and $[5, 10, 20, 40, 80]$ and $[3, 9, 27, 81]$ and $[7, 21, 63]$. Together, these cover $7 + 5 + 5 + 4 + 3 = 24$ terms. The remaining $76$ terms can be covered in at most $38$ sequences, by an argument made here. So we have the bound:

$$31 \leq n \leq 43$$

Can anyone do better?

*We need only consider rational ratios by arguments made in answers to the original question.

(Update) We have a winner!! Thanks to the cumulative efforts of the answerers below, we have arrived at $n = 36$. The upper bound is thanks to jpvee, and the lower bound is due to san. Hooray!

$\endgroup$
7
  • $\begingroup$ I think we can get a few more off the upper bound with this method e.g. $11, 33, 99$ but eventually it will run out of steam and we'll need a new idea. $\endgroup$
    – Colm Bhandal
    Commented Aug 6, 2015 at 10:48
  • $\begingroup$ About the new idea: did you check this related question? math.stackexchange.com/questions/1385991/… Jack claims that, if this is true, then $n \in \{37,38\}$ $\endgroup$
    – Paolo Leonetti
    Commented Aug 6, 2015 at 15:02
  • $\begingroup$ I saw a conjecture along those lines alright, but was it proved? $\endgroup$
    – Colm Bhandal
    Commented Aug 6, 2015 at 15:38
  • $\begingroup$ No, I don't think so: anyway, it would be better to ask Jack's opinion.. $\endgroup$
    – Paolo Leonetti
    Commented Aug 6, 2015 at 15:41
  • $\begingroup$ Yes I agree. Unfortunately I don't know how to tag him as he's not on this thread. $\endgroup$
    – Colm Bhandal
    Commented Aug 6, 2015 at 15:56

5 Answers 5

Reset to default
8
+50
$\begingroup$

Switching from proving lower bounds to finding upper bounds, I played around with the list of progressions a bit and came up with another small improvement:

The $16$ progressions $$(1, 2, 4, 8, 16, 32, 64)\\ (3, 6, 12, 24, 48, 96)\\ (5, 10, 20, 40, 80)\\ (7, 14, 28, 56)\\ (9, 18, 36, 72)\\ (11, 22, 44, 88)\\ (13, 26, 52)\\ (15, 30, 60)\\ (17, 34, 68)\\ (19, 38, 76)\\ (21, 42, 84)\\ (23, 46, 92)\\ (25, 35, 49)\\ (27, 45, 75)\\ (50, 70, 98)\\ (81, 90, 100)$$ are completely disjoint and thus cover $7+6+5+3\cdot4+10\cdot3=60$ integers. Using $20$ additional progressions that each cover $2$ of the remaining $100-60=40$ integers yields a cover of $16+20=36$ geometric progressions.

$\endgroup$
3
  • 1
    $\begingroup$ Nice. Getting closer now! Are you using a computer program to aid you with the upper bounds also? $\endgroup$
    – Colm Bhandal
    Commented Aug 9, 2015 at 15:11
  • 2
    $\begingroup$ @ColmBhandal: I just used to computer to give me the list of all progressions of length $\ge3$; the rest was done on paper. $\endgroup$
    – jpvee
    Commented Aug 9, 2015 at 15:24
  • $\begingroup$ A good manual new :P $\endgroup$
    – Paolo Leonetti
    Commented Aug 9, 2015 at 18:57
7
$\begingroup$

The exact value of n is 36:

First, consider all progressions of length 4 or more:

Length 7: 1,2,4,8,16,32,64

Length 6: 3,6,12,24,48,96

Length 5: 5,10,20,40,80$\qquad \ \ $ 1,3,9,27,81$\qquad \ \ $ 16,24,36,54,81

Length 4: 2,6,18,54$\qquad \ \ $ 27,36,48,64$\qquad \ \ $ 7,14,28,56$\qquad \ \ $ 9,18,36,72$\qquad \ \ $ 11,22,44,88$\qquad \ \ $ 8,12,18,27

These progressions cover the 33 numbers

1,2,3,4,5,6,7,8,9,10,11,12,14,16,18,20,22,24,27,28,32,36,40,44,48,54,56,64,72,80,81,88,96

Moreover, two of the length 5 geometric progressions have only 3 numbers disjoint from the progressions of length 6 and 7. Hence, the best way to cover these 33 numbers is to cover 30 of them with 6 geometric progressions:

The progressions of length 7, 6 one of 5 and 3 progressions of length 4:

Length 7: 1,2,4,8,16,32,64

Length 6: 3,6,12,24,48,96

Length 5: 5,10,20,40,80

Length 4: 7,14,28,56$\qquad \ \ $ 9,18,36,72$\qquad \ \ $ 11,22,44,88

There are 35 numbers which are not in a geometric progression of length three or more:

29,31,37,39,41,43,47,51,53,55,57,58,59,61,62,65,67,69, 71,73,74,77,78,79,82,83,85,86,87,89,91,93,94,95,97

So you need 6 progressions to cover 30 numbers, 18 progressions to cover 35 numbers (in fact you cover 36), and the remaining 35 numbers must be covered with at least 12 progressions of length 3 (even if you covered 36 numbers with the 18 progressions in the item before you need 12 to cover 34 numbers).

So you need at least 36 progressions. This bound is achieved in the answer of jpvee, which is therefore optimal. Since the method of counting which numbers are covered by certain progressions is also of jpvee, and my only contribution was to count how many numbers are covered by progressions of length 4 or more, the bounty should be awarded to jpvee.

$\endgroup$
1
  • $\begingroup$ A very noble answer. The bounty goes to jpvee, but this answer is accepted as the final touch. Nice work. $\endgroup$
    – Colm Bhandal
    Commented Sep 11, 2015 at 12:33
4
$\begingroup$

1,2,4,8,16,32,64
3,6,12,24,48,96
5,10,20,40,80
7,14,28,56
11,22,44,88

13,26,52; 17,34,68; 19,38,76; 21,42,84; 23,46,92

9,15,25; 36,60,100; 49,63,81

27,45,75; 50,70,98

15 sequences with 56 numbers. 44 remains, so 15 + 22 = 37.

Not the only 37 solution, some replacements available (36,54,81; 49,70,100; 18,30,50, 50,60,72), so I believe computer program would find better solution quickly if it exists.

Why not 9,27,81 included? Not to spend three "squares" for a single triplet.

$\endgroup$
2
  • $\begingroup$ Nice work. Maybe a computer program is the way to go. If I have time I'll write it. Still, it would be much more pleasing to see a clever proof! $\endgroup$
    – Colm Bhandal
    Commented Aug 7, 2015 at 12:34
  • $\begingroup$ It is interesting to point out that these progressions fit the scheme of my conjecture in the other thread. We have $V(64)=6$ and a sequence of length $7$, $V(96)=5$ with a sequence of length $6$, $V(80)=4$ with a sequence of length five and so on. $\endgroup$
    – Jack D'Aurizio
    Commented Aug 7, 2015 at 15:28
2
$\begingroup$

Nice problem! Using help from the computer, I found that within the positive integers below 100, there are
66 geometric progressions of length 3,
6 geometric progressions of length 4,
3 geometric progressions of length 5,
1 geometric progression of length 6 and
1 geometric progression of length 7
(after eliminating those that are proper subsequences of longer ones).

These progressions of length 3 or longer cover a total of 65 integers $\le 100$; denote the set of these 65 integers by $\mathbb{M}$. If the $6+3+1+1=11$ progressions of lengths $\ge4$ were all disjoint (which they are not), they together would cover $6\cdot4+3\cdot5+6+7=52$ elements of $\mathbb{M}$; for the remaining ones, at least $\lceil(65-52)/3\rceil=5$ additional progressions of length 3 are necessary.

The remaining 35 integers outside of $\mathbb{M}$ can only be contained in progressions of length 2 and thus need at least $\lceil35/2\rceil=18$ of those progressions to cover them.

Therefore, a lower bound of the progressions needed to cover all positive integers up to 100 is $11+5+18=34$.

Update 2015-08-08: I just saw that my reasoning is a bit flawed; see my comment below.

$\endgroup$
7
  • $\begingroup$ Brilliant. The bound shrinks yet again! $\endgroup$
    – Colm Bhandal
    Commented Aug 7, 2015 at 13:10
  • $\begingroup$ This could lead to another question: how many distinct geometric progressions (not proper subsequences of longer ones) of lenght $k$ are there in the set $\{1, ..., n\}$? Would your code answer that in general? $\endgroup$
    – Colm Bhandal
    Commented Aug 7, 2015 at 13:14
  • $\begingroup$ @ColmBhandal: Well; I'd need to modify the program a bit - I hope to find some time for that later on. $\endgroup$
    – jpvee
    Commented Aug 7, 2015 at 14:55
  • $\begingroup$ I'm awfully sorry, but my reasoning is flawed: It is not a good idea to round up twice. Instead, one could use a progression of length 2 to cover the 35th element outside of $\mathbb{M}$ and the 65th element of $\mathbb{M}$, giving a total of $11+4+17+1=33$. (If, however, you take into consideration my remark that the "larger" progressions are not completely disjoint, it is easy to see that $33$ is in fact not achievable.) $\endgroup$
    – jpvee
    Commented Aug 8, 2015 at 7:28
  • $\begingroup$ kudos for the rigour. Looks like your patch works OK- so we still have a lower bound of 34- right? $\endgroup$
    – Colm Bhandal
    Commented Aug 8, 2015 at 12:24
1
$\begingroup$

100, 60, 36. 99, 66, 44. 98, 84, 72. 96, 48, 24, 12, 6, 3. 92, 46, 23. 90, 30, 10. 88, (44,) 22, 11. 84, 42, 21. 81, 54, (36,) (24,) 16. 80, 40, 20, (10,) 5. 76, 38, 19. 75, 45, 27. 68, 34, 17. 64, 32, (16,) 8, 4, 2, 1. That's 49 numbers, with 14 progressions. So we can certainly do it with 40 sequences. Or we can keep going. 56, 28, 14, 7. 52, 26, 13. 49, 35, 25. So, 38 sequences.

EDIT: turns out this question was discussed last year on MathOverflow, and I even contributed (a little bit) to the discussion. I recommend having a look at that discussion before continuing it here.

$\endgroup$
2
  • $\begingroup$ I wonder if there is a more elegant idea than enumeration of all sequences... $\endgroup$
    – Colm Bhandal
    Commented Aug 6, 2015 at 11:20
  • $\begingroup$ Yes those are asymptotic lower bounds, but here the question is asking for a more precise answer for the concrete case of $a_{100}$. $\endgroup$
    – Colm Bhandal
    Commented Aug 6, 2015 at 11:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .