A327469 -id:A327469 - cp's OEIS frontend

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

Dmitry Kamenetsky, Jul 12 2019

nonn

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

			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.

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?

Cf. A309270, A327465 (first differences).

A327466 and A327469 investigate how many GPs are available.

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

A327466 Number of nonempty subsets of [1..n] which are geometric progressions with rational ratio and are locally maximal.

Original entry on oeis.org

1, 1, 3, 4, 8, 13, 19, 23, 27, 36, 46, 55, 67, 80, 94, 103, 119, 132, 150, 167, 187, 208, 230, 250, 266, 291, 311, 336, 364, 393, 423, 447, 479, 512, 546

Offset: 1

N. J. A. Sloane, Sep 29 2019

"Locally maximal" subsets are those subsets in geometrical progression that cannot be extended to a larger subset of [1..n] in geometric progression. [Comment made precise by Giovanni Resta, Sep 30 2019.]

One might have expected that the GP would be required to have an integer ratio, but in fact we allow rational ratios. The GPs can be assumed to be strictly increasing. - N. J. A. Sloane, Oct 03 2019

			Illustrations of some initial terms:
n=3: (12),(13),(23).
n=4: (124),(13),(23),(34).
n=8: (1248), plus all 28 pairs (ij) from [1..8] except the six subsets of (1248), so a(8) = 1 + 28 - 6 = 23.

See A327469 for GPs of length > 2.

Cf. A309095.

a[1] = 1; a[n_] := Block[{t = Select[ Subsets[ Range[n], {2, Ceiling[ Log2[n + 1]]}], Length@ Union[ Rest[#]/ Most[#]] == 1 &], i = 2}, t = Reverse@ SortBy[t, Length]; i=2; While[i <= Length[t], If[ AnyTrue[ Take[t, i-1], SubsetQ[#, t[[i]]] &], t = Delete[t, i]; i=2; Continue[], i++]]; Length@ t]; Array[a, 16] (* Giovanni Resta, Sep 30 2019 *)

a(9)-a(35) from Giovanni Resta, Sep 30 2019

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions