A003002 -id:A003002 - cp's OEIS frontend

A208746 Size of largest subset of [1..n] containing no three terms in geometric progression.

1, 2, 3, 3, 4, 5, 6, 7, 7, 8, 9, 10, 11, 12, 13, 13, 14, 14, 15, 15, 16, 17, 18, 19, 19, 20, 21, 21, 22, 23, 24, 24, 25, 26, 27, 27, 28, 29, 30, 31, 32, 33, 34, 34, 35, 36, 37, 38, 38, 38, 39, 39, 40, 41, 42, 43, 44, 45, 46, 46, 47, 48, 49, 49, 50, 51, 52, 52, 53, 54, 55, 55, 56, 57, 57, 57, 58, 59, 60, 61, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 71, 72, 73, 74, 74, 75, 75, 75, 75

Offset: 1

David Applegate and N. J. A. Sloane, Mar 01 2012

nonn

All three-term geometric progressions must be avoided, even those such as 4,6,9 whose ratio is not an integer.
David Applegate's computation used a floating-point IP solver for the packing subproblems, so although it's almost certainly correct there is no proof. First he enumerated geometric progressions using
for (i=1;i<=N;i++) {
   for (j=2; j*j<=i; j++) {
     if (i % (j*j) != 0) continue;
     for (k=1; k       print i*k*k/(j*j), i*k/j, i;
     }
   }
}
and then solved the integer program of maximizing the subset of {1..N} subject to not taking all 3 of any progression.

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..125
K. O'Bryant, Sets of Natural Numbers with Proscribed Subsets, J. Int. Seq. 18 (2015) # 15.7.7.
Index entries for non-averaging sequences

Cf. A003002.

# Maple program for computing the n-th term from Robert Israel:
A:= proc(n)
     local cons, x;
     cons:=map(op,{seq(map(t -> x[t]+x[b]+x[b^2/t]<=2,
          select(t -> (t=b^2/n),
       numtheory:-divisors(b^2))),b=2..n-1)});
     Optimization:-Maximize(add(x[i],i=1..n),cons, assume=binary)[1]
end proc;

