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,1

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

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?

Example

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.

Crossrefs

Cf. A309270, A327465 (first differences).

A327466 and A327469 investigate how many GPs are available.

Sequence in context: A126281 A117630 A284774 * A022843 A054088 A186540

Adjacent sequences: A309092 A309093 A309094 * A309096 A309097 A309098

Keyword

nonn

Author

Dmitry Kamenetsky, Jul 12 2019

Extensions

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

Status

approved