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.

%I A309095 #39 Oct 03 2019 11:00:07
%S A309095 2,5,8,10,13,16,18,21,25,28,30,33,35,37,40,42,45,50,53,56,58,60,62,65,
%T A309095 68,70,73,77,80,82,85,88,90,93,96,100,102,105,107,109,112,114,117,120,
%U A309095 122,126,129,132,134,137,139,141,144,148,152,154,157,160,162,165
%N 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.
%C A309095 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.
%C A309095 The difference between consecutive terms is at least 2, because we can always cover 2 extra numbers with a single geometric progression.
%C A309095 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.
%C A309095 {1,2,...,1000} can be covered with 362 geometric progressions, so a(362) >= 1000.
%C A309095 {1,2,...,10000} can be covered with 3620 geometric progressions, so a(3620) >= 10000.
%C A309095 It seems that a(n) is approximately n*e.
%C A309095 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
%H A309095 Rob Pratt, <a href="/A309095/b309095.txt">Table of n, a(n) for n = 1..362</a>
%H A309095 All-Russian Mathematical Olympiad 1995, <a href="https://imomath.com/othercomp/Rus/RusMO95.pdf">Grade 11, problem 1</a>
%H A309095 Dmitry Kamenetsky, <a href="/A309095/a309095.java.txt">Java helper program</a>
%H A309095 Math Overflow, <a href="https://mathoverflow.net/questions/173047/covering-a-set-with-geometric-progressions">Covering a set with geometric progressions</a>
%H A309095 Math StackExchange, <a href="https://math.stackexchange.com/questions/1385844/is-it-possible-to-cover-1-2-100-with-20-geometric-progressions/1385924">Is it possible to cover {1,2,...,100} with 20 geometric progressions?</a>
%H A309095 Math StackExchange, <a href="https://math.stackexchange.com/questions/1386381/cover-1-2-100-with-minimum-number-of-geometric-progressions">Cover {1,2,...,100} with minimum number of geometric progressions?</a>
%H A309095 Math StackExchange, <a href="https://math.stackexchange.com/questions/1385991/what-is-known-about-the-minimal-number-fn-of-geometric-progressions-needed-t">What is known about the minimal number f(n) of geometric progressions needed to cover {1,2,...,n}, as a function of n?</a>
%e A309095 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.
%e A309095 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.
%e A309095 1 to 8 can be covered with 3 geometric progressions: (1,2,4,8), (3,5), (6,7). So a(3) = 8.
%e A309095 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.
%e A309095 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.
%e A309095 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.
%Y A309095 Cf. A309270, A327465 (first differences).
%Y A309095 A327466 and A327469 investigate how many GPs are available.
%K A309095 nonn
%O A309095 1,1
%A A309095 _Dmitry Kamenetsky_, Jul 12 2019
%E A309095 a(37)-a(362) from _Rob Pratt_, Jul 23 2019