a[n_] := a[n] = If[n <= 2, n, Module[{cons, x}, cons = And @@ Flatten@ Rest@ Union@ Table[x[#] + x[b] + x[b^2/#] <= 2& /@ Select[Divisors[b^2], # < b && # >= b^2/n&], {b, 2, n-1}]; Maximize[{Sum[x[i], {i, 1, n}], cons && AllTrue[Array[x, n], 0 <= # <= 1&]}, Array[x, n], Integers]][[1]]];
Reap[For[n = 1, n <= 100, n++, Print[n, " ", a[n]]; Sow[a[n]]]][[2, 1]] (* Jean-François Alcover, May 18 2023, after Robert Israel *)

a(1)-a(82) confirmed by Robert Israel and extended to a(100), Mar 01 2012

A003004 Size of the largest subset of the numbers [1..n] which does not contain a 5-term arithmetic progression.

Original entry on oeis.org

1, 2, 3, 4, 4, 5, 6, 7, 8, 8, 9, 10, 11, 12, 12, 13, 14, 15, 16, 16, 16, 16, 16, 17, 18, 18, 19, 20, 21, 21, 22, 22, 23, 24, 24, 25, 26, 27, 28, 28, 29, 30, 31, 32, 32, 32, 32, 32, 33, 33, 34, 35, 35, 36, 36, 37, 38, 39, 40, 40, 41, 42, 43, 44, 44, 45, 46, 47, 48, 48

Offset: 1

N. J. A. Sloane

These subsets have been called 5-free sequences.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..115
Thomas Bloom, Problem 3, Problem 139, and Problem 142, Erdős Problems.
Fausto A. C. Cariboni, Sets that yield a(n) for n = 6..115, Apr 30 2018.
Kevin O'Bryant, Sets of Natural Numbers with Proscribed Subsets, J. Int. Seq. 18 (2015) # 15.7.7.
Karl C. Rubin, On sequences of integers with no k terms in arithmetic progression, 1973 [Scanned copy, with correspondence]
Zehui Shao, Fei Deng, Meilian Liang, and Xiaodong Xu, On sets without k-term arithmetic progression, Journal of Computer and System Sciences 78 (2012) 610-618.
Terence Tao, Erdős problem database, see nos. 3, 139, 142.
Samuel S. Wagstaff, Jr., On k-free sequences of integers, Math. Comp., 26 (1972), 767-771.

Cf. A003002, A003003, A003005, A065825.

a(51) and beyond from Fausto A. C. Cariboni, Apr 30 2018

A003005 Size of the largest subset of the numbers [1..n] which doesn't contain a 6-term arithmetic progression.

Original entry on oeis.org

1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9, 10, 11, 12, 13, 13, 14, 15, 16, 17, 17, 18, 19, 20, 21, 22, 22, 22, 23, 23, 23, 24, 25, 25, 26, 27, 28, 28, 29, 30, 31, 31, 31, 32, 33, 34, 34, 35, 36, 37, 38, 38, 38, 39, 39, 40, 40, 41, 42, 42, 43, 44, 44, 45, 46, 47, 47, 48, 48

Offset: 1

N. J. A. Sloane

These subsets have been called 6-free sequences.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..147
Thomas Bloom, Problem 3, Problem 139, and Problem 142, Erdős Problems.
Fausto A. C. Cariboni, Sets that yield a(n) for n = 7..147, May 20 2018.
Kevin O'Bryant, Sets of Natural Numbers with Proscribed Subsets, J. Int. Seq. 18 (2015) # 15.7.7.
Karl C. Rubin, On sequences of integers with no k terms in arithmetic progression, 1973. [Scanned copy, with correspondence]
Zehui Shao, Fei Deng, Meilian Liang, and Xiaodong Xu, On sets without k-term arithmetic progression, Journal of Computer and System Sciences 78 (2012) 610-618.
Terence Tao, Erdős problem database, see nos. 3, 139, 142.
Samuel S. Wagstaff, Jr., On k-free sequences of integers, Math. Comp., 26 (1972), 767-771.

Cf. A003002, A003003, A003004, A065825.

A081611 Number of numbers <= n having no 2 in their ternary representation.

Original entry on oeis.org

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

Offset: 0

Reinhard Zumkeller, Mar 23 2003

nonn

a(n) is also the size of the subset of [1..n] when numbers are added greedily so as to not contain a 3-term arithmetic progression, i.e., according to A003278: a(n) = the largest k such that A003278(k) <= n. (Cf. A003002, the size of the optimal (largest) 3-free subset of [1..n].) - Shreevatsa R, Oct 19 2009

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Cf. A003278, A007089, A039966, A081603, A081608, A061392, A081610.

a081611 n = a081611_list !! n
a081611_list = scanl1 (+) a039966_list
-- Reinhard Zumkeller, Jan 28 2012

R:=PowerSeriesRing(Integers(), 100); Coefficients(R!( (&*[1+x^(3^k): k in [0..5]])/(1-x) )); // G. C. Greubel, Mar 29 2019

CoefficientList[Series[Product[1+x^(3^k), {k,0,5}]/(1-x), {x,0,100}], x] (* G. C. Greubel, Mar 29 2019 *)

{a(n)=local(A,m); if(n<0, 0, m=1; A=1+O(x); while(m<=n, m*=3; A=(1+x)*(1+x+x^2)*subst(A,x,x^3)); polcoeff(A,n))} /* Michael Somos, Aug 31 2006 */

first(n)=my(s,t); vector(n,k,t=Set(digits(k,3)); s+=t[#t]<2) \\ Charles R Greathouse IV, Sep 02 2015

my(x='x+O('x^100)); Vec(prod(k=0,5,1+x^(3^k))/(1-x)) \\ G. C. Greubel, Mar 29 2019

from gmpy2 import digits
def A081611(n):
    l = (s:=digits(n,3)).find('2')
    if l >= 0: s = s[:l]+'1'*(len(s)-l)
    return int(s,2)+1 # Chai Wah Wu, Dec 05 2024

(product(1+x^(3^k) for k in (0..5))/(1-x)).series(x, 100).coefficients(x, sparse=False) # G. C. Greubel, Mar 29 2019

a(n) + A081610(n) = n+1.
From Michael Somos, Aug 31 2006: (Start)
G.f. A(x) satisfies A(x)=(1+x)*(1+x+x^2)*A(x^3).
G.f.: (1/(1-x))*Product_{k>=0} (1+x^(3^k)).
a(n) = a(n-1) + A039966(n). (End)

A104406 Number of numbers <= n having no 2 in ternary representation.

Original entry on oeis.org

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

Offset: 1

Reinhard Zumkeller, Mar 05 2005

nonn

Partial sums of A039966: a(n) = Sum(A039966(k): 1<=k<=n).

N. J. A. Sloane, Table of n, a(n) for n = 1..10000

Cf. A005836, A004642, A039966.

This is a lower bound for A003002.

A296468 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 row or column.

Original entry on oeis.org

1, 4, 6, 11, 17, 24, 28, 32, 40, 47, 57, 66, 78, 90

Offset: 1

Heinrich Ludwig, Dec 13 2017

This sequence is a 2-dimensional generalization of A003002 ("no 3-term arithmetic progressions").

			Up to 66 points (x) may be placed on a 12 X 12 point grid. Example with two symmetry axes:
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 . 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, A193838, A300131.

a(13)-a(14) from Bert Dobbelaere, Jan 06 2020

A358062 a(n) is the diagonal domination number for the queen graph on an n X n chessboard.

Original entry on oeis.org

1, 1, 1, 2, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 11, 12, 12, 13, 14, 15, 15, 16, 17, 18, 18, 19, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 30, 31, 32, 33, 34, 35, 36, 37, 37, 38, 39, 40, 40, 41, 42, 43, 44, 45, 46, 47, 47, 48

Offset: 1

Tanya Khovanova and PRIMES STEP junior group, Oct 28 2022

nonn

a(n) is the smallest number of queens that can be placed on the diagonal of an n X n chessboard attacking all the cells on the chessboard. For large n the diagonal domination number exceeds the domination number.
The diagonal dominating set can be described by the set X of the x-coordinates of all the queens. Cockayne and Hedetniemi showed that for n greater than 1, set X has to be the complement to a midpoint-free even-sum set. Here midpoint-free means that the set doesn't contain an average of any two of its elements. Even-sum means that each sum of a pair of elements is even. Thus the problem of finding the diagonal domination number is equivalent to finding a largest midpoint-free even-sum set in the range 1-n.
a(n) agrees with the connected domination number up to n = 11 but differs for n = 12. - Eric W. Weisstein, Mar 27 2025

			Consider a 9 X 9 chessboard. The largest midpoint-free even-sum set has size 4. For example: 1, 3, 7, and 9 form such a subset. Thus, the queen's position diagonal domination number is 5 and queens can be placed on the diagonal in rows 2, 4, 5, 6, and 8 to dominate the board.

Eric W. Weisstein, Table of n, a(n) for n = 1..211
Irene Choi, Shreyas Ekanathan, Aidan Gao, Tanya Khovanova, Sylvia Zia Lee, Rajarshi Mandal, Vaibhav Rastogi, Daniel Sheffield, Michael Yang, Angela Zhao, and Corey Zhao, The Struggles of Chessland, arXiv:2212.01468 [math.HO], 2022.
E. J. Cockayne and S. T. Hedetniemi, On the diagonal queens domination problem, J. Combin. Theory Ser. A, 42, (1986), 137-139.
Eric Weisstein's World of Mathematics, Connected Dominating Set.
Eric Weisstein's World of Mathematics, Queen Graph.

Cf. A003002 (size of largest Salem-Spencer set in [1..n]).
Cf. A373394 (numbers of minimum connected dominating sets of n X n queen graph).
Cf. A381091 (connected domination number of n X n queen graph).

For n > 1, a(n) = n - A003002(ceiling(n/2)). - Eric W. Weisstein, Mar 07 2025

Formula corrected and terms added based on A003002 by Eric W. Weisstein, Mar 07 2025

A262347 Number of subsets of [1..n] of maximal size that are free of 3-term arithmetic progressions.

Original entry on oeis.org

1, 1, 1, 3, 2, 1, 4, 10, 25, 4, 24, 7, 25, 6, 1, 4, 14, 43, 97, 220, 2, 18, 62, 232, 2, 33, 2, 12, 36, 106, 1, 11, 2, 4, 14, 40, 2, 4, 86, 307, 20, 1, 4, 14, 41, 99, 266, 674, 1505, 3510, 7726, 14, 50, 156, 2, 8, 26, 56, 2, 4, 6, 14, 48, 2, 4, 8, 16, 28, 108, 319, 1046, 4, 26, 82, 1, 2

Offset: 0

Nathan McNew, Sep 18 2015

nonn

The sequence A003002 gives the size of the largest subset of the integers up to n that avoids three-term arithmetic progressions. This sequence gives the number of distinct subsets of [1..n] that have that size and are free of three-term arithmetic progressions.

			The largest subset of [1,6] that doesn't have any 3 terms in arithmetic progression has size 4. There are 4 such subsets with this property: {1,2,4,5}, {1,2,5,6}, {1,3,4,6} and {2,3,5,6}, so a(6)=4.

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..140
Fausto A. C. Cariboni, All sets that yield a(n) for n = 4..130., Feb 19 2018.
Janusz Dybizbanski, Sequences containing no 3-term arithmetic progressions, The Electronic Journal of Combinatorics, 19, no. 2 (2012).
Index entries related to non-averaging sequences

Cf. A003002, A065825.

Last elements of rows of A334187.

G:= proc(n, cons, t)
option remember;
local consn, consr;
   if n < t or member({},cons) then return {} fi;
   if t = 0 then return {{}} fi;
   consn, consr:= selectremove(has,cons,n);
   consn:= subs(n=NULL,consn);
   procname(n-1,consr,t) union
      map(`union`,procname(n-1,consr union   consn,t-1),{n});
end proc:
F:= proc(n)
local m,cons,R;
   m:= A003002(n-1);
   cons:= {seq(seq({i,i+j,i+2*j},i=1..n-2*j),j=1..(n-1)/2)};
   R:= G(n,cons,m+1);
   if R = {} then
      A003002(n):= m;
      G(n,cons,m);
   else
      A003002(n):= m+1;
      R
   fi
end proc:
A003002(1):= 1:
a[1]:= 1:
for n from 2 to 40 do
  a[n]:= nops(F(n))
od:
seq(a[i],i=1..40); # Robert Israel, Sep 20 2015

A003002 = Cases[Import["https://oeis.org/A003002/b003002.txt", "Table"], {, }][[All, 2]];
a[n_] := a[n] = Count[Subsets[Range[n], {A003002[[n+1]]}], s_ /; !MatchQ[s, {_, n1_, _, n2_, _, n3_, _} /; n2 - n1 == n3 - n2]];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 25}] (* Jean-François Alcover, May 30 2020 *)

a(25) to a(44) from Robert Israel, Sep 20 2015
a(45) to a(75) from Fausto A. C. Cariboni, Jan 15 2018
a(0)=1 prepended by Alois P. Heinz, May 16 2020

A225745 Smallest k such that n numbers can be picked in {1,...,k} with no four in arithmetic progression.

Original entry on oeis.org

1, 2, 3, 5, 6, 8, 9, 10, 13, 15, 17, 19, 21, 23, 25, 27, 28, 30, 33, 34, 37, 40, 43, 45, 48, 50, 53, 54, 58, 60, 64, 66, 68, 70, 74, 77, 79, 82, 84, 87, 91

Offset: 1

Don Knuth, Aug 05 2013

			a(8)=10 because of the unique solution 1 2 3 5 6 8 9 10.

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 A003003 as A065825 is to A003002.

a(37)-a(41) from Bert Dobbelaere, Sep 16 2020

A269745 Maximal number of 1's in an n X n {0,1} Toeplitz matrix with property that no four 1's form a square with sides parallel to the edges of the matrix.

Original entry on oeis.org

1, 3, 6, 10, 14, 18, 23, 29, 36, 44, 52, 60, 68, 76

Offset: 1

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

Label the entries in the left edge and top row (reading from the bottom left to the top right) with the numbers 1 through 2n-1, and let S denote the subset of [1..2n-1] where the matrix contains 1's. Then the matrix has the no-subsquare property iff S contains no three-term arithmetic progression.

			n, a(n), example of optimal S:
1, 1, [1]
2, 3, [1, 2]
3, 6, [1, 3, 4]
4, 10, [1, 2, 4, 5]
5, 14, [2, 3, 5, 6]
6, 18, [3, 4, 6, 7]
7, 23, [1, 5, 7, 8, 10]
8, 29, [1, 2, 7, 8, 10, 11]
9, 36, [1, 3, 4, 9, 10, 12, 13]
10, 44, [1, 2, 4, 5, 10, 11, 13, 14]
11, 52, [2, 3, 5, 6, 11, 12, 14, 15]
12, 60, [3, 4, 6, 7, 12, 13, 15, 16]
13, 68, [4, 5, 7, 8, 13, 14, 16, 17]
14, 76, [5, 6, 8, 9, 14, 15, 17, 18]
...
For example, the line 5, 14, [2, 3, 5, 6] corresponds to the Toeplitz matrix
11000
01100
10110
11011
01101
and the value a(5) = 14.

This is a lower bound on A227133.
See A269746 for the analogous sequence for a triangular grid.
Cf. A003002.

a(14) from N. J. A. Sloane, May 05 2016

Previous Showing 11-20 of 31 results. Next

cp's OEIS Frontend

A208746 Size of largest subset of [1..n] containing no three terms in geometric progression.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A003004 Size of the largest subset of the numbers [1..n] which does not contain a 5-term arithmetic progression.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A003005 Size of the largest subset of the numbers [1..n] which doesn't contain a 6-term arithmetic progression.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A081611 Number of numbers <= n having no 2 in their ternary representation.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

PARI

PARI

Python

Sage

Formula

A104406 Number of numbers <= n having no 2 in ternary representation.

Views

Author

Keywords

Comments

Links

Crossrefs

A296468 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 row or column.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A358062 a(n) is the diagonal domination number for the queen graph on an n X n chessboard.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A262347 Number of subsets of [1..n] of maximal size that are free of 3-term arithmetic progressions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs