login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 5
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 25 00:48 EDT 2020. Contains 337333 sequences. (Running on oeis4.)