A003002 -id:A003002 - cp's OEIS frontend

A300131 Largest number of points that can be placed on an n X n point grid so that no point is equally distant from two other points on the same straight line.

1, 4, 6, 9, 16, 17, 21, 26, 31, 34, 40, 46

Offset: 1

Heinrich Ludwig, Feb 26 2018

This definition is a 2-dimensional generalization of A003002 ("no 3-term arithmetic progressions"). It generalizes the definition of A296468 to include not only triples on horizontal or vertical lines but on any straight line.

			On a 10 X 10 point grid 34 points (X) can be placed at most. Example:
  . X . . . X X . . .
  X X . . . X X . X .
  X . X X . . . . X .
  . . X . . . . X . X
  . . . . . . . . X X
  X X . . . . . . . .
  X . X . . . . X . .
  . X . . . . X X . X
  . X . X X . . . X X
  . . . X X . . . X .

Cf. A003002, A296468.

a(11) from Bert Dobbelaere, Jan 09 2020

a(12) from Bert Dobbelaere, Jan 12 2020

A334894 Number of maximal subsets of [n] avoiding 3-term arithmetic progressions and containing n if n>0.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 3, 6, 15, 4, 20, 7, 18, 6, 1, 3, 10, 29, 54, 123, 2, 16, 44, 170, 2, 31, 2, 10, 24, 70, 1, 10, 2, 2, 10, 26, 2, 2, 82, 221, 20, 1, 3, 10, 27, 58, 167, 408, 831, 2005, 4216, 14, 36, 106, 2, 6, 18, 30, 2, 2, 2, 8, 34, 2, 2, 4, 8, 12, 80, 211

Offset: 0

Alois P. Heinz, May 14 2020

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..136
Eric Weisstein's World of Mathematics, Nonaveraging Sequence
Wikipedia, Arithmetic progression
Wikipedia, Iverson bracket
Wikipedia, Salem-Spencer set
Index entries related to non-averaging sequences

Last elements of rows of A334892.

Cf. A003002, A262347, A334187.

a(n) = A262347(n) - [n > 0 and A003002(n) = A003002(n-1)] * A262347(n-1).
a(n) = A334892(n,A003002(n)).
a(n) = A334187(n,A003002(n)) - [n > 0] * A334187(n-1,A003002(n)).

A362942 Partial sums of A229037.

Original entry on oeis.org

1, 2, 4, 5, 6, 8, 10, 14, 18, 19, 20, 22, 23, 24, 26, 28, 32, 36, 38, 42, 46, 51, 56, 64, 69, 74, 83, 84, 85, 87, 88, 89, 91, 93, 97, 101, 102, 103, 105, 106, 107, 109, 111, 115, 119, 121, 125, 129, 134, 139, 147, 152, 157, 166, 175, 179, 183, 188, 193

Offset: 1

N. J. A. Sloane, Sep 12 2023

nonn

Michael S. Branicky, Table of n, a(n) for n = 1..100000 (using b-file in A229037)
N. J. A. Sloane, New Gilbreath Conjectures, Sum and Erase, Dissecting Polygons, and Other New Sequences, Doron Zeilberger's Exper. Math. Seminar, Rutgers, Sep 14 2023: Video, Slides, Updates. (Mentions this sequence.)

Cf. A003002, A229037.

a[1] = 1; a[n_] := a[n] = Block[{z = 1}, While[Catch[Do[If[z == 2*a[n - k] - a[n - 2*k], Throw@ True], {k, Floor[(n - 1)/2]}]; False], z++]; z]; Accumulate@ Array[a, 120] (* Michael De Vlieger, Sep 12 2023, after Giovanni Resta at A229037 *)

from itertools import count, islice
def A362942_gen(): # generator of terms
    blist, c = [], 0
    for n in count(0):
        i, j, b = 1, 1, set()
        while n-(i<<1) >= 0:
            b.add((blist[n-i]<<1)-blist[n-2*i])
            i += 1
            while j in b:
                j += 1
        blist.append(j)
        yield (c:=c+j)
A362942_list = list(islice(A362942_gen(),30)) # Chai Wah Wu, Sep 12 2023

A225859 Smallest k such that n numbers can be picked in {1,...,k} with no five terms in arithmetic progression.

