A230490 Size of largest subset of [1..n] containing no three terms in a geometric progression with integer ratio.

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, 23, 23, 24, 25, 26, 26, 27, 28, 29, 30, 31, 32, 33, 33, 34, 35, 36, 36, 37, 38, 39, 39, 40, 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

Offset: 1

Author

Nathan McNew, Oct 20 2013

Keywords

• nonn

Comments

Trivial lower bound: a(n) >= A013928(n+1). - Charles R Greathouse IV, Oct 20 2013

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

Examples

			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.
		

Links

• Fausto A. C. Cariboni, Table of n, a(n) for n = 1..152
• M. Beiglboeck, V. Bergelson, N. Hindman, and D. Strauss, Multiplicative structures in additively large sets, J. Combin. Theory Ser. A 113 (2006)
• N. McNew, On sets of integers which contain no three terms in geometric progression, arXiv:1310.2277 [math.NT], 2013.
• M. B. Nathanson and K. O'Bryant, A problem of Rankin on sets without geometric progressions, arXiv:1408.2880 [math.NT], 2014.
• K. O'Bryant, Sets of natural numbers with proscribed subsets, arXiv:1410.4900 [math.NT], 2014-2015.

Crossrefs

Cf. A003002, A013928, A208746 is similar but also allows progressions with rational ratio, like (4,6,9).

Programs

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