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

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

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.

Example

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.

Prog

(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

Crossrefs

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

Sequence in context: A391285 A138467 A208746 * A247983 A127036 A108789

Adjacent sequences: A230487 A230488 A230489 * A230491 A230492 A230493

Keyword

nonn

Author

Nathan McNew, Oct 20 2013

Status

approved