Cover $\{1,2,...,100\}$ with minimum number of geometric progressions?

Solution 1:

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.

Solution 2:

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.

Solution 3:

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.