Original entry on oeis.org

1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 24, 25, 27, 28, 29, 31, 33, 34, 36, 37, 38, 39, 41, 42, 43, 44, 49, 51, 52, 54, 56, 57, 58, 59, 61, 62, 63, 64, 66, 67, 68, 69, 76

Offset: 1

Don Knuth, Aug 05 2013

Knuth, Donald E., Satisfiability, Fascicle 6, volume 4 of The Art of Computer Programming. Addison-Wesley, 2015, pages 135 and 190, Problem 31.

Samuel S. Wagstaff, Jr., On k-free sequences of integers, Math. Comp., 26 (1972), 767-771.

This sequence is to A003004 as A065825 is to A003002.

Cf. A226066.

A226066 Smallest k such that n numbers can be picked in {1,...,k} with no six terms in arithmetic progression.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 10, 12, 13, 14, 15, 17, 18, 19, 20, 22, 23, 24, 25, 26, 29, 32, 33, 35, 36, 37, 39, 40, 41, 44, 45, 46, 48, 49, 50, 51, 54, 56, 58, 59, 61, 62

Offset: 1

Don Knuth, Aug 05 2013

Knuth, Donald E., Satisfiability, Fascicle 6, volume 4 of The Art of Computer Programming. Addison-Wesley, 2015, pages 135 and 190, Problem 31.

Samuel S. Wagstaff, Jr., On k-free sequences of integers, Math. Comp., 26 (1972), 767-771.

This sequence is to A003005 as A065825 is to A003002.

Cf. A225745, A225859.

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

Original entry on oeis.org

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

Nathan McNew, Oct 20 2013

nonn

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

			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.

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.

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

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

A236697 First differences of A131741.

Original entry on oeis.org

1, 2, 6, 2, 16, 2, 6, 4, 26, 6, 10, 6, 12, 6, 20, 12, 18, 22, 14, 34, 6, 30, 8, 10, 26, 24, 6, 42, 10, 8, 4, 8, 22, 2, 34, 24, 8, 10, 54, 8, 42, 28, 6, 96, 26, 40, 14, 60, 4, 20, 30, 46, 26, 12, 42, 28, 2, 70, 8, 126, 4, 26, 34, 6, 42, 18, 96, 26, 48, 4

Offset: 1

Zak Seidov, Jan 30 2014

nonn

Among first 10000 terms, the largest is a(7790) = 17412.

Zak Seidov, Table of n, a(n) for n = 1..10000

Cf. A003002, A003003, A003278, A004793, A005047, A005487, A033157, A065825, A092482, A093678, A093679, A093680, A093681, A093682, A094870, A101884, A101886, A101888, A131741, A140577, A185256, A208746, A229037.

a(n) = A131741(n+1) - A131741(n).

A269746 Maximal number of 1's in an equilateral triangle of 0's and 1's with n points on each side, the entries being constant on vertical lines, with property that no three 1's form a triangle with sides parallel to the edges of the triangle.

Original entry on oeis.org

1, 2, 4, 6, 8, 10, 13, 16, 20, 24, 28, 32, 36, 40

Offset: 1

Warren D. Smith and N. J. A. Sloane, Mar 20 2016

The triangle is oriented with apex at the top and horizontal base.

Label the entries in the top left and right edges with the numbers 1 through 2n-1, and let S denote the subset of [1..2n-1] where these edges contains 1's. Then the matrix has the no-subtriangle property iff S contains no three-term arithmetic progression.

			n, a(n), example of optimal S:
1, 1, [1]
2, 2, [1, 2]
3, 4, [1, 3, 4]
4, 6, [1, 2, 4, 5]
5, 8, [2, 3, 5, 6]
6, 10, [3, 4, 6, 7]
7, 13, [1, 5, 7, 8, 10]
8, 16, [1, 2, 7, 8, 10, 11]
9, 20, [1, 3, 4, 9, 10, 12, 13]
10, 24, [1, 2, 4, 5, 10, 11, 13, 14]
11, 28, [2, 3, 5, 6, 11, 12, 14, 15]
12, 32, [3, 4, 6, 7, 12, 13, 15, 16]
13, 36, [4, 5, 7, 8, 13, 14, 16, 17]
14, 40, [5, 6, 8, 9, 14, 15, 17, 18]
...
For example, the line 5, 8, [2, 3, 5, 6] corresponds to the triangle
....1....
...0.1...
..1.1.0..
.1.0.1.0.
0.1.1.0.0
and the value a(5) = 8.
It is a plausible conjecture that any optimal solution S here is also an optimal solution to the square grid version in A269745, and vice versa. (The square grid being obtained by reflecting the triangle in its base.)

