|
%I #31 Jun 05 2022 16:14:52
%S 1,2,3,3,4,5,6,7,7,8,9,10,11,12,13,14,15,15,16,16,17,18,19,20,21,22,
%T 23,23,24,25,26,26,27,28,29,30,31,32,33,33,34,35,36,36,37,38,39,39,40,
%U 41,42,42,43,44,45,46,47,48,49,50,51,52,52,52,53,54,55,55,56,57,58,59,60,61,62,62,63,64,65,65,66,67,68,69,70,71,72,73,74,75,76,76,77,78,79,79,80,81,81,81
%N Size of largest subset of [1..n] containing no three terms in a geometric progression with integer ratio.
%C Trivial lower bound: a(n) >= A013928(n+1). - _Charles R Greathouse IV_, Oct 20 2013
%C McNew proves that if n is sufficiently large, then the n-th term is between 0.818n and 0.820n. - _Kevin O'Bryant_, Aug 17 2015
%H Fausto A. C. Cariboni, <a href="/A230490/b230490.txt">Table of n, a(n) for n = 1..152</a>
%H M. Beiglboeck, V. Bergelson, N. Hindman, and D. Strauss, <a href="http://dx.doi.org/10.1016/j.jcta.2005.11.003">Multiplicative structures in additively large sets</a>, J. Combin. Theory Ser. A 113 (2006)
%H N. McNew, <a href="http://arxiv.org/abs/1310.2277">On sets of integers which contain no three terms in geometric progression</a>, arXiv:1310.2277 [math.NT], 2013.
%H M. B. Nathanson and K. O'Bryant, <a href="http://arxiv.org/abs/1408.2880">A problem of Rankin on sets without geometric progressions</a>, arXiv:1408.2880 [math.NT], 2014.
%H K. O'Bryant, <a href="http://arxiv.org/abs/1410.4900">Sets of natural numbers with proscribed subsets</a>, arXiv:1410.4900 [math.NT], 2014-2015.
%e The integers [1..9] include the three geometric progressions (1,2,4) (2,4,8) and (1,3,9), which cannot all be precluded with any 1 exclusion, but 2 exclusions suffice. Thus the size of the largest subsets of [1..9] free of integer ratio geometric progressions is 7.
%o (PARI) ok(v)=for(i=3,#v,my(k=v[i]);fordiv(core(k,1)[2],d,if(d>1 && setsearch(v,k/d) && setsearch(v,k/d^2), return(0)))); 1
%o a(n)=my(v=select(k->4*k>n&&issquarefree(k),vector(n,i,i)), u=setminus(vector(n, i,i),v),r,H);for(i=1,2^#u-1,H=hammingweight(i); if(H>r && ok(vecsort(concat(v,vecextract(u,i)),,8)),r=H));#v+r \\ _Charles R Greathouse IV_, Oct 20 2013
%Y Cf. A003002, A013928, A208746 is similar but also allows progressions with rational ratio, like (4,6,9).
%K nonn
%O 1,2
%A _Nathan McNew_, Oct 20 2013
|
