A309095 a(n) is the largest k such that every number from 1 to k can be covered by n geometric progressions of rational numbers.

2, 5, 8, 10, 13, 16, 18, 21, 25, 28, 30, 33, 35, 37, 40, 42, 45, 50, 53, 56, 58, 60, 62, 65, 68, 70, 73, 77, 80, 82, 85, 88, 90, 93, 96, 100, 102, 105, 107, 109, 112, 114, 117, 120, 122, 126, 129, 132, 134, 137, 139, 141, 144, 148, 152, 154, 157, 160, 162, 165

Offset: 1

Author

Dmitry Kamenetsky, Jul 12 2019

Keywords

• nonn

Comments

Each term in a geometric progression must be an integer, but the ratio between two consecutive terms can be a rational number. This means that geometric progressions like (9,15,25) are allowed.

The difference between consecutive terms is at least 2, because we can always cover 2 extra numbers with a single geometric progression.

The original problem discussed in the links gives a(36) >= 100. In fact one cannot cover {1,2,...,101} with 36 geometric progressions, so a(36) = 100.

{1,2,...,1000} can be covered with 362 geometric progressions, so a(362) >= 1000.

{1,2,...,10000} can be covered with 3620 geometric progressions, so a(3620) >= 10000.

It seems that a(n) is approximately n*e.

Finding the smallest n for a given k is a set covering problem with a binary variable for each geometric progression and a constraint for each number from 1 to k. - Rob Pratt, Jul 23 2019

Examples

			1 to 2 can be covered with 1 geometric progression: (1,2). So a(1) = 2. Note that we cannot cover 1 to 3 with 1 geometric progression.
1 to 5 can be covered with 2 geometric progressions: (1,2,4) and (3,5). So a(2) = 5. Note that we cannot cover 1 to 6 with 2 geometric progressions.
1 to 8 can be covered with 3 geometric progressions: (1,2,4,8), (3,5), (6,7). So a(3) = 8.
1 to 10 can be covered with 4 geometric progressions: (1,2,4,8), (1,3,9), (5,6), (7,10). So a(4) = 10.
1 to 13 can be covered with 5 geometric progressions: (1,2,4,8), (3,6,12), (5,7), (9,10), (11,13). So a(5) = 13.
1 to 16 can be covered with 6 geometric progressions: (1,2,4,8,16), (3,6,12), (5,7), (9,10), (11,13), (14,15). So a(6) = 16.
		

Links

• Rob Pratt, Table of n, a(n) for n = 1..362
• All-Russian Mathematical Olympiad 1995, Grade 11, problem 1
• Dmitry Kamenetsky, Java helper program
• Math Overflow, Covering a set with geometric progressions
• Math StackExchange, Is it possible to cover {1,2,...,100} with 20 geometric progressions?
• Math StackExchange, Cover {1,2,...,100} with minimum number of geometric progressions?
• Math StackExchange, What is known about the minimal number f(n) of geometric progressions needed to cover {1,2,...,n}, as a function of n?

Crossrefs

Cf. A309270, A327465 (first differences).

A327466 and A327469 investigate how many GPs are available.

Extensions

a(37)-a(362) from Rob Pratt, Jul 23 2019