This is a lower bound on A227308.

Cf. A003002, A269745.

A296994 Largest number of points that can be selected from an n X n X n triangular point grid so that no selected point is equally distant from two other selected points on a straight line, which is parallel to one side of the grid.

Original entry on oeis.org

1, 3, 4, 7, 10, 14, 18, 20, 23, 27, 31, 36, 42, 48, 54, 61, 68, 76, 84, 92, 98

Offset: 1

Heinrich Ludwig, Mar 26 2018

This sequence generalizes the idea of A003002 ("no 3-term arithmetic progressions") for triangular point grids.

For the same idea applied to square grids see A296468 and A300131.

			At most 54 points (X) can be chosen from a 15 X 15 X 15 triangular point grid under the condition mentioned above. Example:
                 o
                X X
               X o X
              o X X o
             X X o X X
            X o o o o X
           o o X o X o o
          o o o o o o o o
         o o X X o X X o o
        o X o o X X o o X o
       X X o o X o X o o X X
      X o X X o o o o X X o X
     o X X o o X o X o o X X o
    X X o X X o o o o X X o X X
   X o o o o X X o X X o o o o X

Cf. A296468, A300131.

a(20) from Heinrich Ludwig, Apr 24 2018

a(21) from Heinrich Ludwig, May 01 2018

A304884 Size of the largest subset of the cyclic group of order n which does not contain a nontrivial 3-term arithmetic progression.

Original entry on oeis.org

1, 2, 2, 2, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 6, 5, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 9, 8, 10, 8, 10, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 11, 12, 11, 11, 11, 11, 12, 11, 12, 12, 13, 12, 13, 13, 14, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15

Offset: 1

Daniel Scheinerman, May 20 2018

nonn

Each term is at most the corresponding term of A003002.

Arithmetic progressions are trivial if they are of the form x,x,x.

			For n=10, the integers (mod 10) have sets with four elements like {1,2,4,5} which contain no arithmetic progressions with 3 elements, but no such sets with five elements.  For example, {1,2,4,5,8} has the progression 2,8,4, and {1,2,4,5,9} has the progression 4,9,4.  Since four is the most elements possible, a(10) = 4. - _Michael B. Porter_, May 26 2018

L. Halbeisen and S. Halbeisen, Avoiding arithmetic progressions in cyclic groups, Swiss Mathematical Society, 2005.

Cf. A003002.

a(51)-a(79) from Giovanni Resta, May 22 2018

cp's OEIS Frontend

A300131 Largest number of points that can be placed on an n X n point grid so that no point is equally distant from two other points on the same straight line.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A334894 Number of maximal subsets of [n] avoiding 3-term arithmetic progressions and containing n if n>0.

Views

Author

Keywords

Links

Crossrefs

Formula

A362942 Partial sums of A229037.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

A225859 Smallest k such that n numbers can be picked in {1,...,k} with no five terms in arithmetic progression.

Views

Author

Keywords

References

Links

Crossrefs

A226066 Smallest k such that n numbers can be picked in {1,...,k} with no six terms in arithmetic progression.

Views

Author

Keywords

References

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A236697 First differences of A131741.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A269746 Maximal number of 1's in an equilateral triangle of 0's and 1's with n points on each side, the entries being constant on vertical lines, with property that no three 1's form a triangle with sides parallel to the edges of the triangle.

Views

Author

Keywords

Comments

Examples

Crossrefs

A296994 Largest number of points that can be selected from an n X n X n triangular point grid so that no selected point is equally distant from two other selected points on a straight line, which is parallel to one side of the grid.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A304884 Size of the largest subset of the cyclic group of order n which does not contain a nontrivial 3-term arithmetic progression.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs